精华内容
下载资源
问答
  • 动态规划-N皇后问题

    千次阅读 2015-04-27 15:44:49
    N皇后问题是一个经典的问题,在一个N*N的棋盘上放置N个皇后,每行一个并使其不能互相攻击(同一行、同一列、同一斜线上的皇后都会自动攻击)。 一、 求解N皇后问题是算法中回溯法应用的一个经典案例  回溯算法也...

    转载自:http://blog.csdn.net/hackbuteer1/article/details/6657109


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

    一、 求解N皇后问题是算法中回溯法应用的一个经典案例

           回溯算法也叫试探法,它是一种系统地搜索问题的解的方法。回溯算法的基本思想是:从一条路往前走,能进则进,不能进则退回来,换一条路再试。

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

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

          1) 算法开始, 清空棋盘,当前行设为第一行,当前列设为第一列

          2) 在当前行,当前列的位置上判断是否满足条件(即保证经过这一点的行,列与斜线上都没有两个皇后),若不满足,跳到第4步

          3) 在当前位置上满足条件的情形:

                     在当前位置放一个皇后,若当前行是最后一行,记录一个解;

                     若当前行不是最后一行,当前行设为下一行, 当前列设为当前行的第一个待测位置;

                     若当前行是最后一行,当前列不是最后一列,当前列设为下一列;

                     若当前行是最后一行,当前列是最后一列,回溯,即清空当前行及以下各行的棋盘,然后,当前行设为上一行,当前列设为当前行的下一个待测位置;

                    以上返回到第2步

          4) 在当前位置上不满足条件的情形:

                    若当前列不是最后一列,当前列设为下一列,返回到第2步;

                    若当前列是最后一列了,回溯,即,若当前行已经是第一行了,算法退出,否则,清空当前行及以下各行的棋盘,然后,当前行设为上一行,当前列设为当前行的下一个待测位置,返回到第2步; 

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

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

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

           下面要解决的是使用何种方法来找到所有的N皇后的解。上面说过该问题是回溯法的经典应用,所以可以使用回溯法来解决该问题,具体实现也有两个途径,递归和非递归。递归方法较为简单,大致思想如下:

         void queen(int row)

        {

                  if (n == row)      //如果已经找到结果,则打印结果

                        print_result();

                  else {

                              for (k=0 to N) { //试探第row行每一个列

                                      if (can_place(row, k) { 

                                              place(row, k);   //放置皇后

                                             queen(row + 1);  //继续探测下一行

                                      }

                             }

                 }

        }

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

            但是一般来说递归的效率比较差,下面重点讨论一下该问题的非递归实现。

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

    完整的代码如下:

    1. /** 
    2. * 回溯法解N皇后问题 
    3. * 使用一个一维数组表示皇后的位置 
    4. * 其中数组的下标表示皇后所在的行 
    5. * 数组元素的值表示皇后所在的列 
    6. * 这样设计的棋盘,所有皇后必定不在同一行,于是行冲突就不存在了 
    7. * date  : 2011-08-03  
    8. * author: liuzhiwei 
    9. **/  
    10.   
    11. #include <stdio.h>  
    12. #include <stdlib.h>  
    13. #include <math.h>  
    14.   
    15. #define QUEEN 8     //皇后的数目  
    16. #define INITIAL -10000   //棋盘的初始值  
    17.   
    18. int a[QUEEN];    //一维数组表示棋盘  
    19.   
    20. void init()  //对棋盘进行初始化  
    21. {  
    22.     int *p;  
    23.     for (p = a; p < a + QUEEN; ++p)   
    24.     {  
    25.         *p = INITIAL;  
    26.     }  
    27. }   
    28.   
    29. int valid(int row, int col)    //判断第row行第col列是否可以放置皇后  
    30. {  
    31.     int i;  
    32.     for (i = 0; i < QUEEN; ++i)   //对棋盘进行扫描  
    33.     {  
    34.         if (a[i] == col || abs(i - row) == abs(a[i] - col))   //判断列冲突与斜线上的冲突  
    35.             return 0;  
    36.     }  
    37.     return 1;  
    38. }   
    39.   
    40. void print()    //打印输出N皇后的一组解  
    41. {  
    42.     int i, j;  
    43.     for (i = 0; i < QUEEN; ++i)  
    44.     {  
    45.         for (j = 0; j < QUEEN; ++j)  
    46.         {  
    47.             if (a[i] != j)      //a[i]为初始值  
    48.                 printf("%c "'.');  
    49.             else                //a[i]表示在第i行的第a[i]列可以放置皇后  
    50.                 printf("%c "'#');  
    51.         }  
    52.         printf("\n");  
    53.     }  
    54.     for (i = 0; i < QUEEN; ++i)  
    55.         printf("%d ", a[i]);  
    56.     printf("\n");  
    57.     printf("--------------------------------\n");  
    58. }  
    59.   
    60. void queen()      //N皇后程序  
    61. {  
    62.     int n = 0;  
    63.     int i = 0, j = 0;  
    64.     while (i < QUEEN)  
    65.     {  
    66.         while (j < QUEEN)        //对i行的每一列进行探测,看是否可以放置皇后  
    67.         {  
    68.             if(valid(i, j))      //该位置可以放置皇后  
    69.             {  
    70.                 a[i] = j;        //第i行放置皇后  
    71.                 j = 0;           //第i行放置皇后以后,需要继续探测下一行的皇后位置,所以此处将j清零,从下一行的第0列开始逐列探测  
    72.                 break;  
    73.             }  
    74.             else  
    75.             {  
    76.                 ++j;             //继续探测下一列  
    77.             }  
    78.         }  
    79.         if(a[i] == INITIAL)         //第i行没有找到可以放置皇后的位置  
    80.         {  
    81.             if (i == 0)             //回溯到第一行,仍然无法找到可以放置皇后的位置,则说明已经找到所有的解,程序终止  
    82.                 break;  
    83.             else                    //没有找到可以放置皇后的列,此时就应该回溯  
    84.             {  
    85.                 --i;  
    86.                 j = a[i] + 1;        //把上一行皇后的位置往后移一列  
    87.                 a[i] = INITIAL;      //把上一行皇后的位置清除,重新探测  
    88.                 continue;  
    89.             }  
    90.         }  
    91.         if (i == QUEEN - 1)          //最后一行找到了一个皇后位置,说明找到一个结果,打印出来  
    92.         {  
    93.             printf("answer %d : \n", ++n);  
    94.             print();  
    95.             //不能在此处结束程序,因为我们要找的是N皇后问题的所有解,此时应该清除该行的皇后,从当前放置皇后列数的下一列继续探测。  
    96.             //_sleep(600);  
    97.             j = a[i] + 1;             //从最后一行放置皇后列数的下一列继续探测  
    98.             a[i] = INITIAL;           //清除最后一行的皇后位置  
    99.             continue;  
    100.         }  
    101.         ++i;              //继续探测下一行的皇后位置  
    102.     }  
    103. }  
    104.   
    105. int main(void)  
    106. {  
    107.     init();  
    108.     queen();  
    109.     system("pause");  
    110.     return 0;  
    111. }  

            下面的代码跟上面的代码差不多,只是稍微做了一些变化。。上面函数判断棋盘某个位置合法性的时候,valid函数里面的QUEEN可以修改为row的,只需要将前面row行与第row行进行比较就可以了,不需要将所有行都与第row进行比较的。。。下面的代码中的check函数中循环次数是k而不是皇后的个数就是这个原因。。。

    1. #include "iostream"  
    2. #include "cmath"  
    3. using namespace std;  
    4.   
    5. #define Max 20      //定义棋盘的最大值  
    6. int a[Max];  
    7. int show(int S)    //定义输出函数  
    8. {  
    9.     int i,p,q;  
    10.     int b[Max][Max]={0};     //定义并初始化b[][]输出数组  
    11.   
    12.     for(i=1;i<=S;i++)    //按横列i顺序输出a[i]数组坐标  
    13.     {  
    14.         b[i][a[i]]=1;  
    15.         printf("(%d,%d)\t",i,a[i]);  
    16.     }  
    17.     printf("\n");  
    18.     for(p=1;p<=S;p++)     //按棋盘的横列p顺序标明皇后的位置  
    19.     {  
    20.         for(q=1;q<=S;q++)  
    21.         {  
    22.             if(b[p][q]==1)     //在第p行第q列放置一个皇后棋子  
    23.                 printf("●");  
    24.             else  
    25.                 printf("○");  
    26.         }  
    27.         printf("\n");  
    28.     }  
    29.     return 0;  
    30. }  
    31.   
    32. int check(int k)    //定义check函数  
    33. {  
    34.     int i;  
    35.     for(i=1;i<k;i++)    //将第k行与前面的第1~~k-1行进行判断  
    36.     {  
    37.         if((a[i]==a[k]) || (a[i]-a[k]==k-i) || (a[i]-a[k]==i-k))    //检查是否有多个皇后在同一条直线上  
    38.         {  
    39.             return 0;  
    40.         }  
    41.     }  
    42.     return 1;  
    43. }  
    44.   
    45. void check_m(int num)    //定义函数  
    46. {  
    47.     int k=1,count=0;  
    48.     printf("The possible configuration of N queens are:\n");  
    49.     a[k]=1;  
    50.     while(k>0)  
    51.     {  
    52.         if(k<=num && a[k]<=num)    //从第k行第一列的位置开始,为后续棋子选择合适位子  
    53.         {  
    54.             if(check(k)==0)    //第k行的a[k]列不能放置皇后  
    55.             {  
    56.                 a[k]++;        //继续探测当前行的下一列:a[k]+1  
    57.             }  
    58.             else  
    59.             {  
    60.                 k++;         //第K行的位置已经确定了,继续寻找第k+1行皇后的位置  
    61.                 a[k]=1;      //从第一列开始查找  
    62.             }  
    63.         }  
    64.         else  
    65.         {  
    66.             if(k>num)     //若满足输出数组的要求则输出该数组  
    67.             {  
    68.                 count++;  
    69.                 printf("[%d]:  ",count);  
    70.                 show(num);    //调用输出函数show()  
    71.             }  
    72.             //如果k>num会执行下面两行代码,因为虽然找到了N皇后问题的一个解,但是要找的是所有解,需要回溯,从当前放置皇后的下一列继续探测  
    73.             //如果a[k]>num也会执行下面两行代码,就是说在当前行没有找到可以放置皇后的位置,于是回溯,从上一行皇后位置的下一列继续探测  
    74.             k--;      //棋子位置不符合要求,则退回前一步  
    75.             a[k]++;   //继续试探下一列位置  
    76.         }  
    77.     }  
    78.     printf("The count is: %d \n",count);  
    79. }  
    80.   
    81. int main(void)  
    82. {  
    83.     int N,d;  
    84.     //system("color 2a");  
    85.     do  
    86.     {  
    87.         printf("********************N皇后问题系统*********************\n\n");  
    88.         printf("                  1. 四皇后问题                        \n");  
    89.         printf("                  2. 八皇后问题                        \n");  
    90.         printf("                  3. N 皇后问题(N<20)                  \n");  
    91.         printf("                  4. 退出                              \n");  
    92.         printf("******************************************************\n");  
    93.         printf("\n    从数字1-4之间的数选择需要的操作\n\n"); /*提示输入选项*/  
    94.         printf("      请输入你要选择的功能选项:__\n");  
    95.         scanf("%d",&d);   
    96.         switch(d)  
    97.         {  
    98.         case 1:  
    99.             check_m(4);      //4皇后问题  
    100.             break;   
    101.         case 2:  
    102.             check_m(8);     //8皇后问题  
    103.             break;   
    104.         case 3:  
    105.             printf("请输入N的值:_");  
    106.             fflush(stdin);      //清除缓冲  
    107.             scanf("%d",&N);  
    108.             printf("\n");  
    109.             if(N>0&&N<20)  
    110.             {  
    111.                 check_m(N);    //N皇后问题  
    112.                 break;  
    113.             }  
    114.             else  
    115.             {  
    116.                 printf("输入错误,请从新输入:");  
    117.                 printf("\n\n");  
    118.                 break;   
    119.             }  
    120.         case 4:  
    121.             exit(0);     //程序结束  
    122.         }  
    123.     }while(1);  
    124.     system("pause");  
    125.     return 0;  
    126. }  

            递归解法:

    1. #include <stdio.h>  
    2. #include <stdlib.h>  
    3.   
    4. const int N=20;   //最多放皇后的个数  
    5. int q[N];         //各皇后所在的行号  
    6. int cont = 0;     //统计解得个数  
    7. //输出一个解  
    8. void print(int n)  
    9. {  
    10.     int i,j;  
    11.     cont++;  
    12.     printf("第%d个解:",cont);  
    13.     for(i=1;i<=n;i++)  
    14.         printf("(%d,%d) ",i,q[i]);  
    15.     printf("\n");  
    16.     for(i=1;i<=n;i++)        //行  
    17.     {                  
    18.         for(j=1;j<=n;j++)    //列  
    19.         {  
    20.             if(q[i]!=j)  
    21.                 printf("x ");  
    22.             else   
    23.                 printf("Q ");   
    24.         }  
    25.         printf("\n");  
    26.     }  
    27. }  
    28. //检验第i行的k列上是否可以摆放皇后  
    29. int find(int i,int k)    
    30. {  
    31.     int j=1;  
    32.     while(j<i)  //j=1~i-1是已经放置了皇后的行  
    33.     {  
    34.         //第j行的皇后是否在k列或(j,q[j])与(i,k)是否在斜线上  
    35.         if(q[j]==k || abs(j-i)==abs(q[j]-k))   
    36.             return 0;  
    37.         j++;  
    38.     }  
    39.     return 1;  
    40. }  
    41. //放置皇后到棋盘上  
    42. void place(int k,int n)    
    43. {  
    44.     int j;  
    45.     if(k>n)  
    46.         print(n);  
    47.     else  
    48.     {  
    49.         for(j=1;j<=n;j++)   //试探第k行的每一个列  
    50.         {  
    51.             if(find(k,j))  
    52.             {  
    53.                 q[k] = j;  
    54.                 place(k+1,n);  //递归总是在成功完成了上次的任务的时候才做下一个任务  
    55.             }  
    56.         }  
    57.     }  
    58. }  
    59.   
    60. int main(void)  
    61. {  
    62.     int n;  
    63.     printf("请输入皇后的个数(n<=20),n=:");  
    64.     scanf("%d",&n);  
    65.     if(n>20)  
    66.         printf("n值太大,不能求解!\n");  
    67.     else  
    68.     {  
    69.         printf("%d皇后问题求解如下(每列的皇后所在的行数):\n",n);  
    70.         place(1,n);        //问题从最初状态解起  
    71.         printf("\n");  
    72.     }  
    73.     system("pause");  
    74.     return 0;  
    75. }  

        二、使用位运算来求解N皇后的高效算法

       核心代码如下:

    1. void test(int row, int ld, int rd)  
    2. {  
    3.     int pos, p;  
    4.     if ( row != upperlim )  
    5.     {  
    6.         pos = upperlim & (~(row | ld | rd ));  
    7.         while ( pos )  
    8.         {  
    9.             p = pos & (~pos + 1);  
    10.             pos = pos - p;  
    11.             test(row | p, (ld | p) << 1, (rd | p) >> 1);  
    12.         }  
    13.     }  
    14.     else  
    15.         ++Ans;  
    16. }  

            初始化: upperlim =  (1 << n)-1; Ans = 0;

            调用参数:test(0, 0, 0);

             和普通算法一样,这是一个递归函数,程序一行一行地寻找可以放皇后的地方。函数带三个参数row、ld和rd,分别表示在纵列和两个对角线方向的限制条件下这一行的哪些地方不能放。位于该行上的冲突位置就用row、ld和rd中的1来表示。把它们三个并起来,得到该行所有的禁位,取反后就得到所有可以放的位置(用pos来表示)。

            p = pos & (~pos + 1)其结果是取出最右边的那个1。这样,p就表示该行的某个可以放子的位置,把它从pos中移除并递归调用test过程。

            注意递归调用时三个参数的变化,每个参数都加上了一个禁位,但两个对角线方向的禁位对下一行的影响需要平移一位。最后,如果递归到某个时候发现row=upperlim了,说明n个皇后全放进去了,找到的解的个数加一。


    注:
            upperlime:=(1 << n)-1 就生成了n个1组成的二进制数。
            这个程序是从上向下搜索的。
            pos & -pos 的意思就是取最右边的 1 再组成二进制数,相当于 pos &(~pos +1),因为取反以后刚好所有数都是相反的(怎么听着像废话),再加 1 ,就是改变最低位,如果低位的几个数都是1,加的这个 1 就会进上去,一直进到 0 ,在做与运算就和原数对应的 1 重合了。举例可以说明:

            原数 0 0 0 0 1 0 0 0    原数 0 1 0 1 0 0 1 1

            取反 1 1 1 1 0 1 1 1    取反 1 0 1 0 1 1 0 0
            加1    1 1 1 1 1 0 0 0    加1  1 0 1 0 1 1 0 1

      与运算    0 0 0 0 1 0 0 0    and  0 0 0 0 0 0 0 1
          其中呢,这个取反再加 1 就是补码,and 运算 与负数,就是按位和补码与运算。
           (ld | p)<< 1 是因为由ld造成的占位在下一行要右移一下;
           (rd | p)>> 1 是因为由rd造成的占位在下一行要左移一下。
            ld rd row 还要和upperlime 与运算 一下,这样做的结果就是从最低位数起取n个数为有效位置,原因是在上一次的运算中ld发生了右移,如果不and的话,就会误把n以外的位置当做有效位。
            pos 已经完成任务了还要减去p 是因为?
            while 循环是因为?
            在进行到某一层的搜索时,pos中存储了所有的可放位置,为了求出所有解,必须遍历所有可放的位置,而每走过一个点必须要删掉它,否则就成死循环啦!

             这个是目前公认N皇后的最高效算法。

    完整的代码如下:

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

            上述代码还是比较容易看懂的,但我觉得核心的是在针对试探-回溯算法所用的数据结构的设计上。
            程序采用了递归,也就是借用了编译系统提供的自动回溯功能。

            算法的核心:使用bit数组来代替以前由int或者bool数组来存储当前格子被占用或者说可用信息,从这可以看出N个皇后对应需要N位表示。
             巧妙之处在于:以前我们需要在一个N*N正方形的网格中挪动皇后来进行试探回溯,每走一步都要观察
    和记录一个格子前后左右对角线上格子的信息;采用bit位进行信息存储的话,就可以只在一行格子也就是(1行×N列)个格子中进行试探回溯即可,对角线上的限制被化归为列上的限制。
             程序中主要需要下面三个bit数组,每位对应网格的一列,在C中就是取一个整形数的某部分连续位即可。
     row用来记录当前哪些列上的位置不可用,也就是哪些列被皇后占用,对应为1。ld,rd同样也是记录当前哪些列位置不可用,但是不表示被皇后占用,而是表示会被已有皇后在对角线上吃掉的位置。这三个位数组进行“或”操作后就是表示当前还有哪些位置可以放置新的皇后,对应0的位置可放新的皇后。如下图所示的8皇后问题求解得第一步:
                  row:          [ ][ ][ ][ ][ ][ ][ ][*]
                  ld:             [ ][ ][ ][ ][ ][ ][*][ ]
                  rd:             [ ][ ][ ][ ][ ][ ][ ][ ]
                  --------------------------------------
                row|ld|rd:    [ ][ ][ ][ ][ ][ ][*][*]
            所有下一个位置的试探过程都是通过位操作来实现的,这是借用了C语言的好处,详见代码注释。

           关于此算法,如果考虑N×N棋盘的对称性,对于大N来说仍能较大地提升效率!
           位操作--对优化算法有了个新的认识

      这个是在csdn找到的一个N皇后问题最快的算法,看了好一会才明白,这算法巧妙之处我认为有2个:

           1、以前都是用数组来描述状态,而这算法采用是的位来描述,运算速度可以大大提升,以后写程序对于描述状态的变量大家可以借鉴这个例子,会让你的程序跑得更快                        

           2、描述每行可放置的位置都是只用row,ld,rd这3个变量来描述,这样使得程序看起来挺简洁的。

    展开全文
  • N皇后问题是指在N*N的棋盘上摆N个皇后,要求任何两个皇后不同行、不同列,也不在同一条斜线上。给定一个整数n,返回n皇后的摆法有多少种。 【举例】 n=1;返回1。 n=2或3,2皇后和3皇后问题无论怎么摆都不行,返回0...

    【题目】

    N皇后问题是指在N*N的棋盘上摆N个皇后,要求任何两个皇后不同行、不同列,也不在同一条斜线上。给定一个整数n,返回n皇后的摆法有多少种。

    【举例】

    n=1;返回1。
    n=2或3,2皇后和3皇后问题无论怎么摆都不行,返回0。
    n=8,返回92。

    【解答】

    如果在(i,j)位置(第i行第j列)放置了一个皇后,接下来在哪些位置可以放置皇后。
    1、整个第i行位置都不能放置。
    2、整个第j列位置都不能放置。
    3、如果位置(a,b)满足|a-i|==|b-j|,说明(a,b)与(i,j)处在同一条斜线上,也不能放置。

    把递归过程直接设计成逐行放置皇后的方式,可以避开条件1的那些不能放置的位置。接下来用一个数组保存已经放置的皇后位置,假设数组为record,record[i]的值表示第i行皇后所在的列数。在递归计算到第i行第j列时,查看record [0…k] (k<i)的值,看是否有j相等的值,若有,则说明(i,j)不能放置皇后,再看是否有|k-i| == |record[k]-j|,若有,也说明(i,j)不能放置皇后。

    public int num1(int n){
      if(n<1){
        return 0;
      }
      int[] record = new int[n];//初始化数组
      return process1(0,record,n);
    }
    
    
    
    public int process1(int i,int[] record,int n){
        if(i == n){
          return 1;
        }
        int res = 0;
        for(int j=0;j<n;j++){                           
          if(isValid(record,i,j++){                    //这一步是开始赋值,确定每一个棋位置
            record[i] = j;
            res += process1(i+1,record,n);             //递归
          }
        }
        return res;
    }
    
    
    
    public bolean isValid(int[] record,int i,int j){
      for(int k = 0;k<i;k++){
      //这是放置条件
      //1、整个第i行位置都不能放置。
      //2、整个第j列位置都不能放置。
      //3、如果位置(a,b)满足|a-i|==|b-j|,说明(a,b)与(i,j)处在同一条斜线上,也不能放置。
        if(j == record[k] || Math.abs(record[k]-j) == Math.abs(i-k)){
          return flase;
        }
      }
      return true;
    }
    

    【最优解】

    下面介绍最优解,基本过程与上面方法一样,但使用了位运算来加速。具体加速的递归过程中,找到每行还有哪些位置可以放置皇后的判断过程。因为整个过程比较自然,所以先列出代码,然后对代码进行解释。

    展开全文
  • N皇后问题(递归和动态规划

    千次阅读 2017-09-15 21:25:09
    N皇后问题是指N*N的棋盘要摆N个皇后,要求任何两个皇后不同行、不同列、也不在同一条斜线(两个皇后成45度)上。给定一个整数n,返回n皇后的摆法有多少种。 二:解题思路 如果在(i,j)位置(第i行第j列)放置...

    说明:内容摘录自左程云的《程序员代码面试指南》


    一:题目描述

    N皇后问题是指N*N的棋盘要摆N个皇后,要求任何两个皇后不同行、不同列、也不在同一条斜线(两个皇后成45度)上。给定一个整数n,返回n皇后的摆法有多少种。


    二:解题思路

    如果在(i,j)位置(第i行第j列)放置一个皇后,接下来在哪些位置不能放置皇后呢?

    1、整个第i行的位置都不能放置

    2、整个第j列的位置都不能放置

    3、如果位置(a,b)满足|a-i|==|b-j|,说明(a,b)与(i,j)处在同一条斜线上,也不能放置


    把递归过程直接设计成逐行放置皇后的方式,可以避开1的那些不能放置的位置。

    接下来用一个数组保存已经放置的皇后位置,假设数组为record,record[i]表示第i行皇后所在的列数。

    在递归计算到第i行第j列时,查看record[0..k](k<i)的值:

    1、看是否有j相等的值,若有说明(i,j)不能放置皇后,

    2、再看是否有|k-i|==|recor[k]-j|,若有,也说明(i,j)不能放置皇后。


    三:代码实现

    #include<iostream>
    #include<vector>
    using namespace std;
    
    bool isValid(int* record, int i, int j){
    	for (int k = 0; k < i;k++)
    	if (j == record[k] || abs(record[k] - j) == abs(i - k))
    		return false;
    	return true;
    }
    
    int process(int i, int* record, int n){
    	if (i == n)  //搜索完所有行,说明本次方案可以满足皇后的摆法
    		return 1;
    
    	int res = 0;
    
    	for (int j = 0; j < n; j++){  //对于第i行,每一列都可能是皇后的摆放位置
    		if (isValid(record, i, j)){ //如果该列满足条件,递归寻找下一行皇后可以摆放的位置
    			record[i] = j;
    			res += process(i + 1, record, n);
    		}
    	}
    	return res;
    }
    int num1(int n){
    	if (n < 1)
    		return 0;
    	int * record = new int[n]; //保存每一行皇后保存的列数
    	int res = process(0, record, n);
    
    	delete record;
    	return res;
    
    }
    int main(){
    
    	int n = 8;
    	for (int n = 1; n < 16;n++)
    		cout <<n<<"皇后	的摆法:"<< num1(n) << endl;
    
    	system("pause");
    	return 0;
    }

    N从1-15的结果(等呀等~):
    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


    展开全文
  • 题目:在8×8的国际象棋上摆放八个皇后,使其不能相互攻击,即任意两个皇后不得处在同一行、同一列或者同一对角斜线上。下图中的每个黑色格子表示一个皇后,这就是一种符合条件的摆放方法。请求出总共有多少种摆法。...

    题目:在8×8的国际象棋上摆放八个皇后,使其不能相互攻击,即任意两个皇后不得处在同一行、同一列或者同一对角斜线上。下图中的每个黑色格子表示一个皇后,这就是一种符合条件的摆放方法。请求出总共有多少种摆法。(leetcode51、52)
    leetcode代码网址:https://github.com/vivianLL/LeetCode

    解法一:回溯法

    由于每次都是遍历下一行,所以两个皇后的行肯定不同;因此判断当前列是否已经占用,和判断对角线的位置。
    用三个数组来表示列、正反对角线的占用情况。一行行的遍历,如果没有冲突就把相应的位置置为占用,继续处理下一行,并记录改行的皇后放在了哪一列,当皇后都放完后,根据记录的列号来拼出结果。进行回溯时要把占用的位置还回去。对角线位置的计算要小心(尤其是反对角线),可以把顶点带进去计算验证一下。
    python实现如下:

    def totalNQueens(self, n: int) -> int:
        self.col = [False] * n
        self.diag = [False] * (2 * n)
        self.anti_diag = [False] * (2 * n)
        self.result = 0
        # self.result = []
        self.recursive(0, n, [])
        return self.result
    
    def recursive(self, row, n, column):
        if row == n:
            self.result += 1
            # self.result.append(list(map(lambda x: '.' * x + 'Q' + '.' * (n - 1 - x), column)))
        else:
            for i in range(n):
                if not self.col[i] and not self.diag[row + i] and not self.anti_diag[n - i + row]:
                    self.col[i] = self.diag[row + i] = self.anti_diag[n - i + row] = True
                    self.recursive(row + 1, n, column + [i])
                    self.col[i] = self.diag[row + i] = self.anti_diag[n - i + row] = False
    

    解法二:位运算

    首先,我们的基本思路与传统一样,每一行只能放并且必须放一个皇后。每次放置一个皇后之后,它就会对后面所有行中,可能放置皇后的位置产生影响。如下图所示,我们已经放置了三个皇后Q1,Q2,Q3。 接着在下面一行放置Q4时,用彩色标注出的区域都是不可行的方案,会与已经放置的三个皇后产生冲突。
    在这里插入图片描述
    这个冲突其实有三种不同的情况,我们用三个变量A,B,C分别来表示这三种不同的冲突。这三个变量都是一个八位的二进制数,这八位中,为1的表示有冲突,为0表示没有冲突。

    1. 与已放置的皇后处于同一列中;
      我们用B表示这种冲突。例如在图中,第四行会有三个位置因为列攻击而不能再放置皇后(图中大红色方块),因此A = 1000 1001。
    2. 与已放置的皇后处于同一左斜(指向右下方)对角线中;
      我们用A表示这种冲突。例如在图中,蓝色方块所表示的位置,分别是由于Q1和Q2的左斜对角线上的攻击而不能够放置新的皇后, 因此B = 0001 0010。
    3. 与已放置的皇后处于同一右斜(指向右上方)对角线中。
      我们用C表示这种冲突。例如图中粉色方块, 是由Q2的右斜对角线的攻击造成的。因此C = 0010 0000。

    有了A,B,C,三个变量,我们很容易求出当前这一行中,有哪些位置是可以放置皇后的。这个变量我们用D来表示,我们可以写出D = ~(A|B|C)。D中为1的那些位置则是我们可以放置皇后的位置。在上图的情况下,D = 0100 0100。
    此时,我们有两个可能的放置皇后的位置,那么要如何取出第一个位置呢?这里有一个技巧。我们用bit表示可能的一个位置,使用bit = D & (-D)即可取出D中最右边的一个1。例如D = 0100 0100,则-D = 10111100(注意计算机中的数都是补码)。而bit = D & (-D) = 0000 0100 取出了最右边的那个1。
    注意这个结果中,除了最右 n 位以外,左边的位中也会有一些 1,这些 1 是多余的,应当去掉。怎么去掉呢?可以用一个最右 n 位为 1、其它位为 0 的 bit array 与上述结果进行与运算,而这个 bit array 可以用 (1 << n) - 1 这个表达式制造出来。
    最后还有一点,如何递归?递归中传入的参数(也即A,B,C)该如何设定?其实也很简单,特别是对于列冲突变量B来说,只要使用B|bit即可表示下一行列冲突的情况,对于A,采用(A|bit)<<1,对于C,采用(C|bit>>1)即可表示下一行中,对角线冲突的情况。
    (0按位取反为-1,-1按位取反为0,-1和任何数按位与的结果是任何数,1与任何数按位与的结果是1)
    python代码如下:

    def totalNQueens(self, n: int) -> int:
        self.count = 0
    
        def DFS(n, row, cols, pie, na):
            bits = (~(cols | pie | na)) & ((1 << n) - 1)  # 可以放置皇后的位置,对按列冲突、按左右斜对角线冲突的位置取反
            while bits:
                p = bits & -bits       # 取出可以放置皇后的位置中最右边的一个1
                if row == n - 1:
                    self.count += 1
                else:
                    DFS(n, row + 1, cols | p, (pie | p) << 1, (na | p) >> 1)  # 下一行中列、左斜对角线、右斜对角线冲突的情况
                bits = bits & (bits - 1)
        DFS(n, 0, 0, 0, 0)
        return self.count
    

    参考网址:
    LeetCode N-Queens
    八皇后问题优雅解法——位运算
    10394 用位运算速解 n 皇后问题 (非常好)

    展开全文
  • N皇后问题是指在N×N的棋盘上要摆N个皇后,要求任何两个皇后不同行、不同列,也不在同一条斜线上。给定一个整数N,返回N个皇后的摆法有多少种。基本思路:1.递归方法。如果在位置(i,j)放置了一个皇后,那么那些...
  • 这里的n皇后问题指在一个nxn的棋盘上放置n个棋子,使得每行每列和每条对角线上都只有一个棋子,求其摆放的方法数。 给定一个int n,请返回方法数,保证n小于等于10 import java.util.*; public class ...
  • n皇后问题

    2015-10-03 10:29:04
    //1 分治法 2 回溯法 3 动态规划 4 贪心算法 ...//回溯法-----n皇后问题 //动态规划--- //分治法----- #include using namespace std; //回溯法求解N皇后问题 //************判断当前位置是否可以放置皇后******
  • 皇后问题---动态规划

    千次阅读 2019-03-27 18:31:48
    做了好多动态规划的题目,有了一些心得。 public int getanswer(char[][] map,int index,int n) { if(index==n) {// index==n 则意味的递归结束 /*System.out.println("-------------"); for(int i=0;i<...
  • 回溯法——N皇后问题与TSP问题 对于一般的问题而言,很多时候无法找到其最优子结构性质或者其不是一个最优化问题,这些问题都是NP的。我们无法采用像动态规划一样的技巧简化求出某个具体解的过程,唯一能做的就是蛮...
  • [动态规划]python解决N皇后问题(20行代码) 如果读者对于回溯算法思路解法还不是很了解,可以先点击链接查阅我之前的一篇博文《算法之【回溯算法】详解》,很详细的介绍了回溯算法求解思路及方法,有利于你更好的学习...
  • N皇后问题--回溯算法的经典实例

    万次阅读 2016-04-11 16:50:44
    问题描述: 皇后是国际象棋中威力最大的棋子。在下面所示的棋盘上,皇后可以攻击位于箭头所覆盖位置的所有棋子。我们能不能把N皇后放在棋盘(N×N)上,...回溯算法作为五大常用算法:动态规划算法,贪婪算法,分治算
  • 文章目录题目:最长上升子序列输入输出解法: 动态规划 O(n^2)输入输出解法 动他规划 O(nlogn)题目: 最大子列和输入输出解法: 动态规划题目: n皇后问题输入输出解法: 回溯 - 剪枝 O(n!)AC代码题目:图的着色问题...
  • 1. 回溯问题 回溯就是穷举法的一种,也就是举出所有可能性。 回溯法的思路: 1.如果当前节点放入数据An满足要求,那么继续检查下一个节点是否可以加入A1-An中的其他数据 2.如果当前节点不满足要求,直接放下一个数据...
  • 类似于八皇后问题: 有N个人,对应N种工作的能力,但是各自能力有高低, 要把这N个人分配到这N种工作中去,每个人对应一个工作,想要找到一个...能够用遍历或者递归实现,但是想问能不能通过贪心或者动态规划来实现。
  • 回溯相关练习51.N皇后利用回溯算法求解 0-1 背包问题三、分治1.分治的概念2.分治算法的基本步骤3.分治相关练习利用分治算法求一组数据的逆序对个数四、动态规划1. 动态规划的概念2.基本思想与策略3. 适用的情况4....
  • 那么看到这三种算法,你应该有所出现: 贪心法是动态规划法的特例,如0-1背包,最小代价生成...回溯法是比动态规划法更加一般的算法,如n皇后,子集和数问题 那么,这三种有什么区别呢? 首先,这些方法所要解决
  • 五大常用算法:分治、动态规划、贪心、回溯和分支界定 这五种算法引出了很多问题。慢慢的更新链接!   动态规划的五个典型算法:动态规划  1.最大连续子序列之和 ...回溯法: N皇后问题 ...
  • //N皇后,8皇后的问题,主要就是皇后每一行只允许存在一个,而且皇后斜方向不允许同时存在 //所以循环递归每一行,然后每一行都于前面的皇后进行冲突比较,有冲突的情况就不递归 function queen(a, cur) { if (cur ...
  • N皇后问题其实就是回溯算法中的一个典型应用 回溯算法定义 回溯算法实际上一个类似枚举的搜索尝试过程,主要是在搜索尝试过程中寻找问题的解,当发现已不满足求解条件时,就“回溯”返回,尝试别的路径。回溯法是一...
  • 回溯法解n纸币凑数问题

    千次阅读 2016-11-03 19:56:22
    前言:我们都知道动态规划算法的一个经典案例是0-1背包问题。其中这个问题求的是最优解(即最大解)。然后现在有这么一种情况:设有n张面值不一定相等的纸币,其面值为Vi(0 举个栗子: 现在有6张纸币。其面值Vi序列...
  • 神奇的口袋(背包问题):动态规划或者穷举组合数 数列(类似斐波那契):图形分解,找规律再打印 吃糖果(类似斐波那契):直接修改斐波那契数列算法 问题 D: 八皇后 详细设计参考N皇后全...
  • 报告包括背包问题、装载问题、N皇后问题、作业调度问题等,供学习参考使用。算法分析与设计复习:分治法、动态规划、贪心算法、回溯法、分支限界法比较重要。博客中有些复习总结。(ง •̀_•́)ง
  • 算法设计分析题库四

    多人点赞 2020-07-04 08:41:24
    A N皇后问题 B 最小花费生成树问题 C 单源最短路径问题 D背包问题 3、单选 下列算法中不能解决0/1背包问题的是( C )。 A分支限界法 B回溯法 C贪心法 D动态规划 4、单选 贪心算法与动态规划算法的主要区别是( ...
  • 本文主要赘述的是非树和图的DFS和BFS ...动态规划和回溯法也有类似的题目,但是动态规划一般都是有始有终,回溯法基本就是N皇后类型的问题。 在这种网格中,完成点i,j的相关操作后,有周边的四个位置决定可...
  • 经典算法(C语言版).rar

    2020-04-01 11:00:13
    内含排序、递归、百鸡问题、迪杰斯特拉、动态规划—背包、水仙花数、蛮力背包、N皇后问题、斐波那契数、马踏斜日递归等......
  • 算法分析与设计;填空题;选择题;4. 贪心算法与动态规划算法的共同点是 A.重叠子问题 B.构造最优解 C.贪心选择性质 D.最优子结构性质 5....单源最短路径问题 B.N皇后问题 C.最小代价生成树问题 D.背包问题 7
  • 本科实验报告 课程名称 算法设计与分析 实验项目分治法合并排序 贪心法作业调度 动态规划法求多段图问题 回溯法求 n 皇后问题 实验地点 致远楼 B503 专业班级 学号 学生 指导教师 2017 年 3 月 18 日 实验 1 分治法...

空空如也

空空如也

1 2 3 4
收藏数 62
精华内容 24
关键字:

动态规划n皇后问题