算法与编码技巧 加入小组

7个成员 12个话题 创建时间:2018-07-03

N-Queens(N皇后问题)

发表于07-20 756次查看

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

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

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

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

示例:

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

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

 

链接:

1. 中文:https://leetcode-cn.com/problems/n-queens/description/

2. 英文:https://leetcode.com/problems/n-queens/description/

2回复
  • 2楼 wusheng 09-20

    老规矩,在学习Ryan老师的视频前,自己先写一个,时间有点长,花了3个小时,要是面试的话,估计就悲剧了,请大家帮忙看看写的渣的地方,或者逻辑不好的地方,谢谢!

    class Solution(object):
        def solveNQueens(self, n):
            """
            :type n: int
            :rtype: List[List[str]]
            """
            def ok_queen(i, j, last_i, last_j):
                if i == last_i or j == last_j:
                    return False
                if (i - last_i == j - last_j) or (i - last_i == last_j - j):
                    return False
                else:
                    return True
                return True
            def put_queen(i, j, queens_pos):
                ok = 0
                if j >= n:
                    return [False, False]
                if i >= n:
                    return [False, False]
                if len(queens_pos) == 0:
                    queens_pos.append([i, j])
                    return [i, j]
                for one_queen in queens_pos:
                    if ok_queen(i, j, one_queen[0], one_queen[1]):
                        ok += 1
                    else:
                        return put_queen(i, j+1, queens_pos)
                if ok == len(queens_pos):
                    queens_pos.append([i, j])
                    return [i, j]
            queens_pos = []
            save_pos = []
            i = 0; j = 0
            while i < n:
                col, row = put_queen(i, j, queens_pos)
                if not col is False:
                    if len(queens_pos) == n:
                        save_pos.append(["." * s[1] + "Q" + "." * (n - s[1] - 1)  for s in queens_pos])
                        j = row + 1
                        continue
                    i += 1
                    j = 0
                else:
                    if len(queens_pos) == 0:
                        break
                    i = queens_pos[-1][0]
                    j = queens_pos[-1][1] + 1
                    del queens_pos[-1]
            return save_pos

     

  • 3楼 wusheng 09-20

    leetcode执行时间:136 ms

发表回复
你还没有登录,请先 登录或 注册!
话题作者
解惑者学院首席讲师

新加组员