題目

給定一個n*n的棋盤，棋盤中有一些位置不能放皇后。現在要向棋盤中放入n個黑皇后和n個白皇后，使任意的兩個黑皇后都不在同一行、同一列或同一條對角線上，任意的兩個白皇后都不在同一行、同一列或同一條對角線上。問總共有多少種放法？n小于等于8。

輸入
輸入的第一行為一個整數n，表示棋盤的大小。 n小于等于8
接下來n行，每行n個0或1的整數，如果一個整數為1，表示對應的位置可以放皇后，如果一個整數為0，表示對應的位置不可以放皇后。

輸出
輸出一個整數，表示總共有多少種放法。

樣例輸入

4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

樣例輸出

2

解題思路

本題顯然是深度優先（DFS）的搜索，需要采用遞歸加上回溯的算法。由于要放置兩種皇后，且由題意可知，黑、白皇后必然每一行都有且僅有一個，因此，可以先放好白皇后，再防止黑皇后；也可以逐行放置，放好第i行的白皇后，就放同一行的黑皇后，我采用的方法便是第二種。

首先，讀入輸入的“棋盤”，棋盤上規定了一些格子不允許放置皇后，為0；之后，便進入DFS搜索，每一次調用DFS的遞歸函數，需要放置黑、白皇后各1個，放置的位置要求同行、同列、兩條對角線都不包含同顏色的棋子，且黑白皇后不處于同一格，直到遞歸到每一行都“放過”黑、白皇后。

易錯點

注意兩個判斷斜對角線是否有皇后的hash散列，其長度為(2*n-1)，而不是n（起初，我因為設置為了8，很多n>4的樣例無法通過。。。）；

在每一次遞歸結束之后，需要對稱地將變化的參數還原，即需要回溯到上一層開始時的情況。

代碼

#include<bits/stdc++.h> using namespace std; int a[8][8],num=0; int hash_c[2][15],hash_m[2][15],hash_s[2][15]; void DFS(int n, int r){int i,j;if (r==n){num++;return ;}for (i=0;i<n;i++)//白皇后按照行占位{if (a[r][i]==1 && hash_c[0][i]==0 && hash_s[0][i-r+n-1]==0 && hash_m[0][i+r]==0)//判斷兩條對角線和列{hash_c[0][i] = 1;//該列、對角線已有白皇后hash_s[0][i-r+n-1] = 1;hash_m[0][i+r] = 1;a[r][i] = 0;//落子for (j=0;j<n;j++)//黑皇后按照行占位{if (a[r][j]==1 && hash_c[1][j]==0 && hash_s[1][j-r+n-1]==0 && hash_m[1][j+r]==0){hash_c[1][j] = 1;//該列已有黑皇后hash_s[1][j-r+n-1] = 1;hash_m[1][j+r] = 1;a[r][j] = 0;//落子DFS(n,r+1);//回溯hash_c[1][j] = 0;//該列已有黑皇后hash_s[1][j-r+n-1] = 0;hash_m[1][j+r] = 0;a[r][j] = 1;//允許落子}}//回溯hash_c[0][i] = 0;//該列、對角線已有白皇后hash_s[0][i-r+n-1] = 0;hash_m[0][i+r] = 0;a[r][i] = 1;//允許落子}} } int main() {int n,i,j;scanf("%d",&n);for (i=0;i<n;i++)for (j=0;j<n;j++)scanf("%d",&a[i][j]);//讀入初始化的數值DFS(n,0);printf("%d",num);return 0; }

總結

以上是生活随笔為你收集整理的题目 1460: 2n皇后问题的全部內容，希望文章能夠幫你解決所遇到的問題。

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