Dominoes matching algorithm

Given some inputs, which consist of a left and right symbol, output chains which link the inputs.

Imagine the inputs to be dominoes which you cannot flip horizontally and need to chain them together. Creating big circular chains (ignore if you cannot physically do it with real dominos) is preferred over small circular chains which are preferred over chains where the start and end does not match.

Outputs with more circular chains (regardless of how many or chain length) are what we are looking for. For example, an output of 3 circular chains is better than 1 big chain and a leftover single domino.

Can someone point me in the right direction? What group of problems does this belong and are there existing algorithms for solving this?

Examples (outputs may be incorrect!):

in[0]=(A,B)
in[1]=(B,C)
in[2]=(C,A)
out[0]=(0,1,2)

in[0]=(A,B)
in[1]=(B,A)
in[2]=(C,D)
in[3]=(D,C)
out[0]=(0,1)
out[1]=(2,3)

in[0]=(A,B)
in[1]=(B,A)
in[2]=(C,D)
in[3]=(E,F)
out[0]=(0,1)
out[1]=(2)
out[2]=(3)

in[0]=(A,B)
in[1]=(B,A)
in[2]=(C,D)
in[3]=(D,E)开发者_开发知识库
out[0]=(0,1)
out[1]=(2,3)

in[0]=(A,B)
in[1]=(B,C)
in[2]=(C,D)
out[0]=(0,1,2)

---

Dominoes which cannot be flipped horizontally == directed graphs.

Putting dominoes one after the other is called a "path", if it is a closed path, it's a circuit.

A circuit that includes all the vertices of a graph is a Hamiltonian circuit.

Your problem in graph theory terms is: how to split (decompose) your graph into a minimum number of subgraphs that have Hamiltonian circuits. (a.k.a. Hamiltonian graphs)

---

The problem as it is now is not as clearly stated as it could be - how exactly are solutions rated? What is the most important criterion? Is it the length of the longest chain? Is there a penalty for creating chains of length one?

It is often helpful in such problems to visualize the structure as a graph - say, assign a vertex (V[i]) to each tile. Then for each i, j create an edge between vertices V[i], V[j] if you can place V[i] to the left of V[j] in a chain (so if V[i] corresponds to (X, A) then V[j] corresponds to (A, Y) for some X, Y, A).

In such a graph chains are paths, cycles are closed ("circular") chains and the problem has been reduced to finding some cycle and/or path covering for a graph. This type of problems can in turn often be reduced to matching or *-flow problems (max-flow, max-cost-max-flow, min-cost-max-flow or what have you).

But before you can reduce further you have to establish the precise rules according to which one solution is determined to be "better" than another.

---

It is easy to check whether there exists a circular chain consisting of all dominoes. First you need to make the following directed graph G:

• Nodes of G are symbols on the dominoes (A,B,C..) in your example,
• For each domino (A,B) you put a directed edge from A to B.

There exists a circular chain consisting of all dominoes iff there exists a Eulerian cycle in G. To check whether there exists Eulerian cycle in G it is sufficient to check weather each node has even degree.

---

I'm not sure if this is really the case, but judging by your examples, your problem looks similar to the problem of decomposing a permutation into a product of disjoint cycles. Each tile (X,Y) can be seen as P(X) = Y for a permutation P. If this agrees with your assumptions, the good (or bad) news is that such decomposition is unique (up to the cycle order) and is very easy to find. Basically, you start with any tile, find a matching tile on the other hand and follow this until no matching can be found. Then you move to the next untouched point. If that's not what you are looking for, the more general graph-based solution by t.dubrownik looks like the way to go.