N皇后问题回溯法 C/C++

一:问题描述

　　N皇后问题（含八皇后问题的拓展，规则同四皇后）：在N*N的棋盘上，放置N个皇后，要求每一横行每一列，每一对角线上均只能放置一个皇后，求解可能的方案及方案数。

二：代码及结果如下

 1 #include<stdio.h>
 2 #define N 4
 3 //假设第i个皇后所在位置为(i,xi)
 4 //x[N]数组中存放所得解
 5 
 6 void  place(int t,int x[])    //递归判断第t层是否有解
 7 {
 8     int xi;
 9     if(t>N)
10     {
11         for(xi=1;xi<=N;xi++)
12         {
13         printf("%d
",x[xi]);
14         }
15         printf("
");
16     }
17     else
18     {
19         for(int xi=1;xi<=N;xi++)
20         {
21             for(int j=1;j<t;j++)
22             {
23                 if(xi==x[j]) break; //同一列的排除
24                 if((j-t)!=(xi-x[j]) && (j-t)!=(x[j]-xi) && j==(t-1))
25                 {
26                     x[t]=xi;
27                     place(t+1,x);
28                 }
29             }
30         }
31     }
32 }
33 
34 
35 void main()
36 {
37     int x[N+1]={0,0,0,0,0},k=0;
38     for(x[1]=1;x[1]<=N;x[1]++)
39     {
40         place(2,x);
41     }
42 }

//*********************运行结果****************************//

N皇后问题 回溯法 C/C++

N皇后问题回溯法 C/C++