poj 2676 Sudoku dfs 深搜

题目描述: http://poj.org/problem?id=2676

转自: http://zhangjian110518.blog.163.com/blog/static/74991703200933092722785/

题目技巧性不强，DFS过的，用时16MS。不过写的过程中要注意从后面往前搜。

/************************************************************************/
/*思路：
先从后面开始搜，也就是从第八十个开始搜
1、如果一个小的方格内已经包含了非零的数，则继续向下搜
2、如果一个小的方格内是一个零数，也就是还没有放入相应的数，则对其从零到九开始尝试
3、对每一个数的尝试，检查其合法性：在其所在的3*3方格内是否合适；在此行是否合适：在此列是否合适
4、如果经过以上条件可以的话那么这个数字就可以放在此小方格上，然后继续进行搜索。
************************************************************************/

#include <cstdio>

const int n = 9;
int board[9][9];
char ch[10];

//返回当前board[x][y]中的值是否可行
bool ok(int x, int y) {
    // 3 * 3
    for (int i = x / 3 * 3; i < x / 3 * 3 + 3; ++i) {
        for (int j = y / 3 * 3; j < y / 3 * 3 + 3; ++j) {
            if (x == i && y == j)
                continue;
            if (board[x][y] == board[i][j])        // the number has been used
                return false;
        }
    }
    int temp = board[x][y];
    // check the row
    for (int j = 0; j < n; ++j) {
        if (j == y)
            continue;
        if (board[x][j] == temp)
            return false;
    }
    // check the column
    for (int i = 0; i < n; ++i) {
        if (i == x)
            continue;
        if (board[i][y] == temp)
            return false;
    }
    return true;        // ok
}


int dfs(int location) {
    if (location == -1)
        return 1;

    if (board[location / n][location % n] != 0)        // has number
        return dfs(location - 1);
    else {
        for (int i = 1; i <= n; ++i) {      // try
            board[location / n][location % n] = i;
            if (ok(location / n, location % n)) {
                if (dfs(location - 1))
                    return 1;
            }
            board[location / n][location % n] = 0;
        }
    }
    return 0;
}

int main() {
    int nCases;
    scanf("%d", &nCases);
    while (nCases--) {
        for (int i = 0; i < n; ++i) {
            scanf("%s", ch);
            for (int j = 0; j < n; ++j) {
                board[i][j] = ch[j] - '0';
            }
        }

        dfs(80);

        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                printf("%d", board[i][j]);
            }
            printf("\n");
        }
    }

    return 0;
}