【LeetCode with Python】 N-Queens

2367 단어 LeetCodewithPython
블 로그 도 메 인 이름:http://www.xnerv.wang
원본 페이지:https://oj.leetcode.com/problems/n-queens/
제목 종류:
난이도 평가:★
본문 주소:http://blog.csdn.net/nerv3x3/article/details/39453349
The n-queens puzzle is the problem of placing n queens on ann×n chessboard such that no two queens attack each other.
【LeetCode with Python】 N-Queens_第1张图片
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.."]
]
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

좋은 웹페이지 즐겨찾기