题解 | #八皇后#

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

class Solution {

    public  ArrayList<Integer> getAns(int n) {
        dfs(0, new int[n], n, new int[n]);
        ArrayList<Integer> result = new ArrayList<>();
        for (int[] nums : ans) {
            StringBuilder builder = new StringBuilder();
            for (int x : nums) {
                builder.append(x + 1);
            }

            result.add(Integer.parseInt(builder.toString()));
        }
        result.sort(Integer::compare);
        return result;
    }

    public  boolean isVaild(int []broad, int i, int j) {

        for (int row = i - 1, col = j - 1; row >= 0 && col >= 0; row--, col--) {
            if (broad[row] == col)
                return false;
        }

        for (int row = i - 1, col = j + 1; row >= 0 &&
                col < broad.length; row--, col++) {
            if (broad[row] == col)
                return false;
        }
        return true;
    }

    ArrayList<int[]> ans = new ArrayList<>(92);
    public  void dfs(int i, int []broad, int n, int []visited) {
        if (i >= n) {
            ans.add(Arrays.copyOf(broad, broad.length));

            /*System.out.println("第"+ans.size()+"种:");
            System.out.println("棋盘数组为："+ Arrays.toString(broad));
            for (int j = 0; j < n; j++) {
                for (int k = 0; k < n; k++) {
                    if (broad[j]!=k)
                        System.out.print(". ");
                    else
                        System.out.printf("Q ");
                }
                System.out.println();

            }*/
            return;
        }

        for (int j = 0; j < n; j++) {
            if (visited[j] != 1 && isVaild(broad, i, j)) {
                broad[i] = j;
                visited[j] = 1;
                dfs(i + 1, broad, n, visited);
                visited[j] = 0;
            }
        }


    }

}
public class Main {
    public static void main(String[] args) {
        ArrayList<Integer> ans = new Solution().getAns(8);
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextInt()) {
            System.out.println(ans.get(scanner.nextInt() - 1));
        }
    }
}