题解 | 八皇后

import java.util.*;

public class Main {

    static ArrayList<String> list = new ArrayList<>(); // 存储所有92个解

    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

        boolean[][] array = new boolean[8][8];
        // 初始化棋盘全为false
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                array[i][j] = false;
            }
        }

        // 从第0行开始回溯
        traceBack(array, 0, new StringBuilder());

        // 根据输入输出对应的解
        while (in.hasNextInt()) {
            int b = in.nextInt();
            System.out.println(list.get(b - 1)); // b从1开始
        }
    }

    // 回溯放置第row行
    public static void traceBack(boolean[][] array, int row, StringBuilder choiceStr) {
        if (row == 8) {
            // 找到一个解，存入list
            list.add(choiceStr.toString());
            return;
        }

        for (int col = 0; col < 8; col++) {
            // 检查位置(row, col)是否安全
            if (isSafe(array, row, col)) {
                // 放置皇后
                array[row][col] = true;
                choiceStr.append(col + 1); // 题目要求输出1-based列号

                // 递归下一行
                traceBack(array, row + 1, choiceStr);

                // 回溯，撤销皇后
                array[row][col] = false;
                choiceStr.deleteCharAt(choiceStr.length() - 1);
            }
        }
    }

    // 判断在(row, col)放置皇后是否与已有皇后冲突
    public static boolean isSafe(boolean[][] array, int row, int col) {
        // 检查同一列
        for (int i = 0; i < row; i++) {
            if (array[i][col]) {
                return false;
            }
        }
        // 检查左上对角线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (array[i][j]) {
                return false;
            }
        }
        // 检查右上对角线
        for (int i = row - 1, j = col + 1; i >= 0 && j < 8; i--, j++) {
            if (array[i][j]) {
                return false;
            }
        }
        return true;
    }
}