[关闭]
@songpfei 2015-12-24T09:45:22.000000Z 字数 4926 阅读 3153

N皇后问题

OJ_算法

1. 问题概述

N皇后问题是一个经典的问题，在一个N*N的棋盘上放置N个皇后，每行一个并使其不能互相攻击（同一行、同一列、同一斜线上的皇后都会自动攻击）。

求解N皇后问题是算法中回溯法应用的一个经典案例：
  回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。

  在现实中，有很多问题往往需要我们把其所有可能穷举出来，然后从中找出满足某种要求的可能或最优的情况，从而得到整个问题的解。回溯算法就是解决这种问题的“通用算法”，有“万能算法”之称。N皇后问题在N增大时就是这样一个解空间很大的问题，所以比较适合用这种方法求解。这也是N皇后问题的传统解法，很经典。

2. 问题分析

下面是算法的高级伪码描述，这里用一个N*N的矩阵来存储棋盘：

  1. 1. 算法开始, 清空棋盘，当前行设为第一行，当前列设为第一列
  3. 2. 在当前行，当前列的位置上判断是否满足条件(即保证经过这一点的行,列与斜线上都没有两个皇后)，若不满足，跳到第4步
  5. 3. 在当前位置上满足条件的情形：
  7.     - 在当前位置放一个皇后，若当前行是最后一行，记录一个解；
  9.     - 若当前行不是最后一行，当前行设为下一行, 当前列设为当前行的第一个待测位置；
  11.     - 若当前行是最后一行，当前列不是最后一列，当前列设为下一列；
  13.     - 若当前行是最后一行，当前列是最后一列，回溯，即清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置；
  15.     - 以上返回到第2步
  17. 4. 在当前位置上不满足条件的情形：
  19.    - 若当前列不是最后一列，当前列设为下一列，返回到第2步;
  21.    - 若当前列是最后一列了，回溯，即，若当前行已经是第一行了，算法退出，否则，清空当前行及以下各行的棋盘，然后，当前行设为上一行，当前列设为当前行的下一个待测位置，返回到第2步;

  算法的基本原理是上面这个样子，但不同的是用的数据结构不同，检查某个位置是否满足条件的方法也不同。为了提高效率，有各种优化策略，如多线程，多分配内存表示棋盘等。

  在具体解决该问题时，可以将其拆分为几个小问题。首先就是在棋盘上如何判断两个皇后是否能够相互攻击，在最初接触这个问题时，首先想到的方法就是把棋盘存储为一个二维数组，然后在需要在第i行第j列放置皇后时，根据问题的描述，首先判断是在第i行是否有皇后，由于每行只有一个皇后，这个判断也可以省略，然后判断第j列是否有皇后，这个也很简单，最后需要判断在同一斜线上是否有皇后，按照该方法需要判断两次，正对角线方向和负对角线方向，总体来说也不难。但是写完之后，总感觉很笨，因为在N皇后问题中这个函数的使用次数太多了，而这样做效率较差，个人感觉很不爽。上网查看了别人的实现之后大吃一惊，大牛们都是使用一个一维数组来存储棋盘，在某个位置上是否有皇后可以相互攻击的判断也很简单。具体细节如下：

  把棋盘存储为一个N维数组a[N]，数组中第i个元素的值代表第i行的皇后位置，这样便可以把问题的空间规模压缩为一维O(N)，在判断是否冲突时也很简单，首先每行只有一个皇后，且在数组中只占据一个元素的位置，行冲突就不存在了，其次是列冲突，判断一下是否有a[i]与当前要放置皇后的列j相等即可。至于斜线冲突，通过观察可以发现所有在斜线上冲突的皇后的位置都有规律即它们所在的行列互减的绝对值相等，即| row – i | = | col – a[i] | 。这样某个位置是否可以放置皇后的问题已经解决。
参考文献：

3 算法实现

3.1 递归法

