【LeetCode with Python】 51. N-Queens

题目

原题页面:https://oj.leetcode.com/problems/n-queens/
本文地址:http://leetcode.xnerv.wang/n-queens/
题目类型:Backtracking
难度评价:Hard
类似题目:(H) N-Queens II

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

8-queens

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:

<br/> [<br/> [".Q..", // Solution 1<br/> "...Q",<br/> "Q...",<br/> "..Q."],
<br/> ["..Q.", // Solution 2<br/> "Q...",<br/> "...Q",<br/> ".Q.."]<br/> ]


分析

下标计算处理,控制好循环条件,下标不要越界即可。


代码

class Solution:

    def __init__(self):
        self.paths = [ ]

    def dpSolveNQueens(self, n, prefix, level):
        for i in range(0, n):
            point = (i, level)
            is_valid = True
            for m in range(0, len(prefix)):
                if i == prefix[m]:
                    is_valid = False
                    break
                if level - m == i - prefix[m] or level - m == prefix[m] - i:
                    is_valid = False
                    break
            if is_valid:
                new_prefix = prefix[:]
                new_prefix.append(i)
                if n - 1 != level:
                    self.dpSolveNQueens(n, new_prefix, level + 1)
                else:
                    self.paths.append(new_prefix)

    # @return a list of lists of string
    def solveNQueens(self, n):
        self.dpSolveNQueens(n, [ ], 0)
        lists = [ ]
        for path in self.paths:
            list = [ ]
            for num in path:
                str = "." * num + "Q" + "." * (n - num - 1)
                list.append(str)
            lists.append(list)
        return lists

results matching ""

    No results matching ""