回溯法之n后问题
问题描述
在n x n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线的棋子。n后问题等价于n x n格的棋盘上放置n个皇后，任何2个皇后不放在同一行或同一列或同一斜线上。
算法设计
用n元组x[1:n]表示n后问题的解，其中x[i]表示皇后放在棋盘的第i行的第x[i]列。由于不允许将2个皇后放在同一列上。所以解向量中的x[i]互不相同。2个皇后不能放在同一斜线上是问题的隐约束。对于一般的n后问题，这一隐约束条件可以化成显约束的形式。如果将n x n格的棋盘看做二维方针，其行号从上到下，列号从左到右依次编号为1，2，...，n，从棋盘左上角到右下角的主对角线及其平行线（即斜率为-1的各斜线）上，2个下标值的差（行号-列号）值相等。同理，斜率为+1的每一条斜线上，2个下标值的和（行号+列号）值相等。因此，若两个皇后防止的位置分别是（i，j）和（k，l）,且i-j=k-l或i+j=k+l，则说明这两个皇后处于同一斜率上。以上两个方程分别等价于i-k=j-l和i-k=l-j。由此可知，只要|i-k|=|j-l|成立，就表明两个皇后位于同一条斜率上。问题的隐约束就变成了显约束。
用回溯法解n后问题时，用完全n叉树表示解空间。可行性约束Place减去不满足行、列和斜线约束的子树。
代码求解
import java.util.Scanner;
public class NQueen {
final static int num=20;
static int n;//皇后个数
static int[]x = new int[num]; //当前解
static long sum;
public static boolean place(int k){
for(int j=1;j<k;j++){
if(Math.abs(k-j)==Math.abs(x[j]-x[k])||x[j]==x[k]) return false;
}
return true;
}
public static void backTrack(int t){
if(t>n) sum++;
else{
for(int i=1;i<=n;i++){
x[t]=i;
if(place(t)) backTrack(t+1);
}
}
}
public static void main(String[] args){
Scanner scan = new Scanner(System.in);
n =scan.nextInt();
sum=0;
backTrack(1);
System.out.println(sum);
}
}
