2n皇后问题

 1 import java.util.Scanner;
 2 public class Main {
 3     static int n,count=0;  
 4     static int map[][];  
 5     public static void main(String args[])  
 6     {  
 7         Scanner cn=new Scanner(System.in);  
 8         n=cn.nextInt();  
 9         map=new int[n][n];  
10         for(int i=0;i<n;i++)  
11             for(int j=0;j<n;j++)  
12                 map[i][j]=cn.nextInt();  
13         Put(0,2);   //假设黑皇后为2 白皇后为3  放了皇后的地方就用2，3表示  ，0表示第0行
14         System.out.println(count);  
15     }
16     /**
17      * 
18      * @param t 开始放的下标
19      * @param s 皇后的类型
20      */
21     public static void Put(int t,int s)  
22     {  
23         //放完某种类型的皇后了
24         if(t==n)  
25         {  
26             if(s==2)Put(0,3);  //表示之前放的是黑皇后，现在开始放白皇后
27             else count++;  //因为这会第n个已经放完了，所以方法数量加1
28             return ;  //此时白皇后也放完了 ，就返回
29         }  
30         for(int i=0;i<n;i++)  
31         {  
32               
33             if(map[t][i]!=1)continue; //此处已被不能放皇后或放过皇后则跳出本次循环 
34             if(Check(t,i,s))map[t][i]=s; //当前遍历后发现位置合适，就把皇后放当前位置
35             else continue;  //不合适跳过本次循环，查找当前行下一个位置
36             Put(t+1,s); //此位置放完一个皇后还要去放下一个皇后 
37             map[t][i]=1;   //回溯法的关键，假设这个位置不放皇后，把皇后放在别的位置   
38         }  
39         return ;  
40     }  
41     /**
42      * 
43      * @param t 当前行
44      * @param i 当前列
45      * @param s 皇后的类型
46      * @return
47      */
48     public static boolean Check(int t,int i,int s)  
49     {  
50         for(int q=t-1;q>=0;q--)  
51         {  
52             //当前列上有同类皇后，就返回false
53             if(map[q][i]==s)return false;  
54         }         
55         for(int q=t-1,w=i-1;q>=0&&w>=0;q--,w--)
56         {  
57             //检查主对角线向上方向（前几行）是否处于同类皇后在对角线上
58             if(map[q][w]==s)return false;  
59         }  
60         for(int q=t-1,w=i+1;q>=0&&w<=n-1;q--,w++)  
61         {  
62             //检查副对角线向上方向（前几行）是否处于同类皇后在对角线上
63             if(map[q][w]==s)return false;  
64         }  
65         return true;  
66     }  
67 }