2n皇后问题

此题为蓝桥杯基础练习题。

问题描述

　　给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。

输入格式

　　输入的第一行为一个整数n，表示棋盘的大小。
　　接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，如果一个整数为0，表示对应的位置不可以放皇后。

输出格式

　　输出一个整数，表示总共有多少种放法。

样例输入

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

样例输出

2

样例输入

4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1

样例输出

0

 

此算法使用回溯算法，如下：

import java.util.Scanner;
public class Main {
    static int n,count=0;  
    static int map[][];  
    public static void main(String args[])  
    {  
        Scanner cn=new Scanner(System.in);  
        n=cn.nextInt();  
        map=new int[n][n];  
        for(int i=0;i<n;i++)  
            for(int j=0;j<n;j++)  
                map[i][j]=cn.nextInt();  
        Put(0,2);   //假设黑皇后为2 白皇后为3  放了皇后的地方就用2，3表示  ，0表示第0行
        System.out.println(count);  
    }
    /**
     * 
     * @param t 开始放的下标
     * @param s 皇后的类型
     */
    public static void Put(int t,int s)  
    {  
        //放完某种类型的皇后了
        if(t==n)  
        {  
            if(s==2)Put(0,3);  //表示之前放的是黑皇后，现在开始放白皇后
            else count++;  //因为这会第n个已经放完了，所以方法数量加1
            return ;  //此时白皇后也放完了 ，就返回
        }  
        for(int i=0;i<n;i++)  
        {  
              
            if(map[t][i]!=1)continue; //此处已被不能放皇后或放过皇后则跳出本次循环 
            if(Check(t,i,s))map[t][i]=s; //当前遍历后发现位置合适，就把皇后放当前位置
            else continue;  //不合适跳过本次循环，查找当前行下一个位置
            Put(t+1,s); //此位置放完一个皇后还要去放下一个皇后 
            map[t][i]=1;   //回溯法的关键，假设这个位置不放皇后，把皇后放在别的位置   
        }  
        return ;  
    }  
    /**
     * 
     * @param t 当前行
     * @param i 当前列
     * @param s 皇后的类型
     * @return
     */
    public static boolean Check(int t,int i,int s)  
    {  
        for(int q=t-1;q>=0;q--)  
        {  
            //当前列上有同类皇后，就返回false
            if(map[q][i]==s)return false;  
        }         
        for(int q=t-1,w=i-1;q>=0&&w>=0;q--,w--)
        {  
            //检查主对角线向上方向（前几行）是否处于同类皇后在对角线上
            if(map[q][w]==s)return false;  
        }  
        for(int q=t-1,w=i+1;q>=0&&w<=n-1;q--,w++)  
        {  
            //检查副对角线向上方向（前几行）是否处于同类皇后在对角线上
            if(map[q][w]==s)return false;  
        }  
        return true;  
    }  
}