递归方法较为简单，大致思想如下：

  1. void queen(int row)
  2. {
  4.  if (n == row)      //如果已经找到结果，则打印结果
  5.    print_result();
  7.  else 
  8.  {
  9.    for (k=0 to N) 
  10.    { //试探第row行每一个列
  11.      if (can_place(row, k) 
  12.      { 
  13.          place(row, k);   //放置皇后
  14.          queen(row + 1);  //继续探测下一行
  16.      }
  17.     }
  18.  }
  19. }

该方法由于在探测第i行后，如果找到一个可以放置皇后的位置j后，则会递归探测下一行，结束后则会继续探测i行j+1列，故可以找到所有的N皇后的解。但递归方法一般效率较低。

代码实现如下

  1. /***************************
  2. file:queen.h
  3. #ifndef QUEEN_H
  4. #define QUEEN_H
  5. ***************************/
  7. /******************************
  8. 输入参数：
  9. int n : 皇后的个数
  11. 返回值：
  12. int : 放置n皇后方案的个数
  13. *****************************/
  14. int PlaceQueenMethodNum(int n);
  16. #endif // !QUEEN_H
  1. /****************************
  2. file:queen.cpp
  3. auther:spf
  4. data:2015.12.24
  5. ****************************/
  6. #include"queen.h"
  7. #include<cmath>
  8. static bool CheckQueen(int queen[], int row, int col);
  9. static void PlaceQueen(int queen[], int row, int n_queens, int &result_count);
  12. int PlaceQueenMethodNum(int n)
  13. {
  14.     int *queen = new int[n];
  15.     int result_count = 0;
  16.     PlaceQueen(queen, 0, n, result_count);
  17.     delete[]queen;
  18.     return result_count;
  19. }
  22. bool CheckQueen(int queen[],int row, int col)
  23. {
  24.     for (int i = 0; i < row; i++)//和0~row-1行放置的皇后对比
  25.     {
  26.         if (queen[i] == col || abs(i - row) == abs(queen[i] - col))//判断第i行的皇后是否在col列或（row,col)与（i,queen[i])是否共斜线
  27.             return false;
  28.     }
  29.     return true;
  30. }
  31. void PlaceQueen(int queen[],int row,int n_queens,int &result_count)
  32. {
  34.     if (row == n_queens)
  35.         result_count++;
  36.     else
  37.     {
  38.         for (int i_cols = 0; i_cols < n_queens; i_cols++)//试探第row行
  39.         {
  40.             if (CheckQueen(queen,row, i_cols))
  41.             {
  42.                 queen[row] = i_cols;
  43.                 PlaceQueen(queen, row + 1, n_queens,result_count);
  44.             }
  45.         }
  46.     }
  47. }

main:

  1. #include<cstdlib>
  2. #include<iostream>
  3. #include"queen.h"
  4. using namespace std;
  5. int main(void)
  6. {
  7.     int n;
  9.     do
  10.     {
  11.         cin >> n;
  13.         cout << n << "个queens的解个数为：" << PlaceQueenMethodNum(n) << endl;
  15.     } while (n);
  17.     system("pause");
  18.     return 0;
  19. }

输出：

n solution(n)
1 1
2 0
3 0
4 2
5 10
6 4
7 40
8 92
9 352
10 724
11 2680
12 14200
13 73712
14 365596
15 2279184
16 14772512
17 95815104
18 666090624
19 4968057848
20 39029188884
21 314666222712
22 2691008701644
23 24233937684440
24 227514171973736
25 2207893435808352

3.2 非递归法

  非递归方法的一个重要问题时何时回溯及如何回溯的问题。程序首先对N行中的每一行进行探测，寻找该行中可以放置皇后的位置，具体方法是对该行的每一列进行探测，看是否可以放置皇后，如果可以，则在该列放置一个皇后，然后继续探测下一行的皇后位置。如果已经探测完所有的列都没有找到可以放置皇后的列，此时就应该回溯，把上一行皇后的位置往后移一列，如果上一行皇后移动后也找不到位置，则继续回溯直至某一行找到皇后的位置或回溯到第一行，如果第一行皇后也无法找到可以放置皇后的位置，则说明已经找到所有的解程序终止。如果该行已经是最后一行，则探测完该行后，如果找到放置皇后的位置，则说明找到一个结果，打印出来。但是此时并不能再此处结束程序，因为我们要找的是所有N皇后问题所有的解，此时应该清除该行的皇后，从当前放置皇后列数的下一列继续探测。

代码实现
*回溯法解N皇后问题
* 使用一个一维数组表示皇后的位置
* 其中数组的下标表示皇后所在的行
* 数组元素的值表示皇后所在的列
* 这样设计的棋盘，所有皇后必定不在同一行，于是行冲突就不存在了

  1. /***************************
  2. file:queen.h
  3. #ifndef QUEEN_H
  4. #define QUEEN_H
  5. ***************************/
  7. /******************************
  8. 输入参数：
  9. int n : 皇后的个数
  11. 返回值：
  12. int : 放置n皇后方案的个数
  13. *****************************/
  14. int PlaceQueenMethodNum(int n);
  16. #endif // !QUEEN_H
  1. /****************************
  2. file:queen.cpp
  3. auther:spf
  4. data:2015.12.24
  5. ****************************/
  6. #include"queen.h"
  7. #include<cmath>
  8. static bool CheckQueen(int queen[], int row, int col);
  11. int PlaceQueenMethodNum(int n)
  12. {
  13.     int *queen = new int[n];
  15.     int result_count = 0;
  16.     int row = 0;
  17.     int col = 0;
  18.     while ( row < n )
  19.     {
  20.         while( col<n )//对于第row行，逐一试探，确定其列数
  21.         {
  23.             if (CheckQueen(queen, row, col))
  24.             {
  25.                 queen[row] = col;//确定列数，开始下一行
  26.                 if (row == n - 1)//找到一个解
  27.                 {
  28.                     result_count++;
  29.                     break;
  30.                 }   
  31.                 else
  32.                 {
  33.                     row++;//继续确定下一行皇后位置，从第0列开始搜索
  34.                     col = -1;
  35.                 }    
  36.             }
  37.             col++;
  38.         }
  39.         if (row == 0) //回溯完毕
  40.             break;
  41.         row--;//回溯，把上一行皇后的位置往后移一列
  42.         col = queen[row]+1;
  44.     }
  45.     delete[]queen;
  46.     return result_count;
  47. }
  49. /*检测皇后的有效性*/
  50. bool CheckQueen(int queen[],int row, int col)
  51. {
  52.     for (int i = 0; i < row; i++)//和0~row-1行放置的皇后对比
  53.     {
  54.     if (queen[i] == col || abs(i - row) == abs(queen[i] - col))//判断第i行的皇后是否在col列或（row,col)与（i,queen[i])是否共斜线
  55.             return false;
  56.     }
  57.     return true;
  58. }

main:

  1. #include<cstdlib>
  2. #include<iostream>
  3. #include"queen.h"
  4. using namespace std;
  5. int main(void)
  6. {
  7.     int n;
  9.     do
  10.     {
  11.         cin >> n;
  13.         cout << n << "个queens的解个数为：" << PlaceQueenMethodNum(n) << endl;
  15.     } while (n);
  17.     system("pause");
  18.     return 0;
  19. }
  1. http://blog.csdn.net/hackbuteer1/article/details/6657109
  2. http://blog.chinaunix.net/uid-23781137-id-2181724.html
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注