Dominoes - Competition

Question

http://ecoocs.org/contests/ecoo_2007.pdf

I'm studying for the upcoming ecoo regionals for my area and I'm stumped on this one question. I really have no idea where to start.

It is in the "regional" "west and central" section "problem 3 - domino chains".

I keep going over the problem manually and I keep thinking of breadth first search or depth first search, but the dominoes having two sides is seriously throwing my thinking off. Does anyone have any advice, or maybe some resources that might set me in the right direction?

Answer 1

It looks like this problem calls for a recursive backtracking approach. Keep a 7 by 7 symmetric matrix showing which numbers are attached to which. For example, given tiles 00 12 63 51 you would have the following matrix:

  0 1 2 3 4 5 6 
  -------------
0|1 0 0 0 0 0 0
1|0 0 1 0 0 1 0
2|1 0 0 0 0 0 0
3|0 0 0 0 0 0 1
4|0 0 0 0 0 0 0
5|0 1 0 0 0 0 0
6|0 0 0 1 0 0 0

When you use up a tile by placing it in a potential chain, delete it from the matrix, and put it back in the matrix after you unplace the tile by backtracking. For example, if the chain currecntly contains 51 12, the matrix looks like this:

  0 1 2 3 4 5 6 
  -------------
0|1 0 0 0 0 0 0
1|0 0 0 0 0 0 0
2|0 0 0 0 0 0 0
3|0 0 0 0 0 0 1
4|0 0 0 0 0 0 0
5|0 0 0 0 0 0 0
6|0 0 0 1 0 0 0

Given that the chain currecntly ends in 2, you would look along row 2 for any numbers that can connect to. Not finding any, you would mark down 51 12 as a potential longest chain, and then backtrack to the state where the chain contained only 51.

Maintain a set of all the longest chains you have found, and check a new chain for the existence of itself or its reverse in the set before inserting it.

If you find a longer chain, start a new set. Once you have exhaustively searched through all the possible chains, the size of your set should be the number of variations that are of the longest length.