n皇后2种解题思路与代码-Java与C++实现

2022-01-04 00:34:29

林炳文Evankaka原创作品。转载请注明出处http://blog.csdn.net/evankaka

摘要：本文主要讲了n皇后问题的解题思路，并分别用java和c++实现了过程，最后，对于算法改进，使用了位运算。

一、问题抛出与初步解题思路

问题描述：八皇后问题是一个以国际象棋为背景的问题：如何能够在 8×8 的国际象棋棋盘上放置八个皇后，使得任何一个皇后都无法直接吃掉其他的皇后？为了达到此目的，任两个皇后都不能处于同一条横行、纵行或斜线上。

n皇后2种解题思路与代码-Java与C++实现

转化规则：其实八皇后问题可以推广为更一般的n皇后摆放问题：这时棋盘的大小变为n×n，而皇后个数也变成n。当且仅当 n = 1 或 n ≥ 4 时问题有解。令一个一位数组a[n]保存所得解，其中a[i] 表示把第i个皇后放在第i行的列数（注意i的值都是从0开始计算的），下面就八皇后问题做一个简单的从规则到问题提取过程。

 

（1）因为所有的皇后都不能放在同一列，因此数组的不能存在相同的两个值。
（2）所有的皇后都不能在对角线上，那么该如何检测两个皇后是否在同一个对角线上？我们将棋盘的方格成一个二维数组，如下：

n皇后2种解题思路与代码-Java与C++实现

假设有两个皇后被放置在（i，j）和（k，l）的位置上，明显，当且仅当|i-k|=|j-l| 时，两个皇后才在同一条对角线上。

二、代码与结果

（1）C++版本

运行平台：VS2013

操作系统:Windows7

  1. /**
  2. * n皇后问题解决
  3. * @author lin
  4. *
  5. */
  6. #include <iostream>
  7. #include <cmath>
  8. #include<time.h>
  9. using namespace std;
  10. /**皇后的数目*/
  11. static int num;
  12. /**下标i表示第几行，x[i]表示第i行皇后的位置,注意此处0行不用*/
  13. static int *x;
  14. /**解的数目*/
  15. static int sum = 0;
  16. /**
  17. * 判断第k行皇后可以放置的位置
  18. * @param k k表示第k行，X[K]k表示第k行上皇后的位置
  19. * @return boolean false表示此处不能放置皇后
  20. */
  21. bool place( int k )
  22. {
  23. for ( int j = 1; j < k; j++ )
  24. {
  25. /* 如果当前传入的第K行上的皇后放置的位置和其它皇后一个对角线(abs(x[k]- x[j])==abs(k-j)或一个直线上(x[j] == x[k]) */
  26. if ( abs( x[k] - x[j] ) == abs( k - j ) || x[j] == x[k] )
  27. {
  28. return(false);
  29. }
  30. }
  31. return(true);
  32. }
  33. /**
  34. * 一行一行的确定该行的皇后位置
  35. * @param t
  36. */
  37. void backtrack( int t )
  38. {
  39. if ( t > num )                  /* 如果当前行大于皇后数目，表示找到解了 */
  40. {
  41. sum++;
  42. /* 依次打印本次解皇后的位置 */
  43. for ( int m = 1; m <= num; m++ )
  44. {
  45. //cout << x[m];   /* 这一行用输出当递归到叶节点的时候，一个可行解 */
  46. //这里只是为了好看才写成下面的
  47. for(int k =1; k <= num;k++){
  48. if(k == x[m]){
  49. cout << x[m] <<" ";
  50. }else {
  51. cout << "* ";//用*表示没有被用到的位置
  52. }
  53. }
  54. cout << endl;
  55. }
  56. cout << endl;
  57. } else {
  58. for ( int i = 1; i <= num; i++ )
  59. {
  60. x[t] = i;       /* 第t行上皇放在i列处 */
  61. if ( place( t ) )
  62. {
  63. /* 此处的place函数用来进行我们上面所说的条件的判断，如果成立，进入下一级递归 */
  64. backtrack( t + 1 );
  65. }
  66. }
  67. }
  68. }
  69. int main()
  70. {
  71. cout<<"请输入皇后数目：";
  72. cin>>num;
  73. clock_t start,finish;
  74. double totaltime;//计算程序运行时间
  75. start=clock();//起始时间
  76. x   = new int[num + 1];     /* 此处注意加1，这里0行不用，1-num分别对应1-num行 */
  77. for ( int i = 0; i <= num; i++ )
  78. x[i] = 0;
  79. backtrack( 1 );                 /*传入第一个皇后，开始递归 */
  80. cout << "方案共有" << sum;
  81. delete[]x;
  82. finish=clock();//结束时间
  83. totaltime=(double)(finish-start)/CLOCKS_PER_SEC;
  84. cout<<"\n此程序的运行时间为"<<totaltime<<"秒！"<<endl;
  85. while (1);
  86. return(0);
  87. }

