CIT 594 Dominos, a.k.a. Post Correpondence Problem
Spring 2012, David Matuszek

Suppose you have a set of tiles, or "dominos." Each domino has a string in the upper half, and a string in the lower half. Like this:

#1 #2 #3 #4 #5 #6 #7
AD
DA
AB
ABR
RA
AC
 C 
A
RA
A
CA
BCC
AB
BR

You have as many as you need of each kind of domino. Your task is to arrange a sequence of dominos so that the letters on the domino tops spell out the same string as the letters on the domino bottoms.

You must start with domino #2. (Why?)
AB
ABR
         
The next one must be domino #3 or domino #5. (Why?) We'll pick #3.
AB
ABR
RA
AC
       
Now your choices are domino #4 and domino #6. We'll pick #4.
AB
ABR
RA
AC
 C 
A
     
You can continue with domino #1. (Would domino #2 work?)
AB
ABR
RA
AC
 C 
A
AD
DA
   
Now domino #7.
AB
ABR
RA
AC
 C 
A
AD
DA
AB
BR
 
We could choose #3 or #5. We'll pick #5, and we're done. (Why?)
AB
ABR
RA
AC
 C 
A
AD
DA
AB
BR
RA
A

In this example we used dominos #1, #2, #3, #4, #5, and #7 only once each. We could have used any domino as many times as we liked. We didn't use #5. In solving a problem, any domino may be used zero or more times.

Input

Ask the user to choose a file containing input problems. Each problem will consist of one line. The above tiles would be described with the following line:

AD|DA AB|ABR RA|AC C|A RA|A CA|CC AB|BR

Input alphabet will consist of letters only (upper and/or lower case). Single spaces will separate dominos. The top and bottom of dominos will be separated by a vertical bar. It is possible that the top and/or bottom will have no letters, for example, |X.

Process

For each input line, try to produce a solution. If there is more than one solution, any one will do; it doesn't have to be an optimal solution.

Since the general problem is unsolvable, we need to put some artificial limits on it. Your program should be able to solve any problem that has a solution in 12 or fewer dominos. If you are unable to find a solution with 12 or fewer dominos, you can print out that you were unable to find a solution (don't say that there is no solution, unless you are prepared to prove that!)

Please write your program in Python, Java, or Scala.

Output

Print out each problem followed by its solution (or a statement that your program couldn't find a solution.) Print out each solution as two lines. Use one or more spaces between dominos, but print them with the first characters of the top and bottom lined up. Like this:

AB  RA C AD AB RA
ABR AC A DA BR A

The input is to be read by a program, so the program must accept data in exactly the format specified. Output will be checked by a human, so just make sure your output is neat and easily understook.

Due date

Submit your complete program via Blackboard only before 6am Thursday, April 19. Late programs will lose 10%.

No assignments of any kind will be accepted after the last class period.