Putting and comparing dominoes in order in C, using list or not ( if you can without)

Question

The program asks to check if you have equal dominoes ( if you have at least one possibility to merge data 12|21) and asks to show an order that reaps the basic rule of the Dorians ( 12|24|45|53 );

An accepted entry would be:

3 // número de dominós<br/>
1 3 //<br/>
1 5 // possibilidades<br/>
3 2 //<br/>
2 // número de dominós<br/>
3 4<br/>
2 5<br/>
0 // 0 sinaliza o fim do input ( NumDeDados = 0) <br/>

and an accepted exit would be:

Teste 1<br/>
sim<br/> // validade() retornou 1... existe pelo menos uma combinação
51|13|32|<br/> // FuncaoMestre... coloca os dados na "ordem"
Teste 2<br/>
nao<br/> // return != 1
nao<br/>

The basic scope of the program, without the logical functions, because that is the doubt :)

#include <stdio.h>
int main(){
int NumOfDominoes = 1, Test = 1, Dominoes=1;
int E,D;
int boolean=1;

while( NumOfDominoes != 0 )
{
    scanf("%d",&NumOfDominoes);
    while( Dominoes < NumOfDominoes)
    {
        scanf("%d %d",&E,&D);
        Insert( E, D); // dominó em si
        Dominoes++;
    }

}

for( Test ; Test <= NumOfDominoes ; Test++)
{
    printf("Teste %d\n",Test);

    boolean = validity();  //retorna 1 se a sequência de dominós apresenta pelo menos uma possibilidade aceita.

    if( boolean = 1) printf("sim\n");
    else {printf("nao\nnao\n");}

        masterFunction( E, D); //coloca os dominós em ordem, 01|13|35...
}
return 0;

}

Insert(), Validity(), Function missing()

I don’t know how to enter correctly, whether it would be a list, a double-chained list, whether it needs two-dimensional vectors, nor how to validate the possibility of joining and much less how to put in "order".

I’ve been at it for a week, any help is welcome.

Updating:

Stack Overflow user3386109 user said:

"The solution to this problem is known as 'Depth-first search', which is typically implemented using recursion. Choose an initial domino (in both guidelines). Limiting the choices and guidelines for the second domino in the chain. Keep adding dominoes until there are possible choices for the next domino or for all the dominoes that have been added. If you tried every initial domino possible with all subsequent dominoes and no use of dominoes chain, then the answer is no."

My question, and this answer in English

Answer 1

You’ve already had the gist of your answer: build a recursive algorithm.

If you choose to use a linked list, the advantage is that the removal of items will be quite efficient. Thus, it is possible to construct with some ease the following algorithm:

1. Construct a list of read pieces. Use a data structure that contains for each piece the values on the left and right (using a struct, for example).

2. In the main program, make a loop (a for) to iterate on all elements of this list. The idea is that you will test each one of them to see if there is a solution that begins with such a piece. There are actually two tests per piece: one with it starting at the left (that is, connecting at the right number), and one with it starting at the right (that is, connecting at the left number).

3. Inside this loop, choose the current tile as "first" and one of its numbers to start. Then create a sublist from the removal of the first chosen piece for the test. Using a linked list this removal is efficient: clone the original list and remove the current domino from the loop. This sublist will be used to limit the searches in the recursive call.

4. Call a function (name solucao, for example) that will recursively process the answer you want. Pass to this created sublist function (that is, containing only the next possible dominoes to be connected), the first piece (already chosen) and the number by which it will connect. This function will internally do something similar to the previous steps of the main program: it will scroll through the received list (which is already a sub-list of your previous call! ), trying to find an item that connects to the number received as parameter. If it does not find it is a sign that there is no solution for this number/connection. Therefore, it can return an indicative return of failure. If she finds a piece that connects, she’ll need to keep searching for the other items.

5. So, if you find a connection, just create a new sublist (removing from the "original" list - which, remember, was already a sublist - this next piece found) and recursively search for another piece that connects. The idea of recursion is precisely the deep search in the connection possibilities tree. If the search goes down and does not find a solution, the stacked calls will return until you find a solution (if it exists). If this new recursive call solucao find an answer, you found it and just match the current piece, with the next piece found to build part of the answer. If not, there is no solution.

Obs. Vc can do recursive function solucao already return a string with the solution or an empty string ("") if I can’t fix it. Thus, its indication of "has solution" is to return the strings with the current piece concatenated with the next piece, and the indication of "has no solution" is to return the empty string.

As I don’t have time to prepare a pure C example (which also shouldn’t be done, since your question is probably a school project that you must learn to do by yourself), I just prepared an example in C++. It’s not for you to copy and paste, obviously, but it might help you understand a little more the simple algorithm proposal.

Remember that in C you will need to implement some of the things that there are facilitated by the use of Standard Library of C++ as the linked list (where I use the std::vector), cloning and removal of elements (where I use the allocation operator and the algorithms std::vector::erase and std::remove), the data structure domino (that I used a class, that you will certainly use as a struct), etc..

Anyway, here’s the code:

#include <vector>
#include <algorithm>
#include <iostream>
#include <string>

using namespace std;

class Domino
{
public:
    unsigned short e; // Número na esquerda
    unsigned short d; // Número na direita

    // Construtor padrão
    Domino()
    {
        e = 0;
        d = 0;
    }

    // Construtor com os parâmetros 
    Domino(unsigned short e, unsigned short d)
    {
        this->e = e;
        this->d = d;
    }

    // Operador de igualdade (pra permitir a comparação usada nos métodos erase/remove)
    bool operator==(const Domino &oOutro)
    {
        return this->e == oOutro.e && this->d == oOutro.d;
    }

