# ZeroJudge - d263: 00989 - Su Doku
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=d263
###### tags: `ZeroJudge` `深度優先搜尋（Depth First Search）` `窮舉`

#include <iostream>
#include <cstring>
using namespace std;
#define BLOCK(row, column, blockSize) ((row / blockSize) * blockSize + (column / blockSize))

bool isLegel, haveSolution;
int caseCount, rows[9], columns[9], blocks[9], board[9][9], boardSize, blockSize;

bool SolveSudoku(int nowRow, int nowColumn) {
	do {
		++nowColumn;
		if (nowColumn == boardSize)
			++nowRow, nowColumn = 0;
		if (nowRow == boardSize) {
			haveSolution = true;
			return true;
		}
	} while (board[nowRow][nowColumn]);
	for (int i = 1; i <= boardSize; ++i) {
		if ((rows[nowRow] & (1 << i)) || (columns[nowColumn] & (1 << i)) || (blocks[BLOCK(nowRow, nowColumn, blockSize)] & (1 << i)))
			continue;
		board[nowRow][nowColumn] = i;
		rows[nowRow] |= (1 << i);
		columns[nowColumn] |= (1 << i);
		blocks[BLOCK(nowRow, nowColumn, blockSize)] |= (1 << i);
		if (SolveSudoku(nowRow, nowColumn))
			return true;
		board[nowRow][nowColumn] = 0;
		rows[nowRow] ^= (1 << i);
		columns[nowColumn] ^= (1 << i);
		blocks[BLOCK(nowRow, nowColumn, blockSize)] ^= (1 << i);
	}
	return false;
}

int main() {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	while (cin >> blockSize) {
		if (caseCount)
			cout << '\n';
		++caseCount;
		memset(rows, 0, sizeof(rows));
		memset(blocks, 0, sizeof(blocks));
		memset(columns, 0, sizeof(columns));
		boardSize = blockSize * blockSize;
		haveSolution = false;
		isLegel = true;
		for (int i = 0; i < boardSize; ++i)
			for (int j = 0; j < boardSize; ++j)
				if (cin >> board[i][j], board[i][j]) {
					if ((rows[i] & (1 << board[i][j])) || (columns[j] & (1 << board[i][j])) || (blocks[BLOCK(i, j, blockSize)] & (1 << board[i][j])))
						isLegel = false;
					rows[i] |= (1 << board[i][j]);
					columns[j] |= (1 << board[i][j]);
					blocks[BLOCK(i, j, blockSize)] |= (1 << board[i][j]);
				}		
		if (isLegel)
			SolveSudoku(0, -1);
		if (haveSolution)
			for (int i = 0; i < boardSize; ++i) {
				for (int j = 0; j < boardSize; ++j) {
					if (j)
						cout << ' ';
					cout << board[i][j];
				}
				cout << "\n";
			}
		else
			cout << "NO SOLUTION\n";
	}
}