输出结果：

8皇后：

n皇后2种解题思路与代码-Java与C++实现

10皇后：

n皇后2种解题思路与代码-Java与C++实现

（2）java版本

运行平台：eclispse luna

操作系统:Windows7

  1. package com.lin;
  2. import java.lang.*;
  3. /**
  4. * n皇后问题解决
  5. * @author lin
  6. *
  7. */
  8. public class QueenTest {
  9. /**下标i表示第几行，x[i]表示第i行皇后的位置,注意此处0行不用*/
  10. public int[] x;
  11. /**皇后的数目*/
  12. public int queenNum;
  13. /**解的数目*/
  14. public int methodNum;
  15. QueenTest(int queenNum) {
  16. this.queenNum = queenNum;
  17. this.x = new int[queenNum+1];//注意，这里我们从第1行开始算起，第0行不用
  18. backtrack(1);//从第一个皇后开始递归
  19. }
  20. /**
  21. * 一行一行的确定该行的皇后位置
  22. * @param t
  23. */
  24. public void backtrack(int t)
  25. {
  26. if( t > queenNum) //如果当前行大于皇后数目，表示找到解了
  27. {
  28. methodNum++;//sum为所有的可行的解
  29. //依次打印本次解皇后的位置
  30. for(int m = 1; m <= queenNum; m++){
  31. //System.out.println(x[m]);//这一行用输出当递归到叶节点的时候，一个可行解
  32. //这里只是为了好看才写成下面的
  33. for(int k =1; k <= queenNum;k++){
  34. if(k == x[m]){
  35. System.out.print(x[m]+" ");
  36. }else {
  37. System.out.print("* ");//用*表示没有被用到的位置
  38. }
  39. }
  40. System.out.println();
  41. }
  42. System.out.println();
  43. }
  44. else{
  45. for(int i = 1;i <= queenNum;i++)
  46. {
  47. x[t] = i;//第t行上皇后的位置只能是1-queenNum
  48. if(place(t)) {//此处的place函数用来进行我们上面所说的条件的判断，如果成立，进入下一级递归,即放置下一个皇后
  49. backtrack(t+1);
  50. }
  51. }
  52. }
  53. }
  54. /**
  55. * 判断第k行皇后可以放置的位置
  56. * @param k k表示第k行，X[K]k表示第k行上皇后的位置
  57. * @return boolean false表示此处不能放置皇后
  58. */
  59. public boolean place(int k) {
  60. for (int j = 1; j < k; j++)
  61. // 如果当前传入的第K行上的皇后放置的位置和其它皇后一个对角线(abs(x[k]- x[j])==abs(k-j)或一个直线上(x[j] == x[k])
  62. if (Math.abs(x[k] - x[j]) == Math.abs(k - j) || (x[j] == x[k])){
  63. return false;
  64. }
  65. return true;
  66. }
  67. public static void main(String[] args) {
  68. QueenTest queenTest = new QueenTest(8);
  69. System.out.println("总共解数为："+ queenTest.methodNum);
  70. }
  71. }

输出结果：

这是八皇后

n皇后2种解题思路与代码-Java与C++实现

这是十皇后：
n皇后2种解题思路与代码-Java与C++实现
通过对比java和C++发现，反而java运行更加快？这是为什么呢？原因就是C++中使用了new操作，而java中基本数据都是在栈上来创建的，存取的速度比堆快多了。

三、更加高效的算法-位运算版本

上面的方法递归次数实在太多了，也浪费空间，下面介绍目前号称是最快的--位运算。原理就不介绍了，看这里吧http://blog.csdn.net/xadillax/article/details/6512318

