[TOC]
# 问题描述
在n\*n的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或者同一列或者同一斜线上的棋子。n后问题等价于在n\*n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
* 举例4\*4的棋盘
以上两种情况不满足题目的要求。
而这是其中的一种解。对于任何一个棋子都满足在同行同列同一斜线都没有其他棋子。
# 算法设计
发生错误的条件一共有以上图中的三种情况：
* 同行 ：(2,2)和(2,6) R1 = R2
* 同列 ：(4,3)和(7,3) C1 = C2
* 同一斜线 : (3,4)和(7,8) |R1-R2| = |C1-C2|
这里我们需要一个辅助函数通过返回ture和false来判断某一个位置是否合法。
```
Boolean QueenSafe(row,col) {
for(i=1 to n)
if(board[row][i] has a queen ||board[i][col] has a queen ) return false;
reset = min(row,col) - 1;
for(i=row-reset,j=col-reset;i<=n && j<=n;i++,j++)
if(board[i][j] has a queen) retrun false;
for(i=row-reset,j=col+reset;i<=n && j>0;i++,j--)
if(board[i][j] has a queen) retrun false;
}
```
伪代码：
```
void NqueenBacktrack(row,n) {
for(i=0 to n)
if(QueenSafe(row,i))
board[row][i] = true; //place a queen
if(row == n) print board;
else NqueenBacktrack(row+1,n);
}
```
# 代码实现-1
```
#include <stdio.h>
#define NSIZE (4)
#define true (1)
#define false (0)
int board[NSIZE][NSIZE]={0};
int
min(int n,int m) {
return n>=m ? m : n;
}
int
QueenSafe(int row,int col) {
int i,j;
int reset = min(row,col) - 1;
for(i=0;i<NSIZE;i++)
if(board[row][i] == 1 || board[i][col] == 1) return false;
for(i=row-reset,j=col-reset;i<NSIZE && j<=NSIZE;i++,j++)
if(board[i][j]==1) return false;
for(i=row-reset,j=col+reset;i<NSIZE && j>0;i++,j--)
if(board[i][j] == 1) return false;
return true;
}
int
NqueenBacktrack(int row,int n) {
int i,j;
for(i=0;i<n;i++) {
if(QueenSafe(row,i)) {
board[row][i] = true;
if(row == n-1) return true;
else {
NqueenBacktrack(row+1,n);
}
}
}
}
int
main(void) {
int i,j;
NqueenBacktrack(0,NSIZE);
for(i=0;i<NSIZE;i++){
for(j=0;j<NSIZE;j++) {
printf("%d ",board[i][j]);
}
printf("\n");
}
}
```
# 代码实现版本-2
```
#include <stdio.h>
int sum = 0;
int isSafe(int row,int col,int a[]) {
int i;
for(i=0;i<row;i++) {
if(a[i] == a[row] || abs(a[i]-a[row]) == abs(i-row)) return 0;
}
return 1;
}
void queen(int row,int n,int a[]) {
int i,j;
if(row == n) {
for(j=0;j<n;j++) printf("%d-%d\n",j,a[j]);
printf("---------\n");
sum++;
}
else {
for(i=0;i<n;i++) {
a[row] = i;
if(isSafe(row,i,a)) {
//printf("%d-%d\n",row,i);
queen(row+1,n,a);
}
}
}
}
int
main(void) {
int n;
scanf("%d",&n);
int a[n];
queen(0,4,a);
printf("%d",sum);
return 0;
}
```
# 代码实现版本-3
```
#include <stdio.h>
int
min(int n,int m) {
return n>=m ? m : n;
}
int isSafe(int row,int col,int board[][4],int n) {
int i,j;
int reset = min(row,col) - 1;
for(i=0;i<n;i++)
if(board[row][i] == 1 || board[i][col] == 1) return 0;
for(i=row-reset,j=col-reset;i<n && j<n;i++,j++)
if(board[i][j]==1) return 0;
for(i=row-reset,j=col+reset;i<n && j>0;i++,j--)
if(board[i][j] == 1) return 0;
return 1;
}
void queen(int row,int n,int a[][4]) {
int i,j,p;
for(i=0;i<n;i++) {
if(isSafe(row,i,a,n)) {
a[row][i] = 1;
printf("%d-%d\n",row,i);
if(row == n) {
for(j=0;j<n;j++) {
for(p=0;p<n;p++) {
printf("%d",a[j][p]);
}
}
}else {
queen(row+1,n,a);
}
}
printf("\n----\n");
a[row][i] = 0;
}
}
int
main(void) {
int n;
scanf("%d",&n);
int a[4][4] ={0};
queen(0,4,a);
return 0;
}
```
