程序填空题：求解n皇后问题（递归回溯法）
在n×n的方格棋盘上，放置n个皇后，要求每个皇后不同行、不同列、不同左右对角线。如下图所示是6皇后问题的一个解。
```c++
#include
#include
#define N 20 //最多皇后个数
int q[N]; //存放各皇后所在的列号,即(i,q[i])为一个皇后位置
void dispasolution(int n) //输出n皇后问题的一个解
{
for (int i=1;i<=n;i++)
printf("(%d,%d)",i,q[i]);
printf("\n");
}
bool place(int i,int j) //测试(i,j)位置能否摆放皇后
{
if (i==1) return true; //第一个皇后总是可以放置
int k=1;
while (k { if ((q[k]==j) || (abs(q[k]-j)==abs(i-k)))
;
k++;
}
;
}
void queen(int i,int n) //放置1～i的皇后
{ if (i>n)
dispasolution(n); //所有皇后放置结束
else
{
for (int j=1;j<=n;j++) //在第i行上试探每一个列j
if () //在第i行上找到一个合适位置(i,j)
{ q[i]=j;
;
}
}
}
int main()
{ int n; //n为存放实际皇后个数
scanf("%d",&n);
if (n<=20)
queen(1,n); //放置1～i的皇后
return 0;
}
```
### 输入格式:
输入n。
### 输出格式:
按行输出每组解。
### 输入样例1:
```in
6
```
### 输出样例1:
```out
(1,2)(2,4)(3,6)(4,1)(5,3)(6,5)
(1,3)(2,6)(3,2)(4,5)(5,1)(6,4)
(1,4)(2,1)(3,5)(4,2)(5,6)(6,3)
(1,5)(2,3)(3,1)(4,6)(5,4)(6,2)
```
答案：
第1空：return false
第2空：return true
第3空：place(i,j)
第4空：queen(i+1,n)
```c++
#include
#include
#define N 20 //最多皇后个数
int q[N]; //存放各皇后所在的列号,即(i,q[i])为一个皇后位置
void dispasolution(int n) //输出n皇后问题的一个解
{
for (int i=1;i<=n;i++)
printf("(%d,%d)",i,q[i]);
printf("\n");
}
bool place(int i,int j) //测试(i,j)位置能否摆放皇后
{
if (i==1) return true; //第一个皇后总是可以放置
int k=1;
while (k
;
k++;
}
;
}
void queen(int i,int n) //放置1～i的皇后
{ if (i>n)
dispasolution(n); //所有皇后放置结束
else
{
for (int j=1;j<=n;j++) //在第i行上试探每一个列j
if () //在第i行上找到一个合适位置(i,j)
{ q[i]=j;
;
}
}
}
int main()
{ int n; //n为存放实际皇后个数
scanf("%d",&n);
if (n<=20)
queen(1,n); //放置1～i的皇后
return 0;
}
```
### 输入格式:
输入n。
### 输出格式:
按行输出每组解。
### 输入样例1:
```in
6
```
### 输出样例1:
```out
(1,2)(2,4)(3,6)(4,1)(5,3)(6,5)
(1,3)(2,6)(3,2)(4,5)(5,1)(6,4)
(1,4)(2,1)(3,5)(4,2)(5,6)(6,3)
(1,5)(2,3)(3,1)(4,6)(5,4)(6,2)
```
答案：
第1空：return false
第2空：return true
第3空：place(i,j)
第4空：queen(i+1,n)
