ACM 989 Su Doku

程式碼99%參考演算法筆記
這題要注意可能測資一開始就會不符合數獨的規則，一開始沒想到，吃了好幾個WA= =
接下來又因為if (!first) printf("\n"); 放錯位置，又再吃了幾個WA= =

#include <stdio.h>

int n, done, board[9][9], row_used[9][10], col_used[9][10], block_used[3][3][10];

void sudoku(int x, int y)
{
    int i, j;

    if (y == n*n) {
        ++x;
        y = 0;
    }

    if (x == n*n) {
        for (i = 0; i < n*n; ++i) {
            printf("%d", board[i][0]);
            for (j = 1; j < n*n; ++j)
                printf(" %d", board[i][j]);
            printf("\n");
        }
        done = 1;
        return;
    }

    if (!done && board[x][y]) {
        sudoku(x, y+1);
        return;
    }

    for (i = 1; !done && i <= n*n; ++i)
        if (!row_used[x][i] && !col_used[y][i]
            && !block_used[x/n][y/n][i]) {
            row_used[x][i] = col_used[y][i]
                           = block_used[x/n][y/n][i] = 1;
            board[x][y] = i;
            sudoku(x, y+1);
            board[x][y] = 0;
            row_used[x][i] = col_used[y][i]
                           = block_used[x/n][y/n][i] = 0;
        }
}

int main(void)
{
    int i, j, k, first, dont_do;

    first = 1;
    while (scanf("%d", &n) == 1) {
        done = dont_do = 0;

        for (i = 0; i < n*n; ++i)
            for (j = 1; j <= n*n; ++j)
                row_used[i][j] = col_used[i][j] = 0;

        for (i = 0; i < n; ++i)
            for (j = 0; j < n; ++j)
                for (k = 1; k <= n*n; ++k)
                    block_used[i][j][k] = 0;

        for (i = 0; i < n*n; ++i)
            for (j = 0; j < n*n; ++j) {
                scanf("%d", &board[i][j]);
                if (board[i][j]
                    && (row_used[i][board[i][j]]
                        || col_used[j][board[i][j]]
                        || block_used[i/n][j/n][board[i][j]]))
                    dont_do = 1;
                row_used[i][board[i][j]] = 1;
                col_used[j][board[i][j]] = 1;
                block_used[i/n][j/n][board[i][j]] = 1;
            }

        if (!first)
            printf("\n");

        if (!dont_do)
            sudoku(0, 0);

        if (!done)
            printf("NO SOLUTION\n");
        first = 0;
    }

    return 0;
}