1295 N皇后問題

1295 N皇后問題

?

時間限制: 2 s

空間限制: 128000 KB

題目等級 : 黃金 Gold

題目描述 Description

在n×n格的棋盤上放置彼此不受攻擊的n個皇后。按照國際象棋的規則，皇后可以攻擊與之處在同一行或同一列或同一斜線上的棋子。n后問題等價于再n×n的棋盤上放置n個皇后，任何2個皇后不妨在同一行或同一列或同一斜線上。

輸入描述 Input Description

?給定棋盤的大小n (n ≤ 13)

輸出描述 Output Description

?輸出整數表示有多少種放置方法。

樣例輸入 Sample Input

8

樣例輸出 Sample Output

92

#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<iomanip>
using namespace std;
bool d[100]= {0},b[100]= {0},c[100]= {0};
int sum=0,a[100];
int search(int);
int n;
int print();
int main() 
{cin>>n;search(1);  cout<<sum;                                                        //從第1個皇后開始放置
}
int search(int i) 
{int j;for (j=1; j<=n; j++)                                            //每個皇后都有8位置(列)可以試放if ((!b[j])&&(!c[i+j])&&(!d[i-j+7]))                   //尋找放置皇后的位置{ //由于C++不能操作負數組，因此考慮加7//放置皇后,建立相應標志值a[i]=j;                                                          //擺放皇后b[j]=1;                                                         //宣布占領第j列c[i+j]=1;                                                      //占領兩個對角線d[i-j+7]=1;if (i==n) print();                                           //８個皇后都放置好,輸出else search(i+1);                                      //繼續遞歸放置下一個皇后b[j]=0;                                                        //遞歸返回即為回溯一步,當前皇后退出c[i+j]=0;d[i-j+7]=0;}
}
int print() 
{int i;sum++;                                                        //方案數累加1
}

?