n后问题

问题描述

在n乘以n格的棋盘上放置彼此不受攻击的n个皇后，按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n*n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。

思路

与图着色问题思考方式大致相同，需要一个一维数组记录皇后放置棋盘上的位置，以数组下标为棋盘上的行，数组的值为棋盘的列，进行每列试值，检查其放置是否合法，不合法回溯，合法进行下一行。递归过程为放置下一行。对于棋盘的不在同一斜线的判定，想象等腰直角三角形的判定，两直角边相等。

代码

public class queenProblem {
	static int n=8;
	static int sum=0;
	static int []dir=new int[n+1];	//下标代表棋盘行，值代表棋盘列
	public static void main(String[] args) {
		int map[][]=new int[n+1][n+1];
		queue(1,map);
		System.out.println(sum);
	}

	private static void queue(int j, int[][] map) {
		
		if(j>n) {
			sum++;
			for(int i=1;i<=n;i++)
			System.out.print(dir[i]+" ");
			System.out.println();	
		}
		else {
			for(int i=1;i<=n;i++) {
				dir[j]=i;       //尝试放各个列
				if(isok(j)) queue(j+1,map);
				dir[j]=0;   //回溯
			}
		}
		
	}

	private static boolean isok(int j) {
		for(int i=1;i<j;i++) {
            //不在同一列，不在同一斜线
			if(dir[i]==dir[j] || Math.abs(dir[i]-dir[j])==Math.abs(i-j)) {   
				return false;
			}
		}
		return true;
	}

}