文章目录

• • 6. 四皇后问题
  • 7. 求解四宫格数独
  • 8. 求解九宫格数独
  • • 进一步优化

6. 四皇后问题

【描述】在一个 4x4 棋盘例摆放 4 个皇后，要求任意两个皇后不能在同一行、同一列和同一斜线（平行于对角线上），请输出所有的摆法。

【限制条件实现】摆放皇后的位置（i，j）需要满足：

• 第 i 行没有其他位置被占用；
• 第 j 列没有其他位置被占用；
• 两个斜对角线上没有其他位置被占用，通过找规律可以得出具体是哪些位置没有被占用：
  • 对于左下到右上的斜对角线，满足行列坐标和相等（即 i+j 相同）的其他位置没有被占用（对于 4x4 棋盘 i+j 可以取得的值为 2,3,4,5,6,7,8，如下表所示）；
  • 对于左上到右下的斜对角线，满足行列坐标差相等（即 i-j 相同）的其他位置没有被占用（对于 4x4 棋盘 i-j 可以取得的值为 -3,-2,-1,0,1,2,3，如下表所示）。

所以开辟四个数组用来记录占位情况：

• isRow，记录每一行是否被占用；
• isCol，记录每一列是否被占用；
• isBia1，记录每一右上斜线是否被占用，注意 i+j 作为下标会大于 4，因此把该数组的空间开辟大一些；
• isBia2，记录每一右下斜线是否被占用，注意 i-j 作为下标会出现负值，从而越界，因此不仅要把该数组的空间开辟大一些，而且还要将 i-j 加上一个偏移量使之变为正值。

【算法求解过程】下面来分析回溯算法的求解过程。

• 第一个皇后先尝试摆放在（1,1）处，由于没有其他皇后与（1,1）处于同行、同列、同对角线，因此这个位置被认为是合法的。

• 接下来开始扩展第二层结点，第二个皇后尝试摆放到（2,1）、（2,2）处，但均与第一个皇后冲突，直到尝试到（2,3）时被认为是合法的。

• 接下来开始扩展第三层结点，第三个皇后尝试摆放到（3,1）、（3,2）、（3,3）、（3,4）之后，发现已经没有合法的位置了，也就是说，在当前第二层状态下，已经无法扩展出第三层了。

• 此时就开始回溯，返回到第二层结点，尝试第二层的下一个合法分枝。找到的合法分支是（2,4），在此基础上再扩展第三层。第三层首先找到的合法位置是（3,2）。

• 试图扩展第四层时，第四层已经没有合法位置，于是又要回溯。回溯到第三层，第三层没有余下的合法位置；再回溯到第二层，仍然没有余下的合法位置；回溯到第一层，第一层找到的下一个合法位置是（1,2）。

• 按照同样的规则，逐层向下扩展，在无法扩展时就向上一层回溯，直到扩展到最后一层时，便求得了问题的一个解。

【简要算法描述】

