Su Doku

Problem

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 n²×n² with some of the entries filled with digits from 1 to n² (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 n².

Output

A solution for the problem. If exists more than one, you should give the lower one assuming a lexicographic 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
0 6 0 1 0 4 0 5 0
0 0 8 3 0 5 6 0 0
2 0 0 0 0 0 0 0 1
8 0 0 4 0 7 0 0 6
0 0 6 0 0 0 3 0 0
7 0 0 9 0 1 0 0 4
5 0 0 0 0 0 0 0 2
0 0 7 2 0 6 9 0 0
0 4 0 5 0 8 0 7 0

Sample output

9 6 3 1 7 4 2 5 8
1 7 8 3 2 5 6 4 9
2 5 4 6 8 9 7 3 1
8 2 1 4 3 7 5 9 6
4 9 6 8 5 2 3 1 7
7 3 5 9 6 1 8 2 4
5 8 9 7 1 3 4 6 2
3 1 7 2 4 6 9 8 5
6 4 2 5 9 8 1 7 3

#include <stdio.h>
#include <string.h>
int SuDoku[9][9], row[9][10], column[9][10], grid[9][10];
int n, tn, flag;
void DFS(int now) {
    if(flag == 1)
        return ;
    if(now == n*n) {
        int i, j;
        flag = 1;
        for(i = 0; i < n; i++) {
            for(j = 0; j < n; j++) {
                if(j)
                    printf(" ");
                printf("%d", SuDoku[i][j]);
            }
            puts("");
        }
    }
    int x = now/n, y = now%n;
    if(SuDoku[x][y] != 0)
        DFS(now+1);
    else {
        int i, g = x/tn*tn+y/tn;
        for(i = 1; i <= n; i++) {
            if(row[x][i] == 0 && column[y][i] == 0 && grid[g][i] == 0) {
                row[x][i] = 1;
                column[y][i] = 1;
                grid[g][i] = 1;
                SuDoku[x][y] = i;
                DFS(now+1);
                SuDoku[x][y] = 0;
                row[x][i] = 0;
                column[y][i] = 0;
                grid[g][i] = 0;
            }
        }
    }
}
int main() {
    int first = 1, i, j;
    while(scanf("%d", &n) == 1) {
        tn = n;
        n = n*n;
        memset(row, 0, sizeof(row));
        memset(column, 0, sizeof(column));
        memset(grid, 0, sizeof(grid));
        for(i = 0; i < n; i++) {
            for(j = 0; j < n; j++) {
                scanf("%d", &SuDoku[i][j]);
                row[i][SuDoku[i][j]] = 1;
                column[j][SuDoku[i][j]] = 1;
                grid[i/tn*tn+j/tn][SuDoku[i][j]] = 1;
            }
        }
        if(!first)
            puts("");
        flag = 0;
        DFS(0);
        if(!flag)
            puts("NO SOLUTION");
        first = 0;
    }
    return 0;
}