Dominos problem

An integer N is given, followed by N number of pairs of integers - the pairs represent domino tiles. Each tile can rotate (ie the first number becomes the second and vice versa).

Find such a sequential arrangement of the maximum number of tiles in a row so that for each tile (excluding the first) the first number coincides with the second number of the previous tile. Display the resulting row. If there is more than one row with a maximum length, select any of the options.

So there is no max size for N;
There is nothing said for repetititon so lets say that we can have repetitions;

Example:
Input:
N=5
(1, 2) (2, 10) (7, 10) (1, 5) (4, 11)

Output:
5-1 1-2 2-10 10-7

Do you have any ideas for this problem, is it brute force approach or something else?

DizzyDon (121)

It's never brute force since that would be pointless (no thought required).
In this case the data form an undirected graph.
The answer is the longest path.
Someone will come along and hand you the answer eventually.

seeplus (6591)

Well I'm not an algorithm expert, but here you're looking for the longest path of pairs with adjoining numbers. But if a number can't be paired then that domino can only be used at the start or end of the path - or not used at all. So in the example, (1, 5), (7, 10) and (4, 11) must be either at ends or not used as neither the 5, 7, 4, 11 can be paired with any other. Also neither the 4 nor 11 can be paired so that domino stands alone as a path of 1.

kigar64551 (815)

This could be solved using a "backtracking" algorithm, I think.

Try to extend the path until it is no longer possible to extend it any further (in an allowed way). Where multiple choices are possible, simply pick the first one. And when the path cannot be extended any further (with the still available domino pieces), at the current step, then go back one step and try a different choice at that (previous) step. For each alternative choice, again extend the path as long as possible. If, at a certain step, all choices have been tried, then go back one more step. Once again, try all alternative choices at that step. And so on. If you cannot go back any more, because you already are at the "root", and already tried all choices here, then you are done. Make sure that you record the longest path(s) you were able to build at any point.

This can be implemented as a rather simple recursive function, I believe:
(pseudo-code)

bool solve(const Path &prefix, const std::unordered_set<DominoPiece> &remainingPieces, const size_t n)
{
    if (prefix.length() >= n)
    {
        return true;
    }
    for (const auto &piece: remainingPieces)
    {
        if (piece.can_extend(prefix))
        {
            if (solve(prefix.append(piece, without(remainingPieces, piece), n))
            {
                return true;
            }
        }
        const pieceTurned = piece.turn();
        if (pieceTurned.can_extend(prefix))
        {
            if solve(prefix.append(pieceTurned, without(remainingPieces, piece), n))
            {
                return true;
            }
        }
    }
    return false;
}

int main(void)
{
    std::unordered_set<DominoPiece> pieces
    {
        Piece(1, 2),
        Piece(2, 10),
        /* ... */
    };
    solve(Path.EMPTY, pieces, pieces.size());
}

Edit: In fact, you can also stop the search as soon as you found a path of maximum possible length, because the task only requires you to find one such path, not all of them.

Last edited on

jonnin (11437)

I agree, but you may also be able to craft a metric to choose the first tile. IMHO the first tile governs the solution. It is also recursive to an extent -- if you pick a starting value (again, the starting tile) then each tile is the same problem going forward with 1 less tile to pick from.
recursion can be used to backtrack or side track -- like like a BST, you just call again for each candidate (so if you have 5 tiles with a 3 on them and are matching a previous 3, then you have 5 calls, and after they all resolve you pick the best one of those).

but how to pick the best first tile? I am not convinced its a value with an odd # of instances as that could also be the optimal last tile or you may even do better throwing that tile away. Hmm. I am coming up short on it .. but just like the TSP, solving it quickly depends on picking the first node correctly... thoughts?

ne555 (10692)

> IMHO the first tile governs the solution
i'm not so sure
if the optimal solution is in a cycle, it doesn't matter the starting point
If it's not a cycle, then once you reach a dead end, may simply add tiles to the start.

jonnin (11437)

heh.. adding tiles to the start is changing the starting point, though.
but I see what you mean, you can fix it if you picked the wrong one.

Topic archived. No new replies allowed.