// 在第row行开始放棋子
void trace (row){if (row == 5)输出方案;else{尝试在第row行每一列放棋子if (该行该列该对角线没有被占用){在第row行第col列放棋子;该行该列该对角线 = 占用;trace(row+1);  // 开始放下一行棋子在第row行第col列撤回棋子;该行该列该对角线 = 未占用;}}
}

【题解】

#include 
using namespace std;#define MAX 4
int A[MAX+1][MAX+1] = {0};
bool isRow[MAX+1] = {false};  // 记录每一行是否被占用 
bool isCol[MAX+1] = {false};  // 记录每一列是否被占用 
bool isBia1[2 * MAX + 1] = {false}; // 记录每一右上斜线是否被占用 
bool isBia2[2 * MAX + 1] = {false}; // 记录每一右下斜线是否被占用 void trace (int row){static int cnt = 0;if (row > MAX){  // 如果 4 个棋子都摆放完毕，输出方案 cnt++;printf("方案%d：\n", cnt);for (int i = 1; i <= MAX; i++){for (int j = 1; j <= MAX; j++)printf("%d ", A[i][j]);printf("\n");}printf("\n");}else{for (int col = 1; col <= MAX; col++){  // 每一列都试着摆放一下 if (!isRow[row] && !isCol[col] && !isBia1[row+col] && !isBia2[MAX+row-col]){  // 如果行列及对角线都没有被占用 A[row][col] = 1;  // 摆放旗子，各标志位占位 isRow[row] = true; isCol[col] = true;isBia1[row+col] = true;isBia2[MAX+row-col] = true;trace(row + 1);  // 到下一行摆放下一个棋子 A[row][col] = 0; // 撤回棋子，各标志位复位isRow[row] = false;isCol[col] = false;isBia1[row+col] = false;isBia2[MAX+row-col] = false;}}}
}int main(){trace(1);  // 从第一行开始摆放棋子 return 0;
}

【输出结果】四皇后问题一共只有两种解。八皇后问题一共有 92 种解法。

方案1：
0 1 0 0
0 0 0 1
1 0 0 0
0 0 1 0方案2：
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0

实际上，把判断每一行是否占位的isRow去掉也是可以的，想一想这是为什么。

7. 求解四宫格数独

【四宫格数独规则】四宫格数独由4行4列共16个小格子构成。

分别在格子中填入1到4的数字，并满足下面的条件：

• 每一行都用到1,2,3,4
• 每一列都用到1,2,3,4
• 每2×2的格子都用到1,2,3,4

【输入与输出样例】注意，一道题可能有多个解！

题目：
0 0 0 0
0 0 2 0
0 3 0 1
0 0 0 0答案1：
3 2 1 4
1 4 2 3
2 3 4 1
4 1 3 2答案2：
3 2 1 4
4 1 2 3
2 3 4 1
1 4 3 2答案3：
4 2 1 3
3 1 2 4
2 3 4 1
1 4 3 2

【分析】本题比四皇后问题还要更复杂一些。

四皇后问题是每一行只放一个皇后，每放一行就生成整棵搜索树上的一个结点，在往下一个行放皇后时，这个结点又会生成最多四个结点。每行放一个皇后，不考虑限制的话，那么 4x4 棋盘最多有 4⁴=64 种可能的放法。

但是数独就不一样了，每个格子填一个数字就生成整棵搜索树上的一个结点，在往下一个格子填数字时，这个结点又会生成最多四个结点。注意四皇后只有 4 行，而数独可是有 16 个格子，因此解数独的树形结构要比四皇后问题更宽更深。对于一个全空白的四宫格数独，不考虑各种限制的话，16 个格子就有 4¹⁶ 种可能的填法。

我们不妨来看一下四宫格数独在使用回溯算法时的求解过程。每个数独上面的两个数字表示填数位置。

题目：
0 0 0 0
1 0 2 0
0 4 0 1
0 0 0 00 0 // 在(0,0)处填数字
2 0 0 0
1 0 2 0
0 4 0 1
0 0 0 00 1
2 3 0 0
1 0 2 0
0 4 0 1
0 0 0 00 2
2 3 1 0
1 0 2 0
0 4 0 1
0 0 0 00 3
2 3 1 4
1 0 2 0
0 4 0 1
0 0 0 00 2
2 3 4 0
1 0 2 0
0 4 0 1
0 0 0 00 0 // 发现(0,3)已经填不了数字了，于是回溯至(0,0)
3 0 0 0
1 0 2 0
0 4 0 1
0 0 0 00 1
3 2 0 0
1 0 2 0
0 4 0 1
0 0 0 00 2
3 2 1 0
1 0 2 0
0 4 0 1
0 0 0 00 3
3 2 1 4
1 0 2 0
0 4 0 1
0 0 0 00 2
3 2 4 0
1 0 2 0
0 4 0 1
0 0 0 00 0
4 0 0 0
1 0 2 0
0 4 0 1
0 0 0 00 1
4 2 0 0
1 0 2 0
0 4 0 1
0 0 0 00 2
4 2 1 0
1 0 2 0
0 4 0 1
0 0 0 00 3
4 2 1 3
1 0 2 0
0 4 0 1
0 0 0 01 1
4 2 1 3
1 3 2 0
0 4 0 1
0 0 0 01 3
4 2 1 3
1 3 2 4
0 4 0 1
0 0 0 02 0
4 2 1 3
1 3 2 4
2 4 0 1
0 0 0 02 2
4 2 1 3
1 3 2 4
2 4 3 1
0 0 0 03 0
4 2 1 3
1 3 2 4
2 4 3 1
3 0 0 03 1
4 2 1 3
1 3 2 4
2 4 3 1
3 1 0 03 2
4 2 1 3
1 3 2 4
2 4 3 1
3 1 4 03 3  // 此处得到了答案，开始下一次的尝试
4 2 1 3
1 3 2 4
2 4 3 1
3 1 4 22 0
4 2 1 3
1 3 2 4
3 4 0 1
0 0 0 00 2
4 2 3 0
1 0 2 0
0 4 0 1
0 0 0 00 1
4 3 0 0
1 0 2 0
0 4 0 1
0 0 0 00 2 // 运行到此处，已经没有别的答案了
4 3 1 0
1 0 2 0
0 4 0 1
0 0 0 0

好在，本题已有各种限制，并且已经有一些填好的数字了，我们先不妨按照以上思路去解答本题，即一个一个格子地填数字。

【回溯算法描述】

// 在第row行第col列开始填数字
void solve (row, col){if (row,col 超出了范围)重新调整到下一行，即row+1，col=0;if ((row,col) == (5,0))输出方案;else{if (第row行第col列 == 0){  // 第row行第col列没有填数字尝试在第row行第col列填数字1~4if (该数字与其他数字没有冲突){第row行第col列 = 数字;标记占位标志;solve(row, col+1);  // 往下一个格子填数字第row行第col列 = 0;复位占位标志;}}else{solve(row, col+1);  // 第row行第col列已经填了数字，往下一个格子填数字}}
}

【限制条件的实现】为节省空间开销，使用 C++ 里的 bitset 库，采用哈希表的思路，即第 num 位记录数字 num 的存在情况。这样，我们可以定义三个 bitset 数组：

• bitset <5> rowBit[4]：记录每一行每个数字的存在情况，1 表示存在，0 表示不存在。
• bitset <5> colBit[4]：记录每一列每个数字的存在情况，1 表示存在，0 表示不存在。
• bitset <5> blockBit[2][2]：记录每一个小宫格每个数字的存在情况，1 表示存在，0 表示不存在。

每次读入一个数独时，就顺便把每一行、每一列、每一个小宫格的情况也记录下来，方便后面回溯递归时使用。大致算法如下：

for (int i = 0; i < 4; i++)for (int j = 0; j < 4; j++){rowBit[i].set(A[i][j]);colBit[j].set(A[i][j]);blockBit[i/2][j/2].set(A[i][j]);}	

【题解】

#include 
#include 
#include 
#include 
using namespace std;class Sudoku{private:int data[4][4];bitset <5> rowBit[4];bitset <5> colBit[4];bitset <5> blockBit[2][2];bool isValid;int answer;public:Sudoku (int A[4][4]){isValid = true;answer = 0;for (int i = 0; i < 4; i++){for (int j = 0; j < 4; j++){if (A[i][j] != 0){if (rowBit[i][A[i][j]] || colBit[j][A[i][j]] || blockBit[i/2][j/2][A[i][j]])isValid = false;else{rowBit[i].set(A[i][j]);colBit[j].set(A[i][j]);blockBit[i/2][j/2].set(A[i][j]);}	}data[i][j] = A[i][j];rowBit[i][0] = colBit[j][0] = blockBit[i/2][j/2][0] = 1;}}}bool Solve (int row = 0, int col = 0){if (!isValid){printf("无效数独！\n");return false;}if (col == 4){row++;col = 0;}if (row == 5 && col == 0){answer++;printf("答案%d：\n", answer);Print();printf("\n");}else if (data[row][col] != 0){Solve(row, col+1);}else{for (int num = 1; num <= 4; num++){if (!rowBit[row][num] && !colBit[col][num] && !blockBit[row/2][col/2][num]){rowBit[row][num] = colBit[col][num] = blockBit[row/2][col/2][num] = 1;data[row][col] = num;Solve(row, col+1);rowBit[row][num] = colBit[col][num] = blockBit[row/2][col/2][num] = 0;data[row][col] = 0;}}}}void Print (){for (int i = 0; i < 4; i++){for (int j = 0; j < 4; j++)printf("%d ", data[i][j]);printf("\n");}}bool getValid (){return isValid;}
};int A1[4][4] = {{0, 3, 1, 0},{1, 0, 0, 3},{2, 0, 3, 4},{0, 4, 2, 0},
};int A2[4][4] = {{2, 0, 0, 0},{0, 3, 1, 2},{0, 0, 4, 0},{0, 4, 0, 1},
};int A3[4][4] = {{0, 2, 0, 0},{1, 0, 3, 0},{0, 0, 0, 3},{0, 0, 4, 1},
};int A4[4][4] = {{0, 0, 0, 0},{1, 0, 2, 0},{0, 4, 0, 1},{0, 0, 0, 0},
};int A5[4][4] = {{0, 0, 0, 0},{0, 0, 2, 0},{0, 3, 0, 1},{0, 0, 0, 0},
};int A6[4][4] = {{0, 0, 0, 0},{0, 0, 0, 0},{4, 0, 0, 1},{0, 0, 0, 0},
};int main(){Sudoku S1(A5);printf("题目：\n");S1.Print();printf("\n");S1.Solve();return 0;
}

8. 求解九宫格数独

【九宫格数独规则】九宫格数独由9行9列共81个小格子构成。

分别在格子中填入1到9的数字，并满足下面的条件：

• 每一行都用到1,2,3,4,5,6,7,8,9
• 每一列都用到1,2,3,4,5,6,7,8,9
• 每3×3的格子都用到1,2,3,4,5,6,7,8,9

【输入和输出样例】

题目：
8 0 0 0 0 0 0 0 0
0 0 3 6 0 0 0 0 0
0 7 0 0 9 0 2 0 0
0 5 0 0 0 7 0 0 0
0 0 0 0 4 5 7 0 0
0 0 0 1 0 0 0 3 0
0 0 1 0 0 0 0 6 8
0 0 8 5 0 0 0 1 0
0 9 0 0 0 0 4 0 0答案1：
8 1 2 7 5 3 6 4 9
9 4 3 6 8 2 1 7 5
6 7 5 4 9 1 2 8 3
1 5 4 2 3 7 8 9 6
3 6 9 8 4 5 7 2 1
2 8 7 1 6 9 5 3 4
5 2 1 9 7 4 3 6 8
4 3 8 5 2 6 9 1 7
7 9 6 3 1 8 4 5 2

【分析】对于九宫格数独、六宫格数独、十六宫格数独也可以使用以上解法。不过，如果题面给出的数字太少的话，想要尝试所有的解法，就需要一个个格子的填数字和不断的回溯，运行起来还是比较慢的。试想一个极端的情况，即一个空白的 9x9 数独，那么程序就需要递归 81 层才能输出一个答案，这得遍历很长很长时间才能输出所有答案。

如果我们只是想寻找数独的其中一个解，那就好办了，不需要在寻找其他解上浪费太多时间（而实际上许多九宫格数独谜题也只有一个解而已）。只要一找到解，递归立刻终止，并输出答案。

【回溯算法描述】请注意体会return true和return false为什么要写在这些地方。

// 在第row行第col列开始填数字
bool solve (row, col){if (row,col 超出了范围)重新调整到下一行，即row+1，col=0;if ((row,col) == (9,0))输出方案;返回true; // 表示找到了一种解法，之后开始不断回溯，把“找到解法”的消息一层层往上传递else{if (第row行第col列 == 0){  // 第row行第col列没有填数字尝试在第row行第col列填数字1~9if (该数字与其他数字没有冲突){第row行第col列 = 数字;标记占位标志;if (solve(row, col+1) == true)  // 往下一个格子填数字，若返回来的值是true，则表示下层已经找到了一种解法// 若返回来的值是false，则表示下一个格子填不了数字返回true; // 即向上一层结点表示找到了一种解法第row行第col列 = 0;复位占位标志;}返回false; // 表示该格子填不了数字}else{solve(row, col+1);  // 第row行第col列已经填了数字，往下一个格子填数字}}
}

【题解】

#include 
#include 
#include 
#include 
using namespace std;class Sudoku{private:int data[9][9];int answer;bitset <10> rowBit[9];bitset <10> colBit[9];bitset <10> blockBit[3][3];bool isValid;public:Sudoku (int A[9][9]){isValid = true;answer = 0;for (int i = 0; i < 9; i++){for (int j = 0; j < 9; j++){if (A[i][j] != 0){if (rowBit[i][A[i][j]] || colBit[j][A[i][j]] || blockBit[i/3][j/3][A[i][j]])isValid = false;else{rowBit[i].set(A[i][j]);colBit[j].set(A[i][j]);blockBit[i/3][j/3].set(A[i][j]);}	}data[i][j] = A[i][j];rowBit[i][0] = colBit[j][0] = blockBit[i/3][j/3][0] = 1;}}}bool Solve (int row = 0, int col = 0){if (!isValid){printf("无效数独！\n");return false;}if (col == 9){row++;col = 0;}if (row == 9 && col == 0){answer++;printf("答案%d：\n", answer);Print();printf("\n");return true;  // 找到一个解，就立刻返回 }else if (data[row][col] != 0){Solve(row, col+1);}else{for (int num = 1; num <= 9; num++){if (!rowBit[row][num] && !colBit[col][num] && !blockBit[row/3][col/3][num]){rowBit[row][num] = colBit[col][num] = blockBit[row/3][col/3][num] = 1;data[row][col] = num;if (Solve(row, col+1))  // 若找到一个解，则立刻返回 return true;rowBit[row][num] = colBit[col][num] = blockBit[row/3][col/3][num] = 0;data[row][col] = 0;}}return false;  // 这一格尝试九个数字都不行，返回false }}void Print (){for (int i = 0; i < 9; i++){for (int j = 0; j < 9; j++)printf("%d ", data[i][j]);printf("\n");}}bool getValid (){return isValid;}
};int A1[9][9] = {{5, 3, 0, 0, 7, 0, 0, 0, 0},{6, 0, 0, 1, 9, 5, 0, 0, 0},{0, 9, 8, 0, 0, 0, 0, 6, 0},{8, 0, 0, 0, 6, 0, 0, 0, 3},{4, 0, 0, 8, 0, 3, 0, 0, 1},{7, 0, 0, 0, 2, 0, 0, 0, 6},{0, 6, 0, 0, 0, 0, 2, 8, 0},{0, 0, 0, 4, 1, 9, 0, 0, 5},{0, 0, 0, 0, 8, 0, 0, 7, 9}
};int A2[9][9] = {{5, 6, 7, 0, 0, 0, 0, 3, 8},{8, 3, 2, 0, 0, 0, 1, 4, 0},{0, 0, 0, 0, 3, 8, 7, 5, 6},{0, 0, 0, 3, 6, 4, 5, 1, 7},{4, 1, 3, 0, 0, 0, 9, 6, 2},{6, 7, 5, 9, 2, 1, 0, 0, 0},{2, 5, 9, 6, 1, 0, 0, 0, 0},{0, 4, 1, 0, 0, 0, 6, 2, 5},{7, 8, 0, 0, 0, 0, 3, 9, 1}
};int A3[9][9] = {{0, 0, 0, 0, 0, 0, 3, 0, 0},{0, 0, 0, 9, 0, 0, 7, 0, 0},{0, 0, 9, 0, 5, 0, 0, 8, 1},{4, 1, 0, 0, 0, 6, 0, 0, 0},{0, 6, 0, 0, 7, 0, 0, 2, 0},{0, 0, 0, 2, 0, 0, 0, 5, 4},{1, 4, 0, 0, 3, 0, 2, 0, 0},{0, 8, 0, 0, 0, 2, 0, 0, 0},{0, 0, 5, 0, 0, 0, 0, 0, 0}
};int A4[9][9] = {  // 号称世界最难数独题 {8, 0, 0, 0, 0, 0, 0, 0, 0},{0, 0, 3, 6, 0, 0, 0, 0, 0},{0, 7, 0, 0, 9, 0, 2, 0, 0},{0, 5, 0, 0, 0, 7, 0, 0, 0},{0, 0, 0, 0, 4, 5, 7, 0, 0},{0, 0, 0, 1, 0, 0, 0, 3, 0},{0, 0, 1, 0, 0, 0, 0, 6, 8},{0, 0, 8, 5, 0, 0, 0, 1, 0},{0, 9, 0, 0, 0, 0, 4, 0, 0}
};int main(){Sudoku S1(A3);cout << "题目：\n";S1.Print();cout << "\n";S1.Solve();return 0;
}

进一步优化

上面的算法中，填好了这一个格子的数字后，就开始检查下一个格子，即进入到下一层的递归。如果下一个格子其实已经填数字，那么进入下一层递归这一操作是不必要的。我们可以在进入递归前先判断下一个格子是否填有数字，如果有，就再下一个格子检查；如果没有，则进入到下一层递归中，开始填数字尝试。

【回溯算法描述】请注意体会return true和return false为什么要写在这些地方。同时，请思考两个问题：

（1）为什么行循环的初始值是形参row，列循环的初始值却是数字 0？

（2）为什么从两重循环出来后就可以说明找到了一个解？

（答案在本节末尾ww）

// 在第row行第col列开始填数字
bool solve (row, col){for (row: row~8)  // 循环遍历每一行和每一列，检查每一个格子是否填了数字for (col: 0~8)if (第row行第col列 == 0){  // 第row行第col列没有填数字尝试在第row行第col列填数字1~9if (该数字与其他数字没有冲突){第row行第col列 = 数字;标记占位标志;if (solve(row, col) == true)// 往下一个格子填数字，若返回来的值是true，则表示下层已经找到了一种解法// 若返回来的值是false，则表示下一个格子填不了数字返回true; // 即向上一层结点表示找到了一种解法第row行第col列 = 0;复位占位标志;}返回false; // 表示该格子填不了数字}输出方案; // 从循环里出来，说明找到了一个解返回true; // 表示找到了一种解法，之后开始不断回溯，把“找到解法”的消息一层层往上传递
}

【题解】

bool Sudoku::Solve (int row = 0, int col = 0){if (!isValid){printf("无效数独！\n");return false;}for (int i = row; i < 9; i++){for (int j = 0; j < 9; j++){if (data[i][j] != 0)  // 如果该格子已经有数字了，则直接循环到下一个格子 continue;for (int num = 1; num <= 9; num++){if (!rowBit[i][num] && !colBit[j][num] && !blockBit[i/3][j/3][num]){rowBit[i][num] = colBit[j][num] = blockBit[i/3][j/3][num] = 1;data[i][j] = num;if (Solve(i, j))  // 填好该格子的数字，开始填下一个格子return true;  // 若找到一个解，则立刻返回truerowBit[i][num] = colBit[j][num] = blockBit[i/3][j/3][num] = 0;data[i][j] = 0;}}return false;  // 这一格尝试九个数字都不行，返回false 	}}Print(); // 从循环里出来，说明找到了一个解return true;  // 找到一个解，就立刻返回
}

（1）两重循环中，为什么行循环的初始值是形参row，列循环的初始值是数字 0？请设想，如果行循环的初始值是形参row，列循环的初始值是形参col会发生什么。程序检查到坐标（0,8）并填了数字，现在传递给函数Solve(0, 8)，那么此时行循环的初始值是 0，列循环的初始值是 8。坐标（0,8）已经填了数字，进入下一轮循环，此时行循环的初始值是 1，列循环的初始值依旧是 8，坐标（1,0）到坐标（1,7）全部没有检查到！现在应该明白了吧。

当然，把行循环和列循环的初始值均设为 0 也是可以的，但是这就意味着每次都重头开始检查，这个是没有必要的，因为能进入到第 row 行填数字，就一定说明第 0 行到第 row-1 行已经填了数字，不然你是如何来到第 row 行填数字的？

（2）为什么从两重循环出来后就可以说明找到了一个解？当遍历到最后一个格子，即坐标为（8,8）后，已经没有其他格子了，就会跳出循环。能遍历到坐标（8,8）就说明其他格子都已经填了合法的数字，自然也可以说已经找到了一个解。除了这种情况以外，没有别的情况可以跳出这个两重循环。

参考资料：「leetcode」37. 解数独【回溯算法】详细图解！