In many newspapers we may find some puzzles to solve, one of those is Su Doku. Given a grid 9 × 9 with some of entries filled, the objective is to fill in the grid so that every row, every column, and every 3 × 3 box contains the digits 1 through 9. source: http://www.sudoku.com Input Input contains several test cases separated by a blank line. Each of them contains an integer n such that 1 ≤ n ≤ 3 and a grid n2 ×n2 with some of the entries filled with digits from 1 to n2 (an entrie not filled will have 0). In this case, the objective is to fill in the grid so that every row, every column, and every n × n box contains the digits 1 through n2. Output A solution for the problem. If exists more than one, you should give the lower one assuming a lexico- graphic order. If there is no solution, you should print ‘NO SOLUTION’. For lexicographic comparison you should consider lines in first place. Print a blank line between test cases. Sample Input 3 060104050 008305600 200000001 800407006 006000300 700901004 500000002 007206900 040508070
2/2 Sample Output 963174258 178325649 254689731 821437596 496852317 735961824 589713462 317246985 642598173