leetcode - [51] N-Queens

2020/06/22

问题描述

给你一个n*n的棋盘,如何在上面放置n个皇后。

放置皇后时有如下规则,同一行同一列左右对角线均不能有其他皇后。

举个例子:

Update at 2020_0723

多谢Y总

重新梳理下思路:

首先,创建一个n * nchar类型数组g,并将其初始化为.

然后,进行DFS,当r == n时,说明我们找到了一个答案,

那么将g数组中的数据构建成一个List<String>

接着,继续进行DFS递归遍历。

重点在于,如何判断当前结点是否可以放皇后?

我们使用三个boolean数组进行判断,分别是列col、正对角线dg和反对角线udg

其中正反对角线的判断有点小技巧:

先来看正对角线,如图:

它的特点是:col - row是个固定的值,为了防止负数,我们将其加一个n

再来看反对角线:

它的特点是:col + row是一个固定的值。

来看下完整实现:

class Solution {
    
    int N = 20;
    char[][] g = new char[N][N];
    boolean[] col = new boolean[N]; // 列
    boolean[] dg  = new boolean[N]; // 正对角线
    boolean[] udg = new boolean[N]; // 斜对角线
    List<List<String>> ans = new LinkedList<>();

    public void dfs(int r, int n){
        // 找到一个答案
        if (r == n){
            List<String> child = new LinkedList<>();
            for (int i = 0; i < n; i++){
                StringBuilder sb = new StringBuilder();
                for (int j = 0; j < n; j++){
                    sb.append(g[i][j]);
                }
                child.add(new String(sb));
            }
            ans.add(child);
            return;
        }
        
        // DFS递归遍历
        for (int c = 0; c < n; c++){
            // 确保当前单元可以放皇后
            if (!col[c] && !dg[c + r] && !udg[c - r + n]){
                g[r][c] = 'Q';
                col[c] = true;  dg[c + r] = true;  udg[c - r + n] = true;
                dfs(r + 1, n);
                // 恢复现场
                col[c] = false; dg[c + r] = false; udg[c - r + n] = false;
                g[r][c] = '.';
            }
        }
    }
    
    public List<List<String>> solveNQueens(int n) {
        // 初始化棋盘
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                g[i][j] = '.';
            }
        }
        dfs(0, n);
        return ans;
    }
}

解法1

Thanks

@pirateutopia

N Queen Problem Using Backtracking Algorithm

此题应该使用回溯思想。

思路是这样的:

首先,我们构建一个n*n的字符矩阵,初始值赋为.

然后,进行递归调用,我们用一个字段来标识当前行row,初始值为0

接着进入递归函数内部。

第一步,我们的目标是什么?

一旦row == chess.length,就说明已经生成了一个答案。

所以,我们构建字符串列表,并将其放入最终结果列表ans中。

private List<String> construct(char[][] chess){
    List<String> child = new LinkedList<>();
    for (char[] ch: chess){
        child.add(new String(ch));
    }
    return child;
}

第二步,依次遍历每列。

需要判断当前位置是否允许放置皇后,判断的依据就是当前行、列、左右斜对角是否有皇后。

这边有个判断技巧:

假设当前单元的坐标为(row, col),左斜对角线的坐标为(i, j),有如下规律:

row - col == i - j

同理,右对角线有如下规律:

row + col == i + j

private boolean isValid(char[][] chess, int row, int col){
    for (int i = 0; i < chess.length; i++){
        for (int j = 0; j < chess[0].length; j++){
            if (chess[i][j] == 'Q' && (i - j == row - col || i + j == row + col ||  
                                       i == row || j == col)){
                return false;
            }
        }
    }
    return true;
}

最后,就是常规回溯操作。

来看下实现:

class Solution {
    public List<List<String>> solveNQueens(int n) {
        
        char[][] chess = new char[n][n];
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                chess[i][j] = '.';
            }
        }
        List<List<String>> ans = new LinkedList<>();
        bt(chess, ans, 0);
        return ans;
    }
    
    private void bt(char[][] chess, List<List<String>> ans, int row){
        
        // Goal
        if (row == chess.length){
            ans.add(construct(chess));
            return;
        }
        
        // Choice
        for (int col = 0; col < chess.length; col++){
            if (isValid(chess, row, col)){
                chess[row][col] = 'Q';
                bt(chess, ans, row + 1);
                chess[row][col] = '.';
            }
        }
    }
    
    private boolean isValid(char[][] chess, int row, int col){
        for (int i = 0; i < chess.length; i++){
            for (int j = 0; j < chess[0].length; j++){
                if (chess[i][j] == 'Q' && (i - j == row - col || j + i == col + row ||  
                                           i == row || j == col)){
                    return false;
                }
            }
        }
        return true;
    }
    
    private List<String> construct(char[][] chess){
        List<String> child = new LinkedList<>();
        for (char[] ch: chess){
            child.add(new String(ch));
        }
        return child;
    }
}

Enjoy it !


一位喜欢提问、尝试的程序员

(转载本站文章请注明作者和出处 姚屹晨-yaoyichen

Post Directory