UVa 989 Su Doku

想法：

    每次要填入一個數字時，確認該行與該列和該九宮格(box)裡面是否已經有這個數字，如果能填入，則繼續遞迴下去填下一格。

	#include <cstdio>
	using namespace std;
	int board[9][9];
	int n, N; // n是較小的邊長, N = n * n
	bool backtracking(int r, int c);
	int main()
	{
	int Case = 0;
	while (scanf("%d", &n) != EOF) {
	if (Case++) putchar('\n');
	N = n * n;
	for (int i = 0; i < N; ++i)
	for (int j = 0; j < N; ++j)
	scanf("%d", &board[i][j]);
	if (backtracking(0, 0)) {
	for (int i = 0; i < N; ++i) {
	for (int j = 0; j < N - 1; ++j)
	printf("%d ", board[i][j]);
	printf("%d\n", board[i][N-1]);
	}
	}
	else puts("NO SOLUTION");
	}
	}
	bool backtracking(int r, int c)
	{
	if (r >= N)
	return true;
	if (board[r][c] == 0) {
	bool col[10] = {0};
	bool row[10] = {0};
	bool box[10] = {0};
	//找出該欄與該列已經填過哪些數字
	for (int i = 0; i < N; ++i) {
	if (board[r][i]) row[board[r][i]] = 1;
	if (board[i][c]) col[board[i][c]] = 1;
	}
	//找出所在位置的九宮格裡已經填過哪些數字
	int rr = r - (r % n);
	int cc = c - (c % n);
	for (int i = 0; i < n; ++i)
	for (int j = 0; j < n; ++j)
	if (board[rr+i][cc+j]) box[board[rr+i][cc+j]] = 1;
	//確認1~9哪些數字能填在這格,如果能填則繼續遞迴
	for (int num = 1; num <= 9; ++num) {
	if (!col[num] && !row[num] && !box[num]) {
	board[r][c] = num;
	int nxt_r = r, nxt_c = c + 1;
	if (nxt_c == N) ++nxt_r, nxt_c = 0; //換行
	bool hasAns = backtracking(nxt_r, nxt_c);
	if (hasAns) return true;
	board[r][c] = 0;
	}
	}
	}
	else { // board[r][c] != 0
	int nxt_r = r, nxt_c = c + 1;
	if (nxt_c == N) ++nxt_r, nxt_c = 0;
	bool hasAns = backtracking(nxt_r, nxt_c);
	if (hasAns) return true;
	}
	return false;
	}

view raw [UVa] 989 Su Doku.cpp hosted with ❤ by GitHub