Placing and comparing dominoes in order in C, using list or not (if not)

You've already had the essentials 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. So, you can build the following algorithm with some ease:

Build a list with the parts read. Use a data structure that contains left and right values for each part (using a struct , for example).

In the main program, loop (a for ) to iterate over all elements in that list. The idea is that you will test each of them to see if there is a solution that starts with that part. They are actually two tests per piece: one with it starting at the left (ie connecting by the right number), and one with it starting at the right (ie, connecting by the number on the left).

>

Within this loop, choose the current part as "first" and one of its numbers to start. Then create a sublist from the removal of the first part chosen 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 recursive call searches.

Call a function (named solucao , for example) that will recursively process the response you want. Pass to this function the created sublist (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 internalize something similar to the previous steps of the main program: it will scroll through the received list (which is already a sublist of your previous call!), Trying to find an item that connects to the number received as a parameter. If it does not find a sign that there is no solution for that number / connection. Therefore, it may return a return indicative of failure. If she finds a piece that connects, she'll need to keep searching for the other items.

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 search recursively for another piece that connects . The idea of recursion is precisely the search in depth in the tree of possibilities of connections. If the search goes down and you do not find a solution, the stacked calls will return until you find a solution (if it exists). If this new recursive call of solucao finds a response, you have found it and simply combine the current part with the next part found to build part of the response. If you have not found it, you have no solution.

Obs. You can make the recursive function solucao already return a string with the solution or an empty string ( "" ) if there is no solution. So your "solution" statement is to return the strings with the current part concatenated with the next piece, and the "no solution" indication is to return the empty string.

As I do not have time to prepare an example in pure C (which should also not be done, since your question is probably a school work you should learn to do by itself ), I just prepared an example in C ++. It's not for you to copy and paste, of course, but it might help you to understand the proposed simple algorithm a little more.

  

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

At last, 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 (which I used instead of your example):

Resposta do algoritmo:
25|54|43|36

    

Excellent answer from Luiz Viera! Just curious and to complement, this domino problem is a classic problem in Graph theory! It is isomorphic to the problem of generalized Königsberg bridges for n bridges.

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

If you put each vertex as a number and consider the domino piece 1 | 5 as a bridge linking vertex 1 to 5 and the same for all pieces, you will see that the two problems are the same! Just as each piece of domino can only be worn once, each bridge can only be crossed once. Just as every domino piece has to be worn, 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 only has a solution if the graph is connected and has no more than two vertices with odd valency.

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

A very effective solution is to "cut" all numbers that have more than 2 pieces. For example, if you have 4 pieces with the number 5 they saw 2 pieces with 5-1 and two with 5-2. All vertices have to be cut according to the paths that return to the vertex (if not the graph is disconnected). After the cuts the solution is done with a greedy algorithm, since all the numbers appeared only 2 times (except the final ones)! The cuts can be done at once with a special type of lateral search.

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