编辑代码

package backtracking;

import java.util.LinkedList;

public class EightQueensSolver {
    private static boolean isSafeColumn(int column, int currentRow, int[] placement) {
        boolean safe = true;
        int leftUp = column - 1;
        int rightUp = column + 1;
        for (int previousRow = currentRow - 1; previousRow >= 0; --previousRow) {
            if (placement[previousRow] == column || placement[previousRow] == leftUp || placement[previousRow] == rightUp) {
                safe = false;
                break;
            }
            --leftUp;
            ++rightUp;
        }
        return safe;
    }

    public static void placeQueens(int boardSize, int currentRow, int[] placement, LinkedList<int[]> solutions) {
        if (currentRow == boardSize) {
            solutions.add(placement.clone());
            return;
        }

        for (int column = 0; column < boardSize; ++column) {
            if (isSafeColumn(column, currentRow, placement)) {
                placement[currentRow] = column;
                placeQueens(boardSize, currentRow + 1, placement, solutions);
            }
        }
    }

    public static LinkedList<int[]> solveEightQueensProblem(int boardSize) {
        LinkedList<int[]> solutions = new LinkedList<>();
        int[] placement = new int[boardSize];

        placeQueens(boardSize, 0, placement, solutions);
        return solutions;
    }

    public static void printSolutions(int boardSize, LinkedList<int[]> solutions) {
        System.out.println("Eight Queens Problem has " + solutions.size() + " solutions:");
        for (int[] solution : solutions) {
            for (int queenColumn : solution) {
                for (int column = 0; column < boardSize; ++column) {
                    if (column == queenColumn) {
                        System.out.print('Q');
                    } else {
                        System.out.print('.');
                    }
                }
                System.out.println();
            }
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int boardSize = 4;
        LinkedList<int[]> solutions = solveEightQueensProblem(boardSize);
        printSolutions(boardSize, solutions);
    }
}