N Queen

题目描述

The n-queens puzzle is the problem of placing n queens on an n×n chessboard 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.."]
]

解题方法

N queen的规则是任意两个queen都不能攻击到彼此，而queen的攻击路线是直线或者对角线上，所以需要check的有

• 行
• 列
• 对角线

其实就类似于sudoku问题，sudoku是检查行，列和小的正方形. 这里不像sudoku那样填入到一个matrix里，当然如果我们自己 建一个matrix也是可以的，但是我们并不需要记录那么多的信息，只需要记录queen的位置，并且方便check valid就可以了。

我们可以用一个array来保存queen的信息，array的index表示行，而value就表示列，因为填入n个queen到n*n里的，其实也就是 依次每行填入一个queen,而列的选择也是在n的范围内，就变成了一个找出n的permutation的问题（这里多的条件是要满足 对角线没有queen的条件，所以要加一个check）。

• row array记录信息
• used array记录用过的column number
• 每填入一个number的时候要check对角线的条件是否满足

Solution

class Solution(object):
    def solveNQueens(self, n):
        """
        :type n: int
        :rtype: List[List[str]]
        """
        if not n:
            return [[]]
        row = []
        used = [False for i in range(n)]
        results = []

        self.helper(results, row, used, n)
        results = self.getMatrix(results, n)
        return results

    def helper(self, results, row, used, n):
        if len(row) == n:
            newList = list(row)
            results.append(newList)

        for j in range(n):
            if not used[j]:
                row.append(j)
                if self.checkValid(row):
                    used[j] = True
                    self.helper(results, row, used, n)
                    row.pop()
                    used[j] = False
                else:
                    row.pop()

    # check 是否斜线上有两个queen
    def checkValid(self, row):
        length = len(row)
        for i in range(length):
            for j in range(i + 1, length):
                if abs(row[i] - row[j]) == abs(i-j):
                    return False
        return True

    # 用于得到最后的".......Q."形式的结果
    def getMatrix(self, results, n):
        result = []                                                                                                                       
        for i in range(len(results)):
            string = ""
            for j in range(n):
                string += "."
            matrix = [string for j in range(n)]
            for k in range(len(results[i])):
                st = matrix[k]
                st = list(st)
                index = results[i][k]
                st[index] = "Q"
                matrix[k] = "".join(st)
            result.append(matrix)
        return result

Reference