Chambers Ceramic Conundrum

The Chambers Construction Company (CCC) has a contract to install a tile floor on schedule for its biggest customer. Unfortunately, the clerk who ordered the tiles won the lottery just after placing the order and left no notes on how to arrange them. The tiles are not all plain squares — each one is made of 4 unit squares and can take any of the 7 shapes shown below:

XXXX    XX      XX       XX     X       XXX      X
        XX       XX     XX      XXX     X       XXX

Because the schedule is extremely tight, the tiles cannot be reordered. When the 9 tiles arrive you must decide how to place them — or report that no arrangement works. The tiles in the box are labeled A through I, and the room is 6 units on each side (a 6×6 grid), so the 9 tiles must cover it exactly.

Placement algorithm

A manager at CCC has fixed the exact procedure the tiler must follow:

• The tiler always works on the topmost row that still has an empty cell, and within that row on the leftmost empty cell.
• To fill that target cell, the tiler uses the earliest tile in the box (closest to A) that can cover it. A tile is first tried in the orientation shown above; if it does not fit there, it is rotated 90° clockwise and tried again, up to 3 rotations. Tiles may be rotated but never flipped.
• A placed tile may not extend outside the 6×6 room and may not overlap another tile.

For example, if tiles A and B are already placed like this:

AABBBZ
 AA B

then the next tile must be placed so that it fills the cell marked Z (the leftmost empty cell of the topmost row that still has one).

The tiler keeps laying tiles this way until the room is finished or the current layout cannot be completed. At a dead end it backtracks one tile at a time — first trying the remaining rotations of the tile it placed most recently, then the next eligible tile — and continues until a complete tiling is found or every combination has been exhausted. The floor may be tiled if this procedure produces a full covering; otherwise it may not be tiled.

The first line contains the number of data sets, $N$.

Each of the next $N$ lines contains 9 integers describing one data set. The first integer is the shape of tile A, the second the shape of tile B, and so on through tile I. Each integer is between 1 and 7 and selects one of the shapes above, numbered from 1 (leftmost) to 7 (rightmost).

For each data set, first print a line Data Set k, where $k$ is the index of the data set starting from 1.

On the next line print either The floor may be tiled. or The floor may not be tiled..

If the floor can be tiled, print the final 6×6 layout on the following 6 lines. Each cell holds the letter A–I of the tile that covers it (matching that tile's position in the input line), and each line contains exactly 6 characters.

Print a blank line after each data set. After the last data set, print a line reading End of Output.