算法题--8皇后问题II

image.png

0. 链接

题目链接

1. 题目

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

8皇后示例

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

Example:

Input: 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown below.
[
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

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

2. 思路1：回溯法-深度优先搜索

要把8个皇后放到8*8格子里，可以展望最终结果，必定每行一个，否则就有两个同行，违反规则;

既然每行都有一个，那么只要依次决定8个皇后所在的列数, 这样就可以转化为一维数组来表示结果

记

queens[i] 表示第i行皇后所在的列号

问题答案的深度优先搜索过程如下所示:

1. 假设第1行的皇后的列数为1~8
2. 对于第1行皇后列数为1,则第2行皇后的待选位置，需要排除掉第1行同列的1和对角线的2，只剩下{3, 4, 5, 6, 7, 8}
3. 对于第2行皇后的列数3，则第3行皇后的列数，需要排除掉第1行皇后的同列1和同对角线3，还要排除掉第2行皇后的同列3和同对角线2和4, 这样，只剩下{5,6,7,8}
4. 当没有将所有皇后的位置确定，就发生了待选位置为空的情况时，则说明前面的选择有问题，则需要取消上一步的假设
5. 当所有皇后都找到了位置，那么我们就找到了一个符合条件的答案

3. 代码

# coding:utf8
from typing import List


class Solution:
    def dfs(self, i, n, queens, records):
        # 记录答案与控制递归深度
        if i >= n:
            records.append(self.format_record(n, queens))
        else:
            for j in range(n):
                # 判断之前定下的皇后是否含有同列
                if j in queens:
                    continue

                # 判断之前定下的皇后是否含有同对角线
                flag = False
                for k in range(len(queens)):
                    if abs(i - k) == abs(j - queens[k]):
                        flag = True
                        break
                if flag:
                    continue

                # 递归与回溯
                queens.append(j)
                self.dfs(i + 1, n, queens, records)
                queens.pop()

    def format_record(self, n, record):
        rtn_list = list()
        for i in range(n):
            each_list = ['.'] * n
            each_list[record[i]] = 'Q'
            rtn_list.append(''.join(each_list))

        return rtn_list

    def totalNQueens(self, n: int) -> int:
        records = list()
        self.dfs(0, n, list(), records)
        return len(records)


solution = Solution()
print(solution.totalNQueens(8))

输出结果

92

4. 结果

image.png