有问题请及时联系博主：Alliswell_WP，转载请注明出处。

参考书籍：《C++程序设计》作者：（美）Y. Daniel Liang著、刘晓光等译

书籍源代码下载：https://media.pearsoncmg.com/bc/abp/cs-resources/products/product.html#product,isbn=0133252817

 P559-P561

问题描述：参考——https://baike.baidu.com/item/%E5%85%AB%E7%9A%87%E5%90%8E%E9%97%AE%E9%A2%98/11053477?fr=aladdin

在 8×8 格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法？

问题求解：

关键点：八皇后问题可以通过递归方法求解。

国际象棋上摆放八个皇后，令任意两个皇后都不能处于同一行、同一列或同一斜线上，使其不能互相攻击，问有多少种摆法。可以用一个二维排列代表棋盘网格。当然，每一行只能有一个皇后。首先按照下面的形式声明数组queens:

  int queens[8];

分配j到网格queens[i]上，其中i表示行，j表示列。图a展示皇后的排列内容，图b展示的是网格中的排列。queens[i]表示了第i行的皇后的位置

 

求解八皇后问题的程序如下：

 1 #include <iostream>
 2 using namespace std;
 3 
 4 const int NUMBER_OF_QUEENS = 8; //常数：八个皇后
 5 int queens[NUMBER_OF_QUEENS];
 6 
 7 //检查是否可以在第i行和第j列放置一个女王
 8 bool isValid(int row, int column)
 9 {
10     for (int i = 1; i <= row; i++)
11         if (queens[row - i] == column //检查列
12             || queens[row - i] == column - i //检查左上对角线
13             || queens[row - i] == column + i) //检查右上对角线
14             return false; //发生冲突
15     return true; //没有冲突
16 }
17 
18 //显示带有八个皇后的棋盘
19 void printResult()
20 {
21     cout << "\n---------------------------------\n";
22     for (int row = 0; row < NUMBER_OF_QUEENS; row++)
23     {
24         for (int column = 0; column < NUMBER_OF_QUEENS; column++)
25             printf(column == queens[row] ? "| Q " : "|   ");
26         cout << "|\n---------------------------------\n";
27     }
28 }
29 
30 //搜索以将皇后放在指定的行
31 bool search(int row)
32 {
33     if (row == NUMBER_OF_QUEENS) //停止条件
34         return true; //找到将8个皇后放在8行中的解决方案
35     for (int column = 0; column < NUMBER_OF_QUEENS; column++)
36     {
37         queens[row] = column; //在(row, column)放置一个女王
38         if (isValid(row, column) && search(row + 1))
39             return true; //找到，因此返回true退出循环
40     }
41     return false; //在该行的任何列上都没有皇后的解决方案
42 }
43 
44 int main()
45 {
46     search(0); //从第0行开始搜索。注意行索引为0到7
47     printResult(); //显示结果
48     return 0;
49 }

 

程序分析：

递归调用search(1)，search(2)，search(3)，search(4)，search(5)，search(6)，search(7)，对于某一行放置皇后，递归检查上一行的三个位置，上上行的三个位置.....；如果有冲突，开始放置本行的下一个位置，依次判断，最后决定本行是否可以放置皇后。

演算如下：

 

有问题请及时联系博主：Alliswell_WP，转载请注明出处。