文章目录

• 1. 题目
• 2. 思路
• • (1) 回溯法
• 3. 代码

1. 题目

2. 思路

(1) 回溯法

• 利用回溯法确定每一行中皇后的位置，由于回溯法遍历的是行，因此，可以不用记录行号，只记录列号、正对角线、反对角线即可。
• 关键在于如何唯一地表示某一对角线，行号-列号可以唯一地表示正对角线，行号+列号可以唯一地表示反对角线。

3. 代码

import java.util.*;

public class Test {
    public static void main(String[] args) {
    }
}

class Solution {
    public int n;
    public List<List<String>> res;
    public List<Integer> list;
    public Set<Integer> col;
    public Set<Integer> l1;
    public Set<Integer> l2;


    public List<List<String>> solveNQueens(int n) {
        this.n = n;
        res = new ArrayList<>();
        list = new ArrayList<>();
        col = new HashSet<>();
        l1 = new HashSet<>();
        l2 = new HashSet<>();
        backtrack(0);
        return res;
    }

    public void backtrack(int index) {
        if (index == n) {
            if (list.size() == n) {
                add();
            }
            return;
        }
        for (int i = 0; i < n; i++) {
            int ll1 = index - i;
            int ll2 = index + i;
            if (!col.contains(i) && !l1.contains(ll1) && !l2.contains(ll2)) {
                col.add(i);
                l1.add(ll1);
                l2.add(ll2);
                list.add(i);
                backtrack(index + 1);
                col.remove(i);
                l1.remove(ll1);
                l2.remove(ll2);
                list.remove(list.size() - 1);
            }
        }
    }

    public void add() {
        List<String> temp = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            char[] chars = new char[n];
            Arrays.fill(chars, '.');
            chars[list.get(i)] = 'Q';
            temp.add(String.valueOf(chars));
        }
        res.add(temp);
    }
}