给定一个n*n的棋盘,棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后,使任意的两个黑皇后都不在同一行、同一列或同一条对角线上,任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法?n小于等于8。
进行连续的两次n皇后即2n皇后。如:① 1 1 1 1
② 1 1 1 1
③ 1 1 1 1
④ 1 1 1 1
先插入黑皇后,从①[0]开始遍历,到②[x]~④[x],回溯,全符合条件后再进行白皇后的判断。
代码:
1 import java.util.Scanner; 2 public class Main { 3 static int bQ=2; 4 static int wQ=3; 5 static int count=0; 6 static int white[]; 7 static int black[]; 8 static int arr[][]; 9 public static void main(String[] args) { 10 Scanner sc=new Scanner(System.in); 11 int n=sc.nextInt(); 12 arr=new int[n][n]; 13 white=new int[n]; 14 black=new int[n]; 15 for(int i=0;i<n;i++){ 16 for(int j=0;j<n;j++){ 17 arr[i][j]=sc.nextInt(); 18 } 19 } 20 dfs(black,bQ,0); 21 System.out.println(count); 22 } 23 private static void dfs(int[] Arr,int color,int n){ 24 if(n==Arr.length){ 25 if(color==wQ) { 26 count++; 27 } 28 else if(color==bQ){ 29 dfs(white,wQ,0); 30 } 31 return; 32 } 33 for(int i=0;i< white.length;i++){ 34 if(arr[n][i]==1&&test(Arr,i,n)){ 35 arr[n][i]=color; 36 Arr[n]=i; 37 dfs(Arr,color,n+1); 38 arr[n][i]=1; 39 } 40 } 41 } 42 private static boolean test(int arr[],int line,int high){ 43 for(int i=0;i<high;i++){ 44 if(arr[i]==line){ 45 return false; 46 } 47 if(arr[i]+i==line+high){ 48 return false; 49 } 50 if(arr[i]-i==line-high){ 51 return false; 52 } 53 } 54 return true; 55 } 56 }
该dfs为c语言网的解。明天试试课本的dfs代码,,