Write a program to solve a Hitori puzzle, if possible. Hitori is played on a square grid of cells, each occupied by a number. The objective is to clear some cells so that there are no duplicate numbers in any row or column. Any two cleared cells may not be horizontally or vertically adjacent to each other. All occupied cells must be horizontally or vertically connected together into a single group; i.e., the cleared cells cannot divide the occupied cells into unconnected sets.
Input
There are multiple test cases for this problem.
The grid is specified by a single line containing two positive integers n and m separated by white space. Each of the next n lines contains n numbers in the range from 1 to m, separated by white space, which occupy the grid. Neither n nor m will exceed 25.
Output
The output should be "No solution" if no solution exists, or it should be in the same format as the input, where a cleared cell contains a single period and each occupied cell still contains the original number. An output line need not preserve the spacing of the corresponding input line. Note that there can be multiple solutions; your program should output only one.
Sample Input
8 10
4 10 1 6 3 2 5 7
3 6 7 2 1 6 5 4
2 3 4 10 2 10 6 1
4 1 6 5 7 7 3 5
7 2 3 1 10 5 1 2
3 5 6 7 3 1 10 4
6 4 2 3 5 4 7 10
10 7 1 4 2 3 5 6
Sample Output
8 10
. 10 . 6 3 2 . 7
3 6 7 2 1 . 5 4
. 3 4 . 2 10 6 1
4 1 . 5 7 . 3 .
7 . 3 . 10 5 1 2
. 5 6 7 . 1 10 .
6 . 2 3 5 4 7 10
10 7 1 4 . 3 . 6