給定一個 N×N 的棋盤，請你在上面放置 N 個棋子，要求滿足：

每行每列都恰好有一個棋子
每條對角線上都最多只能有一個棋子

上圖給出了當 N=6 時的一種解決方案，該方案可用序列 2 4 6 1 3 5 來描述，該序列按順序給出了從第一行到第六行，每一行擺放的棋子所在的列的位置。

請你編寫一個程序，給定一個 N×N 的棋盤以及 N 個棋子，請你找出所有滿足上述條件的棋子放置方案。

輸入格式
共一行，一個整數 N。

輸出格式
共四行，前三行每行輸出一個整數序列，用來描述一種可行放置方案，序列中的第 i 個數表示第 i 行的棋子應該擺放的列的位置。

這三行描述的方案應該是整數序列字典序排在第一、第二、第三的方案。

第四行輸出一個整數，表示可行放置方案的總數。

數據范圍
6≤N≤13
輸入樣例：
6
輸出樣例：
2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

這條對角線x-y+n,y-x+n都可以，但是數組的大小要發現變化，在這道題，如果你用x-y+n，N = 30，但如果你要y-x+n,N可以 = 20，所以數組開大一點。

代碼如下：

#include <iostream> using namespace std; const int N = 30; int path[N]; bool col[N],duijiao1[N],duijiao2[N]; int ans; int n; void dfs(int x)//行 {if (x > n){ans++;if (ans<=3){for (int i = 1;i<=n;i++){cout<<path[i]<<" ";}cout<<endl;return ;}}for (int y = 1;y<=n;y++){if (!col[y] && !duijiao1[x+y] && !duijiao2[x-y+n]){col[y] = duijiao1[x+y] = duijiao2[x-y+n] = true;path[x] = y;dfs(x+1);col[y] = duijiao1[x+y] = duijiao2[x-y+n] = false;// path[x] = 0;}} }int main() {cin>>n;dfs(1);cout<<ans<<endl;return 0; }

總結

以上是生活随笔為你收集整理的[USACO1.5]八皇后 Checker Challenge的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。