用C++实现数独解法
Description（如果嫌烦可以忽略描述，说白了就是解数独）
Input
Output
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; }
原文：https://www.cnblogs.com/yyyxu/p/14612308.html