0051. N Queens - kumaeki/LeetCode GitHub Wiki

0051. N-Queens

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space, respectively.

Example 1:

Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above

Example 2:

Input: n = 1
Output: [["Q"]]

Constraints:

  • 1 <= n <= 9

解法1

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList<List<String>>();
        char[][] board = new char[n][n];
        for(int i = 0; i < n; i++)
            for(int j = 0; j < n; j++)
               board[i][j] = '.'; 
        
        setQueens(0, res, board, n);
        return res;
    }
    
    private void setQueens(int line, List<List<String>> res,char[][] board, int n){
        // 如果所有n个queen都已经放完了, 那么将当前方案放入结果集中
        if(line == n){
            List<String> list = new ArrayList<String>();
            for(char[] row : board)
                list.add(new String(row));
            res.add(list);
            return;
        }
        // 从第一列开始遍历当前行的所有可能排列
        // 如果有有效位置, 那么继续计算下一行,直到最后.
        // 计算完成之后恢复原状, 计算下一个可能的位置
        for(int j = 0; j < n; j++){
            if(isValidPosition(board, line, j)){
                board[line][j] = 'Q';
                setQueens(line + 1, res, board, n); 
                board[line][j] = '.';
            }
        }
        
    }
    // 判断当前位置是否可以放queen
    // 判断条件是3个
    // 1. 当前行没有放置queen, 根据setQueens的处理, 每一行同时至多只有一个queen, 所以可以不check
    // 2. 当前列没有放置queen, 根据setQueens的处理, 处理顺序是从上到下, 所以j之后的位置可以不check
    // 3. 两条斜线没有放置queen, 根据setQueens的处理, 处理顺序是从左上到右下, 
    //    所以只需要判断左上 和 右上两条不完整的斜线就可以.
    private boolean isValidPosition(char[][] board, int i, int j){
        int n = board.length;
        for(int k = 0; k < i; k++)
           if(board[k][j] == 'Q')
               return false;
        
        for(int k = 0; k <= i && k <= j; k++)
            if(board[i - k][j - k] == 'Q')
                return false;
            
        
        for(int k = 0; k <= i && k + j < n; k++)
            if(board[i - k][j + k] == 'Q')
                return false;
        
        return true;    
    }
}
⚠️ **GitHub.com Fallback** ⚠️