# ZeroJudge - b053: 4. 數獨遊戲
### 題目連結：https://zerojudge.tw/ShowProblem?problemid=b053
###### tags: `ZeroJudge` `深度優先搜尋（Depth First Search）` `窮舉`

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

int rows[9], columns[9], houses[9], board[9][9], blockSize, boardSize;

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

int main() {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	while (cin >> blockSize) {
		memset(rows, 0, sizeof(rows));
		memset(columns, 0, sizeof(columns));
		memset(houses, 0, sizeof(houses));
		boardSize = blockSize * blockSize;
		for (int i = 0; i < boardSize; ++i)
			for (int j = 0; j < boardSize; ++j)
				if (cin >> board[i][j], board[i][j]) {
					rows[i] |= (1 << board[i][j]);
					columns[j] |= (1 << board[i][j]);
					houses[HOUSE(i, j, blockSize)] |= (1 << board[i][j]);
				}
		if (SolveSudoku(0, -1))
			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";
	}
}