【LeetCode】0051&0052 N皇后

https://leetcode-cn.com/problems/n-queens/

# -*- coding:utf-8 -*-

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        def check(i, j, temp_dir):
            for x in range(n):
                # 检查横竖
                if temp_dir[x][j] is 'Q' or temp_dir[i][x] is 'Q':
                    return False
                # 检查右上斜线
                if i + x < n and j - x >= 0:
                    if temp_dir[i + x][j - x] is 'Q':
                        return False
                # 检查左下斜线
                if i - x >= 0 and j + x < n:
                    if temp_dir[i - x][j + x] is 'Q':
                        return False
                # 检查左上斜线
                if i - x >= 0 and j - x >= 0:
                    if temp_dir[i - x][j - x] is 'Q':
                        return False
                # 检查右下斜线
                if i + x < n and j + x < n:
                    if temp_dir[i + x][j + x] is 'Q':
                        return False
            return True
        def back(x, from_x_idx, temp_dir):
            if x == n:
                import copy
                res.append(copy.deepcopy(temp_dir))
                return
            if from_x_idx > n - 1:
                return
            for i in range(from_x_idx, n):
                for j in range(n):
                    if temp_dir[i][j] is not 'Q' and check(i, j, temp_dir):
                        temp_dir[i][j] = 'Q'
                        back(x + 1, i + 1, temp_dir[:])
                        temp_dir[i][j] = '.'
        res = []
        init_map = [['.' for _ in range(n)] for _ in range(n)]
        back(0, 0, init_map)
        res_final = []
        for i in range(len(res)):
            temp_res = []
            for j in range(n):
                temp_res.append("".join(res[i][j]))
            res_final.append(temp_res)
        return res_final
if __name__ == '__main__':
    n = 8
    print(Solution().solveNQueens(n))

思路：回溯法，判断当前位置是否可以摆放然后一步一步回溯即可。

值得提出的是，由于对于较大的n运行时间较长，因此要进行状态压缩也就是剪枝，比如当前位置的横纵斜不需要判断，比当前位置的x坐标小的不需要判断等。可以再做一个可访问地图剪枝即可。

0052 求个长度即可。