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

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

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

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

int main() {
	cin.sync_with_stdio(false); cin.tie(nullptr);
	while (cin >> board[0][0]) {
		for (int i = 1; i < 9; ++i)
			cin >> board[0][i];
		for (int i = 1; i < 9; ++i)
			for (int j = 0; j < 9; ++j)
				cin >> board[i][j];
		haveSolution = haveMore = false;
		isLegel = true;
		++caseCount;
		memset(rows, 0, sizeof(rows));
		memset(blocks, 0, sizeof(blocks));
		memset(columns, 0, sizeof(columns));
		for (int i = 0; i < 9; ++i)
			for (int j = 0; j < 9; ++j)
				if (board[i][j]) {
					if ((rows[i] & (1 << board[i][j])) || (columns[j] & (1 << board[i][j])) || (blocks[BLOCK(i, j)] & (1 << board[i][j]))) {
						isLegel = false;
						break;
					}
					rows[i] |= (1 << board[i][j]);
					columns[j] |= (1 << board[i][j]);
					blocks[BLOCK(i, j)] |= (1 << board[i][j]);
				}
		if (isLegel)
			SolveSudoku(0, -1);
		cout << "Case " << caseCount << ": " << (isLegel ? (haveSolution ? (haveMore ? "Ambiguous" : "Unique") : "Impossible") : "Illegal") << ".\n";
	}
}