N皇后问题

Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other)

Total Submission(s) : 11 Accepted Submission(s) : 3

Font: Times New Roman | Verdana | Georgia

Font Size: ← →

Problem Description

Input

Output

Sample Input

1
8
5
0

Sample Output

1
92
10

Author

Source

思路分析：

本题用到了递归，一遇到递归就头疼，不知道递归到哪里去了。针对该题，我把N=4的情况，把递归完全跑了一遍，在纸上画来画去，终于对该题递归的过程有了一定的理解。在递归的同时也进行回溯。下面代码中行数和列数均是从0开始的。这里写思路为了好理解，我们认为行数和列数均是从1开始的。整体思路是一行一行的放，在每一行中一列一列的放。这里的n设为4，先放第一行，从第一列开始，外层一个循环，从第1列到第n列，但是程序还没有跑到第n列（这里，第一行放在第一列就符合题意），代码中一个递归，就跳到第二行里去了search(1+1)，该放第二行了，外层一个循环，从第1列到第n列，再用一个for循环检查放的位置是否合适，第二行放在第一列肯定不行（和第一行同列），放在第二列也不行（和第一行对角线），放在第三列可以，这时候外层循环也没有跑完，就进入了一个新的递归，跳到第三行里去了search(2+1)，该放第三行了，外层一个循环，放在第一列不行，第二列也不行，第三列也不行，第四列也不行。循环结束，没有执行里面的search(3+1)，第三行哪里也不能放，回溯，又跑到第二行的状态去，还记得第二行里面的那个外层循环没有跑完吗，上面跑到了第三列，于是接着循环，放在第四列，可以放，又进入一个新的递归，search(2+1)，即刚才说的哪里都不能放的第三行，又一个循环，从第一列开始放，第一列不行，第二列可以，这时候在第三行外层循环在第二列的时候，又进入了新的递归search(3+1)，寻找下一行，接着又一个外循环。。。。如果不行，又跳到第三行。。。接下来就不说了，已经说了这么多，大体的流程就是这样的，不断的递归，不断的回溯，（因为上一行的循环还没有执行完）。

代码：

#include 
  
   
#include 
   
     using namespace std; int c[11],tot,n; void search(int cur)//不符合条件就回溯 { int i,j; if(cur==n) tot++;//当search(n-1)时也成功，说明有符合题意的情况，所以search(n-1)里面有search(n)执行时，tot++ else for(i=0;i
    
     >n&&n) { cout<