51. N皇后

题目描述

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

上图为 8 皇后问题的一种解法。

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

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

示例:

输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

我的解法——递归（AC）

• 详见《程序员代码面试指南》

import copy

class Solution(object):
    def add_res(self, now_res):
        now_res_output = []
        for i in range(len(now_res)):
            now_step = ''
            left_count = now_res[i]
            right_count = self.n - now_res[i] - 1
            if(left_count):
                now_step += '.' * left_count
            now_step += 'Q'
            if(right_count):
                now_step += '.' * right_count
            now_res_output.append(now_step)
        self.res.append(now_res_output)

    def isvalid(self, now_res, now_step):
        for i in range(now_step - 1):
            if(abs(now_res[now_step - 1] - now_res[i]) == abs(now_step - 1 - i)):
                return False
        return True
    
    def dfs(self, now_res, now_rest_set):
        now_step = self.n - len(now_rest_set)
        if(now_step >= 2):
            for i in range(len(now_res)):
                if(not self.isvalid(now_res, now_step)):
                    return
        if(now_step == self.n):
            self.add_res(now_res)
            return
        for i in range(len(now_rest_set)):
            temp_rest_set = copy.deepcopy(now_rest_set)
            now_res[now_step] = temp_rest_set[i]
            del temp_rest_set[i]
            self.dfs(now_res, temp_rest_set)
            
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        self.res = []
        self.n = n
        now_res = [-1] * n
        now_rest_set = [i for i in range(n)]
        
        self.dfs(now_res, now_rest_set)
        return self.res

更好解法——位运算加速

• 详见《程序员代码面试指南》