Description

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

Input

輸入的第一個(gè)為測(cè)試樣例的個(gè)數(shù)T，接下來有T個(gè)測(cè)試樣例。每個(gè)測(cè)試樣例的只有一行一個(gè)數(shù)n （ n < 15 ），表示棋盤的大小。

Output

對(duì)應(yīng)每個(gè)測(cè)試樣例輸出一行結(jié)果：可行方案數(shù)。

Sample Input

2
3
4

Sample Output

0
2

#include<iostream> #include<string.h> #include<cmath> using namespace std; const int NUM = 16; int x[NUM]; int n; //棋盤的大小 int sum; //當(dāng)前找到的可行方法數(shù) inline bool place(int t){for(int i=1;i<t;i++){if((abs(t-i)==abs(x[i]-x[t]))||(x[i]==x[t])){return false;}}return true; } void Backtrack(int t){if(t>n){sum++;}else{for(int i=1;i<=n;i++){x[t]=i;if(place(t)) Backtrack(t+1);}} } int main(){int T;cin >> T;while(T--){cin >> n;sum = 0;memset(x,0,sizeof(x));Backtrack(1);cout << sum <<endl;} }

?

轉(zhuǎn)載于:https://www.cnblogs.com/dichuan/p/8213613.html

總結(jié)

以上是生活随笔為你收集整理的n后问题的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。