n后问题回溯笔记

问题描述

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

代码

import java.util.Scanner;

import static java.lang.Math.abs;

class Main{
    static int n;
    static int sum=0;
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        n=sc.nextInt();
        int x[]=new int [n+1];
        Backtrack(1,x);
    }
    public static int[] Backtrack(int t,int x[]){
            if(t>n){
                sum++;
                System.out.println("第"+sum+"个情况：");
                for (int i = 1; i < x.length; i++) {
                    for (int j = 1; j < x.length; j++) {
                        if(j==x[i]) System.out.print("Q");
                        else System.out.print("*");
                    }
                    System.out.println();
                }
                System.out.println();
            }
            else{
                for (int i = 1; i <= n; i++) {
                    x[t] = i;
                    if(Place(t,x)){
                        Backtrack(t+1,x);
                    }
                }
            }
            return x;
    }
    public static boolean Place(int t,int[] x){
        for (int j = 1; j <= t-1; j++) {
            if((abs(t - j) == abs(x[j] - x[t]))||(x[j] - x[t]==0)){
                return false;
            }
        }
        return true;
    }
}