Tile Puzzle
Time limit8sMemory limit512 MB
On a toroidal N x N grid of 7-state lights, find how many times to press each tile so the all-black board becomes a given pattern.
- Level
Medium7 of 10
- Topics
- Greedy, Math, Matrix, Implementation
- Solved
- No attempts yet
Problem
You are visiting the Ancient and Contemporary Museum. Today there is an exhibition on the history of natural science. You have seen many interesting exhibits about ancient, medieval, and modern science and mathematics, and you are in a resting space now.
You have found a number of panels there. Each of them is equipped with N × N electric tiles arranged in a square grid. Each tile is lit in one of the following colors: black (unlit), red, green, yellow, blue, magenta, and cyan. Initially all the tiles are black. When a tile is pressed once, that tile and the eight adjacent tiles change their colors as follows: black -> red, red -> green, green -> yellow, yellow -> blue, blue -> magenta, magenta -> cyan, and cyan -> black. Here, the leftmost and rightmost columns are considered adjacent, and so are the uppermost and lowermost rows. There is a goal pattern for each panel, and you are to change the colors of the tiles as presented in the goal pattern. For example, if you are given the goal pattern shown in the figure below for a panel of 4 × 4, you will press the upper-left tile once and then press the lower-right tile twice (note that this might not be the only way).
Since you are good at programming, you guess you can find the solution using your computer. So your job in this problem is to write a program for it.
Figure 1: Example Goal Pattern
Input
The input contains a series of datasets. Each dataset is given in the following format:
N
Row1
...
RowN
N is the size (that is, the number of rows and columns) of the electrical panel (3 ≤ N ≤ 15). Rowi describes the goal pattern of the i-th row and contains exactly N numbers separated by a space. The j-th number is the color of the j-th column, and it is one of the following: 0 (black), 1 (red), 2 (green), 3 (yellow), 4 (blue), 5 (magenta), and 6 (cyan).
The input is terminated by a line containing a single zero. This line is not part of any dataset.
Output
For each dataset, your program should produce the output of N lines. The i-th line corresponds to the i-th row and contains exactly N numbers separated by a space, where the j-th number is the number of presses on the tile of the j-th column. The number is in the range from 0 to 6 inclusive.
If there is more than one solution, your program may output any of them. If it is impossible to make the goal pattern, your program should output a single line containing “-1” (without quotes) instead of the N lines.
A blank line should follow the output for every dataset (including the last one).