51. N Queens - jiejackyzhang/leetcode-note GitHub Wiki

The n-queens puzzle is the problem of placing n queens on an n×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.

For example,

There exist two distinct solutions to the 4-queens puzzle:

[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
]

解题思路为backtracking。

用一个int[] cols数组来记录每一行Queen所在的列。 然后一行一行放置Queen，在每一行中，依次尝试每一列，若valid，则继续放下一行；若都不valid，则返回上一行，继续尝试后面的位置。

public class Solution {
    
    private List<List<String>> res;
    private int N;
    private int[] cols;
    
    public List<List<String>> solveNQueens(int n) {
        res = new ArrayList<>();
        N = n;
        cols = new int[N]; 
        solve(0);
        return res;
    }
    
    private void solve(int row) {
        if(row == N) {
            res.add(generateSolution());
            return;
        }
        for(int col = 0; col < N; col++) {
            cols[row] = col;
            if(isValid(row)) {
                solve(row + 1);
            }
        }
    }
    
    private boolean isValid(int row) {
        for(int i = 0; i < row; i++) {
            if(cols[i] == cols[row] || row - i == Math.abs(cols[row] - cols[i])) return false;
        }
        return true;
    }
    
    private List<String> generateSolution() {
        List<String> solution = new ArrayList<>();
        for(int row = 0; row < N; row++) {
            StringBuilder sb = new StringBuilder();
            for(int col = 0; col < N; col++) {
                if(col == cols[row]) {
                    sb.append("Q");
                } else {
                    sb.append(".");
                }
            }
            solution.add(sb.toString());
        }
        return solution;
    }
}
⚠️ **GitHub.com Fallback** ⚠️