回溯法求解n皇后问题java

n皇后问题是一个经典的回溯问题，思路如下：

1. 定义一个n \* n的棋盘，用二维数组board表示，其中0表示空格，1表示皇后。

2. 从第一行开始，每次放置一个皇后，然后递归到下一行。

3. 在每一行中，从左到右依次尝试每个位置，如果该位置不冲突，则放置皇后，并递归到下一行。

4. 如果递归到最后一行，说明找到了一组解，将其保存。

5. 如果当前行无法放置皇后，回溯到上一行，重新尝试其他位置。

下面是Java代码实现：

public class NQueenProblem {
    private int n;
    private int[][] board;
    private List<int[][]> solutions;

    public NQueenProblem(int n) {
        this.n = n;
        this.board = new int[n][n];
        this.solutions = new ArrayList<>();
    }

    public void solve() {
        solve(0);
    }

    private void solve(int row) {
        if (row == n) {
            int[][] solution = new int[n][n];
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    solution[i][j] = board[i][j];
                }
            }
            solutions.add(solution);
            return;
        }
        for (int col = 0; col < n; col++) {
            if (isValid(row, col)) {
                board[row][col] = 1;
                solve(row + 1);
                board[row][col] = 0;
            }
        }
    }

    private boolean isValid(int row, int col) {
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 1) {
                return false;
            }
        }
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 1) {
                return false;
            }
        }
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 1) {
                return false;
            }
        }
        return true;
    }

    public List<int[][]> getSolutions() {
        return solutions;
    }
}

其中isValid方法用于判断当前位置是否可以放置皇后。它需要检查当前列、左上角和右上角是否已经有皇后。如果没有，则返回true，否则返回false。

在主方法中，我们创建一个实例，调用solve方法来解决问题。最后，我们可以通过getSolutions方法得到所有的解。