（1）Java代码

  1. package com.lin;
  2. import java.util.Scanner;
  3. /**
  4. * n皇后问题解决
  5. * @author lin
  6. *
  7. */
  8. public class QueenTest3 {
  9. /**sum用来记录皇后放置成功的不同布局数*/
  10. public long sum = 0;
  11. /**upperlim用来标记所有列都已经放置好了皇后*/
  12. public long upperlim = 1;
  13. /**
  14. * 试探算法从最右边的列开始。
  15. * @param row 竖列
  16. * @param ld  左对角线
  17. * @param rd  右对角线
  18. */
  19. void queenPos(long row, long ld, long rd)
  20. {
  21. if (row != upperlim)
  22. {
  23. // row，ld，rd进行“或”运算，求得所有可以放置皇后的列,对应位为0，
  24. // 然后再取反后“与”上全1的数，来求得当前所有可以放置皇后的位置，对应列改为1
  25. // 也就是求取当前哪些列可以放置皇后
  26. long pos = upperlim & ~(row | ld | rd);
  27. while (pos != 0)    // 0 -- 皇后没有地方可放，回溯
  28. {
  29. // 拷贝pos最右边为1的bit，其余bit置0
  30. // 也就是取得可以放皇后的最右边的列
  31. long p = pos & -pos;
  32. // 将pos最右边为1的bit清零
  33. // 也就是为获取下一次的最右可用列使用做准备，
  34. // 程序将来会回溯到这个位置继续试探
  35. pos -= p;
  36. // row + p，将当前列置1，表示记录这次皇后放置的列。
  37. // (ld + p) << 1，标记当前皇后左边相邻的列不允许下一个皇后放置。
  38. // (ld + p) >> 1，标记当前皇后右边相邻的列不允许下一个皇后放置。
  39. // 此处的移位操作实际上是记录对角线上的限制，只是因为问题都化归
  40. // 到一行网格上来解决，所以表示为列的限制就可以了。显然，随着移位
  41. // 在每次选择列之前进行，原来N×N网格中某个已放置的皇后针对其对角线
  42. // 上产生的限制都被记录下来了
  43. queenPos(row + p, (ld + p) << 1, (rd + p) >> 1);
  44. }
  45. }
  46. else
  47. {
  48. // row的所有位都为1，即找到了一个成功的布局，回溯
  49. sum++;
  50. }
  51. }
  52. /**
  53. * 根据传入的皇后数目开始计算
  54. * @param n 皇后数据
  55. */
  56. void queen(int queenNum) {
  57. if ((queenNum < 1) || (queenNum > 32)) {
  58. System.out.println(" 只能计算1-32之间\n");
  59. return;
  60. }
  61. // N个皇后只需N位存储，N列中某列有皇后则对应bit置1。
  62. upperlim = (upperlim << queenNum) - 1;
  63. queenPos(0, 0, 0);
  64. }
  65. public static void main(String[] args) {
  66. Scanner sc=new Scanner(System.in);
  67. System.out.print("请输入皇后数目:");
  68. int num=sc.nextInt();
  69. long starTime=System.currentTimeMillis();//程序开始时间
  70. QueenTest3 queenTest3 = new QueenTest3();
  71. queenTest3.queen(num);
  72. System.out.println("总共解数为："+ queenTest3.sum);
  73. long endTime=System.currentTimeMillis();//程序结束时间
  74. double runTimes=(double)(endTime-starTime) / 1000.0;
  75. System.out.println("程序总共运行时间："+ runTimes + "s");
  76. }
  77. }

运行结果：

八皇后的效果：（位运算版本）

n皇后2种解题思路与代码-Java与C++实现

把上面的代码中的输出结果的去掉：（非位运算版本）

  1. //依次打印本次解皇后的位置
  2. /*  for(int m = 1; m <= queenNum; m++){
  3. //System.out.println(x[m]);//这一行用输出当递归到叶节点的时候，一个可行解
  4. //这里只是为了好看才写成下面的
  5. for(int k =1; k <= queenNum;k++){
  6. if(k == x[m]){
  7. System.out.print(x[m]+" ");
  8. }else {
  9. System.out.print("* ");//用*表示没有被用到的位置
  10. }
  11. System.out.println();
  12. }
  13. System.out.println();*/

然后输出如下：

n皇后2种解题思路与代码-Java与C++实现

经过两者对比，发现快了2ms

