[UVa] 989 Su Doku.cpp

#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;
}