回溯法之n后問題
問題描述
在n x n格的棋盤上放置彼此不受攻擊的n個皇后。按照國際象棋的規(guī)則侠驯，皇后可以攻擊與之處在同一行或同一列或同一斜線的棋子。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;//皇后個數(shù)
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);
}
}
