用C++实现数独解法

Description（如果嫌烦可以忽略描述，说白了就是解数独）

Sudoku is a very simple task. A square table with 9 rows and 9 columns is divided to 9 smaller squares 3x3 as shown on the Figure. In some of the cells are written decimal digits from 1 to 9. The other cells are empty. The goal is to fill the empty cells with decimal digits from 1 to 9, one digit per cell, in such way that in each row, in each column and in each marked 3x3 subsquare, all the digits from 1 to 9 to appear. Write a program to solve a given Sudoku-task.

Input

The input data will start with the number of the test cases. For each test case, 9 lines follow, corresponding to the rows of the table. On each line a string of exactly 9 decimal digits is given, corresponding to the cells in this line. If a cell is empty it is represented by 0.

Output

For each test case your program should print the solution in the same format as the input data. The empty cells have to be filled according to the rules. If solutions is not unique, then the program may print any one of them.

Sample Input

1
103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

Sample Output

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

思路
解数独这道题相当于是DFS部分八皇后问题的进一步扩展。
八皇后问题是要求两个皇后不能出现在同一行或同一列或者同一对角线上。
数独要求两个相同的数不能出现在同一行或同一列或者同一个子3*3方框里。
因此思路是大致一样的：
　　1.从第一行第一列开始，如果当前元素非零（已经给定），则递归到下一个元素（第一行第二列）。
　　2.如果当前元素是零，则从1到9枚举能填的数，并且检测是否合适。如果合适，则递归下一个元素。一直到最后一个元素（第九行第九列）。
　　3.需要注意的是如果递归到了一行的末尾，则下一个元素是下一行第一个。
　　4.递归结束条件是递归到了第10行第一个元素，这时候打印输出即可。
此外，我们需要对递归的过程进行剪枝处理，否则会超时。因为当找到一种正确解法后，任务就已经结束了，不需要再去找其他可能了，所以可以定义一个bool型变量
done来标识是否已经找到解，如果找到则return。

代码

#include <iostream>
using namespace std;
bool done;//用于剪枝 当得到一个正确答案后直接程序结束 不再继续寻找
int map[9][9];
//方便调试的代码
void show() {
    cout << "     "<<"123456789" << endl;
    cout << endl;
    for (int i = 0; i < 9; i++) {
        cout << i + 1 << "    ";
        for (int j = 0; j < 9; j++) {
            cout << map[i][j];
        }
        cout << endl;
    }
    cout << endl;
    cout << "--------------------------" << endl;
}
//用于提交的代码
//void show() {
//    for (int i = 0; i < 9; i++) {
//        for (int j = 0; j < 9; j++) {
//            cout << map[i][j];
//        }
//        cout << endl;
//    }
//}

//判断第r行第c列是否可以填入n
bool check(int r, int c, int n) {
    //判断行列
    for (int i = 0; i < 9; i++) {
        if (map[r][i] == n || map[i][c] == n) {
            return false;
        }
    }
    //判断3*3
    int startR = r / 3;
    int startC = c / 3;
    int endR = startR * 3 + 3;
    int endC = startC * 3 + 3;
    for (int i = startR * 3; i < endR; i++) {
        for (int j = startC * 3; j < endC; j++) {
            if (n == map[i][j]) {
                return false;
            }
        }
    }
    return true;
}

void dfs(int row, int col) {
    //递归到了第10行，结束
    if (row == 9) {
        done = true;
        show();
        return;
    }
    //剪枝
    if (done)    return;
    if (map[row][col]) {
        if (col == 8) {
            dfs(row + 1, 0);
        }
        else {
            dfs(row, col + 1);
        }
    }
    else {
        //枚举当前位置能填入的数字
        for (int i = 1; i <= 9; i++) {
            if (check(row, col, i)) {
                map[row][col] = i;
                //如果合适则递归下一个元素
                if (col == 8) {
                    dfs(row + 1, 0);
                }
                else {
                    dfs(row, col + 1);
                }
                map[row][col] = 0;
            }
        }
        
    }
}

int main() {
    int n;
    char str;
    while (cin >> n) {
        while (n--) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    cin >> str;
                    map[i][j] = str - '0';
                }    
            }
            done = false;
            dfs(0, 0);
        }
    }
    return 0;
}