Su-domino-ku#3108

Su-domino-ku

1 second

64 megabytes

Hard

As if there were not already enough sudoku-like puzzles, the July 2009 issue of Games Magazine describes a variant that combines aspects of both sudoku and dominoes. In a standard sudoku, there is a $9 \times 9$ 9 \times 9 grid that must be filled using only the digits $1$ through $9$ . In a successful solution:

Each row must contain each of the digits $1$ through $9$ .
Each column must contain each of the digits $1$ through $9$ .
Each of the indicated $3 \times 3$ 3 \times 3 squares must contain each of the digits $1$ through $9$ .

For su-domino-ku, nine arbitrary cells are initialized with the numbers $1$ to $9$ . This leaves $72$ remaining cells. These cells must be filled using a set of $36$ domino tiles. The tile set includes one domino for each possible pair of unique numbers from $1$ to $9$ (for example, $1 + 2$ 1+2, $1 + 3$ 1+3, $1 + 4$ 1+4, $1 + 5$ 1+5, $1 + 6$ 1+6, $1 + 7$ 1+7, $1 + 8$ 1+8, $1 + 9$ 1+9, $2 + 3$ 2+3, $2 + 4$ 2+4, $2 + 5$ 2+5, ...). Note that there are not separate $1 + 2$ 1+2 and $2 + 1$ 2+1 dominoes in the set; the single domino can be rotated to provide either orientation. Also, dominoes may cross the boundary of the $3 \times 3$ 3 \times 3 squares (such as the $2 + 9$ 2+9 domino in the sample).

To help, we begin each puzzle by specifying the location of some dominoes. For example, Figure 1 shows a sample puzzle in its initial state. Figure 2 shows the unique solution for that puzzle.

Input

Each puzzle description begins with a line containing an integer $N$ , $10 \leq N \leq 35$ 10 \leq N \leq 35, representing the number of dominoes initially placed. Then $N$ lines follow, each describing a single domino as $U$ $LU$ $V$ $L V$ . Value $U$ is one of the numbers on the domino, and $LU$ is a two-character string representing the location of $U$ on the board, as diagrammed in Figure 1. The variables $V$ and $L V$ represent the respective value and location of the other half of the domino. For example, in the first sample input, the first domino is described as $6$ $B 2$ $1$ $B 3$ . This corresponds to the domino with values $6 + 1$ 6+1 being placed so that $6$ is in row $B$ , column $2$ , and $1$ is in row $B$ , column $3$ . The two locations for any given domino will always be adjacent.

After the specification of the $N$ dominoes, a final line describes the initial locations of the single numbers $1$ to $9$ , using the same row-column convention for describing locations. All initial numbers and dominoes will be at unique positions.

The input ends with a line containing $0$ ; this line is not processed.

Output

For each puzzle, output a line identifying the puzzle number, as shown below. Then output the solution in a $9 \times 9$ 9 \times 9 matrix. There will be a unique solution for each puzzle.

Examples

Example 1