N 皇后问题-一一网

Offer 驾到，掘友接招！我正在参与2022春招打卡活动，点击查看活动详情。

一、题目描述

设计一种算法，打印 N 皇后在 N × N 棋盘上的各种摆法，其中每个皇后都不同行、不同列，也不在对角线上。这里的“对角线”指的是所有的对角线，不只是平分整个棋盘的那两条对角线（图源网络）。

n皇后1.jpeg

示例

 输入：4
 输出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
 解释: 4 皇后问题存在如下两个不同的解法。
[
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
复制代码

二、思路分析

n 皇后题目无论在笔试还是面试，都是比较热门的题目，这也是 leetcode 平台上的一道标记为 hard 的题目。遇难题时我自己觉得首先还是不要慌，心平气静才是解题的关键。
看到题目要求时，第一时间可能会到 “暴力法” ，先确定一个皇后，并在她所映射到的行、列，斜线上都做下标记，然后再确定下一个皇后，最后重复此步骤。当棋盘上上没有位置可以容下皇后时，统计此时棋盘上的皇后数量，判断皇后数量能够否达到要求。
方案似乎是可行的，但是我们该如何去实现呢？如何标记不能容下皇后的位置？如何保证找到所有的解？
通过题目不难发现，每次摆放皇后之后，我们只需标记所再行 $x = x1$ ,所在列 $y = y1$ ,两条斜线可表示为 $y = x + b$ , $y = -x + b$ ，易知 $b$ 由唯一斜线上坐标确定。为保证包含全部解，我们可以用回溯法探索所有可能（图源网络）。

n皇后.jpeg

三、AC 代码

class Solution {
    Set<Integer> row = new HashSet<>(); // 行访问
    Set<Integer> col = new HashSet<>(); // 列访问
    Set<Integer> l1 = new HashSet<>();  // 斜向右下访问  由 y = -x + b 知 b 可控制 斜率为 -1 过点 (x,y) 的所有位置，下同。
    Set<Integer> l2 = new HashSet<>();  // 斜向左下访问  由 y =  x + b 知 ...
    List<List<String>> res = new ArrayList<>();
    List<String> t = new ArrayList<>();
    int n;
    String[] data;
    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        data = new String[n];
        StringBuilder sb = new StringBuilder();
        for (int i = 1; i < n; i++) {
            sb.append('.');
        }
        for (int i = 0; i < n; i++) {
            sb.insert(i,'Q');
            data[i] = sb.toString();
            sb.deleteCharAt(i);
        }
        for (int i = 0; i < n; i++) {
            backtrack(0,i);
        }
        return res;
    }

    private void backtrack(int i, int j) {
        if (i < 0 || i >= n || j < 0 || j >= n) return;
        if (row.contains(i) || col.contains(j) || l1.contains(i + j) || l2.contains(i - j)) return;
        t.add(data[j]);
        // 皇后数量符合题意。
        if (i == n - 1) {
            res.add(new ArrayList(t));
            t.remove(t.size() - 1);
            return;
        }
        // 记录不能够放置皇后的位置。
        row.add(i);
        col.add(j);
        l1.add(i + j);
        l2.add(i - j);
        for (int p = 0; p < n; p++) {
            backtrack(i + 1,p);
        }
        // 对以上行为进行撤销。
        row.remove(i);
        col.remove(j);
        l1.remove(i + j);
        l2.remove(i - j);
        t.remove(t.size() - 1);
    }
}
复制代码