51. N-Queens

Question:

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.

Example:

Input: 4
Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

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

Thinking:

1. Question9_9: 八皇后

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new ArrayList<>();
        if(n == 0) return result;
        backtrace(result, new ArrayList<String>(), 0, n, new boolean[n]);
        return result;
    }
    public static void backtrace(List<List<String>> result, List<String> list, int level, int n, boolean[] used){
        if(level == n) result.add(new ArrayList<String>(list));
        else{
            for(int i = 0; i < n; i++){
                if(used[i]) continue;
                if(isValid(list, level, i, n)){
                    list.add(createQueen(n, i));
                    used[i] = true;
                    backtrace(result, list, level + 1, n, used);
                    used[i] = false;
                    list.remove(list.size() - 1);
                }
            }
        }
    }
    public static boolean isValid(List<String> list, int row, int column, int n){
        if(row > 0){
            String cmp = list.get(row - 1);
            for(int i = 0; i < row; i++)
                if(list.get(i).charAt(column) == 'Q') return false;
            int tempRow = row;
            int tempCol = column;
            while(--tempRow >= 0 && --tempCol >= 0){
                if(list.get(tempRow).charAt(tempCol) == 'Q') return false;
            }
            tempRow = row;
            tempCol = column;
            while(--tempRow >= 0 && ++tempCol <= n-1)
                if(list.get(tempRow).charAt(tempCol) == 'Q') return false;
        }
        return true;
    }
    private static String createQueen(int n, int index){
        StringBuilder sb = new StringBuilder();
        int i = 0;
        for(; i < index; i++)
            sb.append('.');
        sb.append('Q');
        for(++i; i < n; i++){
            sb.append('.');
        }
        return sb.toString();
    }
}

二刷

这是一道基础的回溯问题，这次一开始就创建了char[][] map并全部设置为 ‘.’，然后通过回溯向中间插入‘Q’

class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new LinkedList<>();
        char[][] map = new char[n][n];
        for(int i = 0; i < n; i++){
            for(int j = 0; j < n; j++){
                map[i][j] = '.';
            }
        }
        backtrace(result, map, 0, n);
        return result;
    }
    private void backtrace(List<List<String>> result, char[][] map, int i, int n){
        if(i == n){
            List<String> res = new LinkedList<>();
            for(int p = 0; p < n; p++)
                res.add(new String(map[p]));
            result.add(res);
        }else{
            for(int j = 0; j < n; j++){
                if(check(map, i, j)){
                    map[i][j] = 'Q';
                    backtrace(result, map, i + 1, n);
                    map[i][j] = '.';
                }
            }
        }
    }
    private boolean check(char[][] map, int row, int col){
        for(int i = 0; i < row; i++) if(map[i][col] == 'Q') return false;
        for(int i = 0; i < col; i++) if(map[row][i] == 'Q') return false;
        int i = row, j = col;
        while(--i >= 0 && --j >= 0) if(map[i][j] == 'Q') return false;
        while(--row >= 0 && ++col < map.length) if(map[row][col] == 'Q') return false;
        return true;
    }
}

Third time

• Method 1: Search + bfs 3ms

  class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> result = new LinkedList<>();
        char[][] table = new char[n][n];
        for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) table[i][j] = '.';
        dfs(result, table, 0, n);
        return result;
    }
    public void dfs(List<List<String>> result, char[][] table, int row, int n){
        if(row == n){
            List<String> temp = new LinkedList<>();
            for(int i = 0; i < n; i++){
                temp.add(new String(table[i]));
            }
            result.add(temp);
            return;
        }
        for(int i = 0; i < n; i++){
            if(check(table, row, i, n)){
                table[row][i] = 'Q';
                dfs(result, table, row + 1, n);
                table[row][i] = '.';
            }
        }
    }
    private boolean check(char[][] table, int row, int col, int n){
        for(int i = 0; i < n; i++){
            if(table[row][i] == 'Q') return false;
            if(table[i][col] == 'Q') return false;
        }
        int tempRow = row, tempCol = col;
        while(tempRow >= 0 && tempCol >= 0) if(table[tempRow--][tempCol--] == 'Q') return false;
        while(row >= 0 && col < n) if(table[row--][col++] == 'Q') return false;
        return true;
    }
  }