[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;
}
```