    // Pra facilitar a geração da string da peça
    string toString(unsigned int iNaDireita)
    {
        string s;
        if (iNaDireita == e)
            s = to_string(d) + to_string(e);
        else
            s = to_string(e) + to_string(d);

        return s;
    }
};

typedef vector<Domino> Dominos;

// Função de procura recursiva por conexoes a partir de uma peça e número dados
string solucao(Dominos vPecas, Domino oPeca, unsigned short iNumero)
{
    Domino oProxima;
    unsigned short iProximo;
    bool bFound = false;

    // Procura por uma peça qualquer que encaixe na peça + número dados
    for (unsigned int i = 0; i < vPecas.size(); i++)
    {
        Domino oAtual = vPecas[i];
        if (oAtual.e == iNumero || oAtual.d == iNumero)
        {
            oProxima = oAtual;
            iProximo = (oAtual.e == iNumero) ? oAtual.d : oAtual.e; // !!OBSERVAÇÃO!!
            bFound = true;
            break;
        }
    }

    // Se encontrou alguma peça que se encaixa, checka a solução
    if (bFound)
    {
        // Se só existe ela e ela encaixa, pronto! Achou-se a solução!
        if (vPecas.size() == 1)
            return oPeca.toString(iNumero) + "|" + oProxima.toString(iProximo);

        // Mas se existem mais peças, continua a busca recursivamente...
        else 
        {
            Dominos vOutros = vPecas; // Clona a lista
            // Remove a próxima peça do clone, criando a sublista
            vOutros.erase(remove(vOutros.begin(), vOutros.end(), oProxima));

            // Procura recursivamente por outra, considerando agora a próxima peça como "primeira"
            // O número para a nova conexão deve ser *necessariamente* o oposto àquele que encaixou,
            // o que foi decidido anteriormente onde está marcado com o comentário "!!OBSERVAÇÃO!!"
            string s = solucao(vOutros, oProxima, iProximo);

            if (s.length() == 0)
                return ""; // Não tem solução porque há mais peças, mas elas não encaixam
            else
                return oPeca.toString(iNumero) + "|" + s; // Tem solução! Monta e devolve!
        }
    }
    else
        return ""; // Não tem solução porque não há peças que encaixam na peça recebida como parâmetro
}

int main()
{
    Dominos vPecas;
    /*vPecas.push_back(Domino(1, 3));
    vPecas.push_back(Domino(1, 5));
    vPecas.push_back(Domino(3, 2));*/

    vPecas.push_back(Domino(3, 4));
    vPecas.push_back(Domino(2, 5));
    vPecas.push_back(Domino(3, 6));
    vPecas.push_back(Domino(4, 5));

    // Tenta uma solução com cada uma das peças, posicionada à esquerda ou à direita
    string sSolucao;
    for (unsigned int i = 0; i < vPecas.size(); i++)
    {
        Domino oPrimeira = vPecas[i];

        Dominos vOutros = vPecas; // Clona a lista
        // Remove da lista clonada a peça usada como primeira
        vOutros.erase(remove(vOutros.begin(), vOutros.end(), oPrimeira));

        // Tenta uma solução com a peça colocada à esquerda
        sSolucao = solucao(vOutros, oPrimeira, oPrimeira.d);

        // Se encontrou, ótimo!
        if (sSolucao.length() != 0)
            break;
        // Senão, tenta com a peça colocada à direita
        else
        {
            sSolucao = solucao(vOutros, oPrimeira, oPrimeira.e);
            if (sSolucao.length() != 0)
                break;
        }
    }

    // verifica se algo foi devolvido. Se não, não há solução
    if (sSolucao.length() == 0)
        sSolucao = "Solucao nao encontrada.";

    // Imprime a resposta
    cout << "Resposta do algoritmo:" << endl;
    cout << sSolucao << endl;
    return 0;
}

This code produces the following result for the parts 3 4, 2 5, 3 6 and 4 5 (I used in place of your example):

Resposta do algoritmo:
25|54|43|36

Answer 2

Luiz Viera’s excellent answer! Just out of curiosity and to complement, this dominoes problem is a classic problem in graph theory! It is isomorphic to the problem of bridges from generalized Königsberg to n bridges.

The problem is a city full of islands and bridges. The goal is to travel a path passing exactly once over each bridge. This can be modeled as a graph considering islands as vertices and bridges as edges.

If you place each vertex as a number and consider the domino piece 1|5 as a bridge connecting vertex 1 to 5 and the same for all pieces, you will see that the two problems are the same! Just as each domino piece can only be worn out once, each bridge can only be crossed once. Just like every domino piece has to be worn out, every bridge has to be crossed.

Euler solved this problem for all cases and the solution is called Euler’s path. Every solution of a domino game is also a path of Euler. He found that this problem can only be solved if the graph is connected and has no more than two vertices with odd valence.

So to know if the problem has a solution or not, just see if the graph is connected, which can be done easily with a side search (BFS) and also calculate how many times each number appears in the dominoes. If more than two numbers appear an odd number of times, there is no solution! Two numbers may appear an odd number of times, as they can be placed at the beginning and end of the path, but if a third appears an odd number of times it will surely be on the outside. So if number 1 is in 3 pieces, 2 in 1 piece and 3 in 5 pieces, there is no solution (1, 2 and 3 have odd valence).

A very efficient solution is to "cut" all numbers that has more than 2 pieces. For example, if you have 4 pieces with the number 5 turn 2 pieces with 5-1 and 2 with 5-2. All vertices have to be cut according to the paths that go back to the vertex (otherwise the graph is disconnected). After the cuts the solution is made with a greedy algorithm, since all the numbers appeared only 2 times (except the endings)! Cuts can be performed at once with a special type of lateral search.

I’m not going to put the algorithm here now, since it would take a long time to do so. I left the answer more out of curiosity and to give a direction to those who want to go a little deeper.