首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >leetcode: 51. N-Queens

leetcode: 51. N-Queens

作者头像
JNingWei
发布2018-09-27 17:03:49
4300
发布2018-09-27 17:03:49
举报
文章被收录于专栏:JNing的专栏JNing的专栏

Problem

# The n-queens puzzle is the problem of placing n queens on
这里写图片描述
这里写图片描述
# an nxn chess board such that no two queens attack each other.
# 
# 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.
# 
# For example,
# There exist two distinct solutions to the 4-queens puzzle:
# 
# [
#  [".Q..",  // Solution 1
#   "...Q",
#   "Q...",
#   "..Q."],
# 
#  ["..Q.",  // Solution 2
#   "Q...",
#   "...Q",
#   ".Q.."]
# ]

Idea

1. 逐行放置皇后:排除在同一行的可能。
2. 记录之前所放皇后的列坐标:col[i]=j表示第i行的皇后在第j列。这样在放置第i+1行时,只要保证col[i+1] != col[k], k=0...i 即可。
3. 对角线判断:对于任意(i1, col[i1])和(i2, col[i2]),只有当abs(i1-i2) = abs(col[i1]-col[i2])时,两皇后才在同一对角线。

AC

class Solution():
    def solveNQueens(self, n):
        from functools import reduce
        def solveNQueensRecu(solution, row, n):
            if row == n:
                solutions.append(list(map(lambda x: '.' * x + "Q" + '.' * (n - x - 1), solution)))
            else:
                for i in range(n):
                    if i not in solution and reduce(lambda acc, j: abs(row - j) != abs(i - solution[j]) and acc, range(len(solution)), True):
                        solveNQueensRecu(solution + [i], row + 1, n)
        solutions = []
        solveNQueensRecu([], 0, n)
        return solutions


if __name__ == "__main__":
    assert Solution().solveNQueens(4) == [['.Q..', '...Q', 'Q...', '..Q.'], ['..Q.', 'Q...', '...Q', '.Q..']]
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2017年11月18日,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • Problem
    • Idea
    • AC
    领券
    问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档