8.N皇后

• 2.14
  • 左上，中上，右上
  • 回溯函数中 row 固定，col++
  • char【】·转为 list《String》

class Solution {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] grid = new char[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                grid[i][j]='.';
            }
        }
        backtrack(grid,n,0);
        return res;
    }
 
    public void backtrack(char[][] grid,int n,int row){
        if(n==row){
            res.add(Array2List(grid));
            return;
        }
        for(int i=0;i<n;i++){
            if(!check(grid,n,row,i)) continue;
            grid[row][i]='Q';
            backtrack(grid,n,row+1);
            grid[row][i]='.';
        }
    }
 
 
    public boolean check(char[][] grid,int n,int row,int col){
        for(int i=row;i>=0;i--){
            if(grid[i][col]=='Q'){
                return false;
            }
        }
        for(int i=row-1,j=col-1;i>=0&&j>=0;i--,j--){
            if(grid[i][j]=='Q') return false;
        }
        for(int i=row-1,j=col+1;i>=0&&j<=n-1;i--,j++){
            if(grid[i][j]=='Q') return false;
        }
        return true;
    }
    public List<String> Array2List(char[][] grid){
        List<String> list = new ArrayList<>();
        for(char[] g:grid){
            list.add(new String(g));
        }
        return list;
    }
}

• 2.3
  • 回溯的经典套路，多了一个判断是否满足对角线和头上是否满足的辅助函数，和 char【】【】转向 List《string》的辅助函数

class Solution {
    List<List<String>> res = new ArrayList<>();
    public List<List<String>> solveNQueens(int n) {
        char[][] grid = new char[n][n];
        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                grid[i][j] = '.';
            }
        }
        backtrack(grid,0,n);
        return res;
    }
    public void backtrack(char[][] grid,int row,int n){
        if(row==n){
            res.add(array2List(grid));
            return;
        }
        for(int col=0;col<n;col++){
            if(isValid(grid,row,col,n)){
                grid[row][col] = 'Q';
                backtrack(grid,row+1,n);
                grid[row][col] = '.';
            }
        }
    }
    public boolean isValid(char[][] grid,int row,int col,int n){
        for(int i=0;i<row;i++){
            if(grid[i][col]=='Q'){
                return false;
            }
        }
        for(int i = row-1,j = col-1;i>=0&&j>=0;i--,j--){
            if(grid[i][j]=='Q'){
                return false;
            }
        }
        for(int i = row-1,j=col+1;i>=0&&j<grid[0].length;i--,j++){
            if(grid[i][j]=='Q') return false;
        }
        return true;
    }
    public List<String> array2List(char[][] grid){
        List<String> path = new ArrayList<>();
        for(char[] chs:grid){
            path.add(String.valueOf(chs));
        }
        return path;
    }
}

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
 
class Solution {
    List<List<String>> res = new ArrayList<>();
 
    public List<List<String>> solveNQueens(int n) {
        // 1. 初始化棋盘，全部填入 '.'
        char[][] board = new char[n][n];
        for (char[] row : board) {
            Arrays.fill(row, '.');
        }
        
        // 2. 从第 0 行开始回溯
        backtrack(board, 0, n);
        return res;
    }
 
    /**
     * @param board 当前棋盘状态
     * @param row   当前正在处理哪一行
     * @param n     总行数
     */
    private void backtrack(char[][] board, int row, int n) {
        // 结束条件：如果 row 等于 n，说明 0 ~ n-1 行都放好皇后了
        if (row == n) {
            res.add(array2List(board));
            return;
        }
 
        // 尝试在当前行的每一列 (col) 放皇后
        for (int col = 0; col < n; col++) {
            // 剪枝：检查这个位置 (row, col) 是否合法
            if (isValid(board, row, col, n)) {
                // 1. 做选择
                board[row][col] = 'Q';
                
                // 2. 递归进入下一行
                backtrack(board, row + 1, n);
                
                // 3. 撤销选择 (回溯)
                board[row][col] = '.';
            }
        }
    }
 
    // 核心逻辑：判断 board[row][col] 是否可以放皇后
    private boolean isValid(char[][] board, int row, int col, int n) {
        // 1. 检查列 (Column)：看当前位置的“正上方”有没有皇后
        for (int i = 0; i < row; i++) {
            if (board[i][col] == 'Q') {
                return false;
            }
        }
 
        // 2. 检查左上斜线 (45度)：往“左上”遍历
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
 
        // 3. 检查右上斜线 (135度)：往“右上”遍历
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (board[i][j] == 'Q') {
                return false;
            }
        }
 
        return true;
    }
 
    // 辅助工具：把 char[][] 转成 List<String>
    private List<String> array2List(char[][] board) {
        List<String> list = new ArrayList<>();
        for (char[] row : board) {
            list.add(new String(row));
        }
        return list;
    }
}