Czech ACM Student Chapter
Czech Technical University in Prague
Charles University in Prague
Technical University of Ostrava
Slovak University of Technology
Pavol Jozef Saf´rik University in Koˇice
University of Zilina
Matej Bel University in Bansk´ Bystrica
University of West Bohemia
CTU Open Contest 2011
tiling.c, tiling.C, tiling.java, tiling.p
The aliens want to dominate the whole universe. So it comes as no surprise that their favorite
game is played with domino tiles. A domino tile is a tile of size 1 × 2 with a digit 0-9 written on
each half. Their game board is a rectangular array with a digit 0-9 written in each unit square.
The task is to cover the whole board with the set of provided domino tiles. The tiles can be
placed only if the two numbers on the tile equal the two numbers in the unit squares covered
by the tile. The tiles can be placed as they are or may be rotated by 90◦, 180◦ or 270◦ . No two
tiles may overlap. You can always use only one piece of each provided tile.
Some tiles are already placed on the board. These must stay where they are.
You are to write a program that will play this game. If you do not succeed, our planet will be
The input contains several descriptions of game settings. The first line of each description
contains three numbers separated by one or more spaces. The first two numbers are the height
M and the width N of the board. They satisfy 1 ≤ M ≤ 20, 1 ≤ N ≤ 20, at least one of them
is even, and their product 2 ≤ M · N ≤ 110 (guess why). The last number is the number of
available tiles K , 1 ≤ K ≤ M · N/2.
The next line contains K pairs of space-separated integers describing the pairs of numbers on
the available tiles. Each two consecutive numbers on this line are separated by at least one
space. In addition, no two tiles are identical, that is, they are different (and stay different even
if one is rotated by 180◦ ). The tiles already placed on the board are not among these K tiles.
The following M lines contain N space-separated entries each. For every i, j, 0 ≤ i < M, 0 ≤
j < N , the jth entry in the ith row describes the place in the ith row and jth column of
the gameboard. The entry is either the capital letter "X" if there is an already-placed tile, or
a number Ai,j (0 ≤ Ai,j ≤ 9) written on the board.
Every description is followed by an empty line and the empty line after the last description is
followed by a line containing three zeros.
For each game, find a way to place all tiles onto the board. If there are more solutions, output
any of them. Provide the solution by a graphic representation as an M × N array with "[" and
"]" (square brackets) standing for the left and right half of a horizontally placed domino, and
lowercase letters "n" and "u" for the upper and lower half of a vertically placed domino. The
squares covered by a tile in the input are still represented by "X". After the M rows, print one
line containing the number of other different solutions that exist.
Do not output any spaces and start a new line for each row of the gameboard.
If there is no solution, write a single line with the word "impossible".
Print one empty line after the each gameboard result.
Output for Sample Input