十皇后效果，没想到反而比八皇后的位运算版本还快（十皇后位运算版本）

n皇后2种解题思路与代码-Java与C++实现

十皇后非位运算版本
n皇后2种解题思路与代码-Java与C++实现
快了10倍啊！！！！！！！！！！！！！！！！！！！
 

12皇后

位运算

n皇后2种解题思路与代码-Java与C++实现

非位运算

n皇后2种解题思路与代码-Java与C++实现

（2）C++版本

  1. /*
  2. ** 目前最快的N皇后递归解决方法
  3. ** N Queens Problem
  4. ** 试探-回溯算法，递归实现
  5. */
  6. #include <iostream>
  7. using namespace std;
  8. #include <time.h>
  9. // sum用来记录皇后放置成功的不同布局数；upperlim用来标记所有列都已经放置好了皇后。
  10. long sum = 0, upperlim = 1;
  11. // 试探算法从最右边的列开始。
  12. void test(long row, long ld, long rd)
  13. {
  14. if (row != upperlim)
  15. {
  16. // row，ld，rd进行“或”运算，求得所有可以放置皇后的列,对应位为0，
  17. // 然后再取反后“与”上全1的数，来求得当前所有可以放置皇后的位置，对应列改为1
  18. // 也就是求取当前哪些列可以放置皇后
  19. long pos = upperlim & ~(row | ld | rd);
  20. while (pos)    // 0 -- 皇后没有地方可放，回溯
  21. {
  22. // 拷贝pos最右边为1的bit，其余bit置0
  23. // 也就是取得可以放皇后的最右边的列
  24. long p = pos & -pos;
  25. // 将pos最右边为1的bit清零
  26. // 也就是为获取下一次的最右可用列使用做准备，
  27. // 程序将来会回溯到这个位置继续试探
  28. pos -= p;
  29. // row + p，将当前列置1，表示记录这次皇后放置的列。
  30. // (ld + p) << 1，标记当前皇后左边相邻的列不允许下一个皇后放置。
  31. // (ld + p) >> 1，标记当前皇后右边相邻的列不允许下一个皇后放置。
  32. // 此处的移位操作实际上是记录对角线上的限制，只是因为问题都化归
  33. // 到一行网格上来解决，所以表示为列的限制就可以了。显然，随着移位
  34. // 在每次选择列之前进行，原来N×N网格中某个已放置的皇后针对其对角线
  35. // 上产生的限制都被记录下来了
  36. test(row + p, (ld + p) << 1, (rd + p) >> 1);
  37. }
  38. }
  39. else
  40. {
  41. // row的所有位都为1，即找到了一个成功的布局，回溯
  42. sum++;
  43. }
  44. }
  45. int main()
  46. {
  47. int num;
  48. cout<<"请输入皇后数目：";
  49. cin>>num;
  50. clock_t start,finish;
  51. double totaltime;//计算程序运行时间
  52. start=clock();//起始时间
  53. // 因为整型数的限制，最大只能32位，
  54. // 如果想处理N大于32的皇后问题，需要
  55. // 用bitset数据结构进行存储
  56. if ((num < 1) || (num > 32))
  57. {
  58. cout << " 只能计算1-32之间\n";
  59. return 0;
  60. }
  61. // N个皇后只需N位存储，N列中某列有皇后则对应bit置1。
  62. upperlim = (upperlim << num) - 1;
  63. test(0, 0, 0);
  64. cout << "方案共有" << sum;
  65. finish=clock();//结束时间
  66. totaltime=(double)(finish-start)/CLOCKS_PER_SEC;
  67. cout<<"\n此程序的运行时间为"<<totaltime<<"秒！"<<endl;
  68. while(1);
  69. return 0;
  70. }

输出结果：

n皇后2种解题思路与代码-Java与C++实现

n皇后2种解题思路与代码-Java与C++实现

n皇后2种解题思路与代码-Java与C++实现

下面来对比下java和C++运算的效果：

16皇后C++版本（位运算）

n皇后2种解题思路与代码-Java与C++实现

16皇后java版本（位运算）

n皇后2种解题思路与代码-Java与C++实现

发现又是java快了点。

from: http://blog.csdn.net/evankaka/article/details/48756951

上一篇：python 下载.whl 文件，查看已安装软件包方法


下一篇：C#微信公众号开发之网页授权oauth2.0获取用户基本信息（一）