N皇后问题--回溯法

package com.javaTest.cn.nqueen;

import java.util.Scanner;

public class Nqueen {
    //皇后的个数
    int n;
    //第几行的皇后放在哪一列
    int[] x=new int[100];
    //记录有多少种方案
    int sum=0;
    
    public void output(int n){
        System.out.println("第"+sum+"种方案为：");
        for (int i = 1; i <= n; i++) {
            System.out.println("("+i+","+x[i]+")");
        }
    }
    
    public boolean place(int k) {
        for (int j = 1; j < k; j++) {
            //判断给皇后使得否在同一列或者对角线上；
            if (x[j]==x[k]||Math.abs(x[j]-x[k])==Math.abs(j-k)) {
                return false;
            }
        }
        return true;
        
    }
    public void BackTrace(int t,int n) {//递归
        if (t>n) {//如果t>n说明已经完成一次放置
            sum++;
            output( n);
        }else {
            for (int i = 1; i <=n; i++) {
                x[t]=i;
                if (place(t)) {//可以放在i位置处，则继续搜索
                    BackTrace(t+1, n);
                }
            }
        }
    }
        
    public  void BackTrace1(int n) {//非递归
        
        int k;
        x[1]=0;
        k=1;
        while(k>=1) {
            x[k]+=1;//先放在第一个位置
            while (x[k]<=n&&!(place(k))) {//当不能放时；
                x[k]++;
            }
        if (x[k]<=n) {
            if (k==n) {
                sum++;
                output(n);
            }else { //没有处理完，让k自加，处理下一个皇后
                k++;
                x[k]=0;
            }
        }else {// 当前无法完成放置，则进行剪枝，回溯回去，回到第k-1步
            k--;
        }    
        }
    }
    public static void main(String[] args) {
        System.out.println("您需要测试的是多少个皇后？请输入!");
        Scanner sc=new Scanner(System.in);
        int count=Integer.parseInt(sc.nextLine());
        System.out.println(count+"皇后的放置方法为：");
        Nqueen nqueen=new Nqueen();
        //nqueen.BackTrace(count);
        nqueen.BackTrace(1, count);
    }

}