精华内容
下载资源
问答
  • 动态规划 N皇后问题 人工智能作业,vc 6.0
  • 题目:在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皇后问题

    千次阅读 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皇后问题所有的解,此时应该清除该行的皇后,从当前放置皇后列数的下一列继续探测。

    完整的代码如下:

    [cpp]  view plain copy
    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而不是皇后的个数就是这个原因。。。

    [cpp]  view plain copy
    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. }  

            递归解法:

    [cpp]  view plain copy
    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皇后的高效算法

       核心代码如下:

    [cpp]  view plain copy
    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皇后的最高效算法。

    完整的代码如下:

    [cpp]  view plain copy
    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<=10)的国际象棋棋盘,要求将n个皇后放置于该国际象棋棋盘中,要求任意两个皇后不在同一行,不在同一列,也不在同一条对角线上,那么请问有多少种方法? 样例输入: 4 ...

    经典问题-N皇后

    问题描述
    给定一个n*n(n<=10)的国际象棋棋盘,要求将n个皇后放置于该国际象棋棋盘中,要求任意两个皇后不在同一行,不在同一列,也不在同一条对角线上,那么请问有多少种方法?
    样例输入:
    4
    样例输出:
    2
    问题分析:
    此题是经典的dp(动态规划)题,所以我们用动态规划来解决这一道题。
    我们可以用一个数组 x [ t ] 来表示第 t 行的皇后所在的列是第 x [ t ] 列(数组x 的值表示列数),然后进行一行一行的判断,如果最后一行可以放置皇后,那么就让sum++ 来记录放置皇后成功的次数,如果是没有走到最后一行,并且第 t 行的皇后无法放置之后,就再将上一行的皇后向右移动判断是否可以放置,最后,要保证皇后不能走出棋盘。
    下面是C++代码。

    #include <iostream>
    #include <stdlib.h>
    using namespace std;
    
    int n, sum = 0, x[11];// x 这个数组对应的值代表第几个皇后所在的列  
    
    int place(int k)
    {
    	int i;
    	for (i = 1; i < k; i++)
    	{
    		if (abs(k - i) == abs(x[k] - x[i]) || x[k] == x[i])// 判断是否在同一对角线的过程
    		{
    			return 1;// 此列不能放置皇后 
    		}
    	}
    	return 0;
    }
    
    int queen()
    {
    	x[1] = 0;
    	int t = 1;// t 代表放置的第几个皇后 
    	while (t > 0)
    	{
    		x[t] += 1;
    		while (x[t] <= n && place(t) == 1)// 如果此列不能放置皇后 ,那么就继续向右走 
    		{
    			x[t]++;
    		}
    		if (x[t] <= n)// 如果第 t 个皇后在棋盘内 
    		{
    			if (t == n)// 第 t 个皇后在最后一行放置 ,记录数据 
    			{
    				sum++;
    			}
    			else//继续向下走 并且将下一行归零 
    			{
    				t++;
    				x[t] = 0;
    			}
    		}
    		else// 如果不在棋盘内 就返回上一行 让上一行的皇后向右移动一个位置 
    		{
    			t--;
    		}
    	}
    	return sum;
    }
    
    int main()
    {
    	int count;
    	cin >> n;
    	count = queen();
    	cout << count;
    	return 0;
    }
    
    展开全文
  • 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列)放置...
  • /* * @Author: sober * @Date: 2021-08-18 16:07:43 * @LastEditTime: 2021... * @Description: N Queen Problem * @FilePath: \vscode_coding\C++\N_Queen_Problem.cpp */ #include<iostream> #include<.
  • 问题:设计一种算法,打印八皇后在8*8棋盘上的各种摆法,其中每个皇后都不同行、不同列,也不在对角线上。这里的“对角线”指的是所有的 对角线,不只是平分整个棋盘的那两条对角线。 分析:这个问题是在《算法设计...
  • #include #include #define N 4 using namespace std;...int x[N+1],fg,k,i,s,n,j; n=N;i=1;x[i]=1;s=0; while(1) { fg=1; for(k =i-1;k>=1;k--) { if(x[i]==x[k]||abs(x[i]-x[k])==i-k)
  • N皇后问题

    2020-04-20 12:42:10
    n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。 解题思路: 搜索空间是子集树。 整个棋盘的第一列肯定都存在可能的,所以需要循环遍历。 逐个判断位置是否合法。 到达...
  • N皇后问题是指在N×N的棋盘上要摆N个皇后,要求任何两个皇后不同行、不同列,也不在同一条斜线上。给定一个整数N,返回N个皇后的摆法有多少种。基本思路:1.递归方法。如果在位置(i,j)放置了一个皇后,那么那些...
  • n皇后问题

    2019-09-07 18:10:17
    N*N的方格棋盘放置了N皇后,使得它们不相互攻击(即任意2个皇后不允许处在同一排,同一列,也不允许处在与棋盘边框成45角的斜线上。 你的任务是,对于给定的N,求出有多少种合法的放置方法。 Input 共有若干...
  • 皇后问题---动态规划

    千次阅读 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皇后问题指在一个nxn的棋盘上放置n个棋子,使得每行每列和每条对角线上都只有一个棋子,求其摆放的方法数。 给定一个int n,请返回方法数,保证n小于等于10 import java.util.*; public class ...
  • 算法题解:N皇后问题(JAVA代码) n皇后是把n个棋子皇后放在n×n棋盘上,这样就不会有两个皇后互相攻击。 例如,下面是4皇后问题的解决方案。 设计一个算法,输出在4*4的棋盘上,4皇后问题的解决方案。 ...
  • Python|回溯算法解n皇后问题

    千次阅读 2020-07-18 00:00:00
    欢迎点击「算法与编程之美」↑关注我们!本文首发于微信公众号:"算法与编程之美",欢迎关注,及时了解更多此系列文章。欢迎加入团队圈子!与作者面对面!直接点击!问题描述给定一...
  • n皇后问题 java现在已成为最热门的编程语言,我自己也在学习java,在学习java的过程中,最难的应该莫过于算法了。今天来玩一下n皇后问题,也算是记录自己在算法学习中的成长足迹,通过博客可以促进博主与阅读者的...
  • n-皇后问题

    千次阅读 2019-06-14 23:23:02
    n-皇后问题是指将 n 个皇后放在 nn 的国际象棋棋盘上,使得皇后不能相互攻击到,即任意两个皇后都不能处于同一行、同一列或同一斜线上。 现在给定整数n,请你输出所有的满足条件的棋子摆法。 输入格式 共一行,...
  • N皇后问题及答案解

    2021-01-07 23:03:25
    在一张NN的国际象棋棋盘上,放置N皇后,使得所有皇后都无法互相直接攻击得到,(皇后可以直接攻击到她所在的横行,竖列,斜方向上的棋子),现在输入一个整数N,表示在NN的棋盘上放N皇后,请输出共有多少种...
  • 应用搜索原理解n皇后问题算法分析及优化。对n皇后问题的另一种理解。
  • N皇后问题--回溯算法的经典实例

    万次阅读 2016-04-11 16:50:44
    问题描述: 皇后是国际象棋中威力最大的棋子。在下面所示的棋盘上,皇后可以攻击位于箭头所覆盖位置的所有棋子。我们能不能把N皇后放在棋盘(N×N)上,...回溯算法作为五大常用算法:动态规划算法,贪婪算法,分治算
  • [动态规划]python解决N皇后问题(20行代码) 如果读者对于回溯算法思路解法还不是很了解,可以先点击链接查阅我之前的一篇博文《算法之【回溯算法】详解》,很详细的介绍了回溯算法求解思路及方法,有利于你更好的学习...
  • 1.动态规划法: 基本思想也是将待求解问题分解成若干个子问题,先求解子问题,然后从这些子问题的解得到原问题的解,以自底向上的方式解各子问题。 2.分治法问题: 将一个难以直接解决的大问题,分割成一些规模较小...
  • 回溯法——N皇后问题与TSP问题 对于一般的问题而言,很多时候无法找到其最优子结构性质或者其不是一个最优化问题,这些问题都是NP的。我们无法采用像动态规划一样的技巧简化求出某个具体解的过程,唯一能做的就是蛮...
  • 回溯算法详解 回溯算法框架。...如果你不理解这三个词语的解释,没关系,我们后面会用「全排列」和「N 皇后问题」这两个经典的回溯算法问题来帮你理解这些词语是什么意思, 代码方面,回溯算法的框架:...
  • 回溯算法—n皇后问题

    千次阅读 多人点赞 2015-10-11 22:36:01
    回溯是搜索算法中一种控制策略,基本思想是:为了求得问题的解,先选择某一种可能情况向前探索,在探索过程中,一旦发现原来的选择是错误的,就退回一步重新选择,继续向前探索,如此反复进行,直至得到解或证明无解...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 3,001
精华内容 1,200
关键字:

动态规划n皇后问题