題目描述

檢查一個(gè)如下的6 x 6的跳棋棋盤，有六個(gè)棋子被放置在棋盤上，使得每行、每列有且只有一個(gè)，每條對角線(包括兩條主對角線的所有平行線)上至多有一個(gè)棋子。



上面的布局可以用序列2 4 6 1 3 5來描述，第i個(gè)數(shù)字表示在第i行的相應(yīng)位置有一個(gè)棋子，如下：

行號 1 2 3 4 5 6
列號 2 4 6 1 3 5

這只是跳棋放置的一個(gè)解。請編一個(gè)程序找出所有跳棋放置的解。并把它們以上面的序列方法輸出。解按字典順序排列。請輸出前3個(gè)解。最后一行是解的總個(gè)數(shù)。

輸入輸出格式

輸入格式：

一個(gè)數(shù)字N (6 <= N <= 13) 表示棋盤是N x N大小的。

輸出格式：

前三行為前三個(gè)解，每個(gè)解的兩個(gè)數(shù)字之間用一個(gè)空格隔開。第四行只有一個(gè)數(shù)字，表示解的總數(shù)。

輸入輸出樣例

輸入樣例#1：

6

輸出樣例#1：

2 4 6 1 3 5
3 6 2 5 1 4
4 1 5 2 6 3
4

源代碼

#include<iostream> using namespace std; int n; int row[101]={0},column[101]={0},l_diagonal[101]={0},r_diagonal[101]={0};//定義行、列、兩條對角線，并初始化為均未封路 int a[101];//用于記錄是否可以放置皇后 int sum=0;//用于記錄方案數(shù) void dfs(int x);int main() {cin>>n;//輸入棋盤大小dfs(1);//開始回溯cout<<sum<<endl;//輸出方案數(shù)return 0; }/*①思路：要判斷行、列、左對角線、右對角線均未被封，才可以放置一皇后②實(shí)現(xiàn)：已知行數(shù)x，設(shè)置列數(shù)y，按列進(jìn)行循環(huán)判斷是否被封，如果可以放置，記錄到新數(shù)組中，封閉四條路，向下進(jìn)行回溯③其中，行數(shù)x，列數(shù)，左對角線：x-y+n，右對角線：x+y*/ void dfs(int x) {int y;int i;if(x==n+1)//如果到達(dá)終點(diǎn)，說明方案成功{sum++;//方案數(shù)+1if(sum<=3)//輸出前三個(gè)解的皇后放置的情況{for(i=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl;}}for(y=1;y<=n;y++){if(!row[x]&&!column[y]&&!l_diagonal[x-y+n]&&!r_diagonal[x+y])//如果行、列、左對角線、右對角線均可以下{a[x]=y;//說明該點(diǎn)可以放置一皇后，記錄row[x]=1;//封閉行column[y]=1;//封閉列l(wèi)_diagonal[x-y+n]=1;//封閉左對角線r_diagonal[x+y]=1;//封閉右對角線dfs(x+1);//進(jìn)行下一層回溯row[x]=0;//還原行column[y]=0;//還原列l(wèi)_diagonal[x-y+n]=0;//還原左對角線r_diagonal[x+y]=0;//還原右對角線}} }

?

總結(jié)

以上是生活随笔為你收集整理的八皇后（洛谷-P1219）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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