leetcode刷题-51N皇后

题目

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。

给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。

思路

这道题思路与37解数独完全一致，利用约束条件和回溯来解题，不同之处在于数独是唯一解，n皇后问题是多解。

因此程序不会中途停止，而是在成功后记录，继续删除现有元素，继续解题。

实现

class Solution:
    def solveNQueens(self, n) :
        table = [[False for _ in range(n)] for j in range(n)]
        result = [['.' for _ in range(n)] for j in range(n)]
        answer = []
        checkflag = False

        def put(i, j):
            tmp = []
            tmp1 = i + j
            tmp2 = i - j
            for l in range(n):
                for m in range(n):
                    if l == i or m == j or l + m == tmp1 or l - m == tmp2:
                        if table[l][m] == False:
                            table[l][m] = True
                            tmp.append((l, m))
            result[i][j] = "Q"
            return tmp

        def remove(i, j, tmp):
            for x in tmp:
                l = x[0]
                m = x[1]
                table[l][m] = False
            result[i][j] = "."

        def valid(i, j):
            if table[i][j] is False:
                return True

        def check(i, j):
            if i == n-1:
                res = []
                for w in result:
                    strtmp = "".join(w)
                    res.append(strtmp)
                answer.append(res)
                nonlocal checkflag
                checkflag = True
            else:
                for x in range(n):
                    backtrace(i + 1, x)


        def backtrace(row, col):
            #if result[row][col] == '.':
            if valid(row, col):
                tmp = put(row, col)
                check(row, col)
                remove(row, col, tmp)
        
        for t in range(n):
            backtrace(0, t)
            checkflag = False
            table = [[False for _ in range(n)] for j in range(n)]
            result = [['.' for _ in range(n)] for j in range(n)]
        return answer