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 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.."]
]

Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

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

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

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

记

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

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

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

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 solveNQueens(self, n: int) -> List[List[str]]:
        records = list()
        self.dfs(0, n, list(), records)
        return records


def print_list(n, l: List[List[str]]):
    print("题目: n={}".format(n))
    print("=" * 30)
    for i, each_list in enumerate(l):
        print("答案{}".format(i + 1))
        print(each_list)
    print("=" * 30)
    print()


solution = Solution()
n_list = [5]
for n in n_list:
    print_list(n, solution.solveNQueens(n))

输出结果

题目: n=5
==============================
答案1
['Q....', '..Q..', '....Q', '.Q...', '...Q.']
答案2
['Q....', '...Q.', '.Q...', '....Q', '..Q..']
答案3
['.Q...', '...Q.', 'Q....', '..Q..', '....Q']
答案4
['.Q...', '....Q', '..Q..', 'Q....', '...Q.']
答案5
['..Q..', 'Q....', '...Q.', '.Q...', '....Q']
答案6
['..Q..', '....Q', '.Q...', '...Q.', 'Q....']
答案7
['...Q.', 'Q....', '..Q..', '....Q', '.Q...']
答案8
['...Q.', '.Q...', '....Q', '..Q..', 'Q....']
答案9
['....Q', '.Q...', '...Q.', 'Q....', '..Q..']
答案10
['....Q', '..Q..', 'Q....', '...Q.', '.Q...']