蓝桥杯基础练习VIP-2n皇后问题 （Java代码）

解题思路:

2n皇后 回溯法，枚举所有可能，三重循环验证当前与其余的是否点有重复



注意事项:
    狗日的弱智三重循环写了半天




参考代码:

package lanqiao;

import java.util.Scanner;

public class Basic_27 {
	private static int n;
	private static int [][]x = new int[10][10]; 
	private static int [][] a = new int[100][10];
	private static int [] b = new int[10];
	private static int sum;
	public static void main(String[] args) {
		Scanner input = new Scanner(System.in);
		n = input.nextInt();
		sum = 0;
		for(int i = 1; i <= n ; i ++)
			for(int j = 1; j <= n; j ++)
				x[i][j] = input.nextInt();
		
		backtrack(1);

		//第i行的结果与其余行的结果进行比较，如果有相等的则调到下一行
		int i = 1;
		boolean flag;
		while(i <= p - 1) {
			System.arraycopy(a[i], 1, b, 1, n); //b存第i个结果
			//b与a中的所有结果进行比较
			for(int k = 1; k <= p - 1 ; k ++) {
				flag = true;
				for(int j = 1; j <= n; j ++) {
					if(a[k][j] == b[j]) {
						flag = false;
						break; //跳出与下一行进行对比
					}
				}
				if(flag) sum ++;
			}
			i ++;
		}
		System.out.println(sum);
	}
	
	
	private static int p = 1;
	//2n皇后 回溯法，枚举所有可能，二重循环验证当前与其余的是否点有重复
	private static void backtrack(int t) {
		int i;
		//到达叶子节点
		if(t > n) {
			System.arraycopy(b, 1, a[p], 1, n);
			p ++;
		} else {
			for(i = 1; i <= n; i ++) {
				b[t] = i;
				if(x[t][i] == 1 && bound(t)) backtrack(t + 1); //t代表已经放了t个皇后,如果当前点不与之前的点冲突，则搜索下一层

			}
		}
		
	}
	
	private static boolean bound(int t) {
		for(int i = 1; i < t; i ++) {
			if((b[t] == b[i]) || (Math.abs(b[t] - b[i]) == Math.abs(t - i))) {
				return false;
			}
		}
		return true;
	}

	
}