N Queen

Question

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.

xample There exist two distinct solutions to the 4-queens puzzle:

[

    [".Q..", // Solution 1

     "...Q",

     "Q...",

     "..Q."],

    ["..Q.", // Solution 2

     "Q...",

     "...Q",

     ".Q.."]

]

Challenge Can you do it without recursion?

Thoughts

reference

用一个n长度的array， 每个index表示row number, elment value表示column, 每次选不一样的row和column(用另一个usedArray来记录哪些column被选过)， 然后每次加入一个新的位置时，只需要check是否有任意两个queen在同一条斜线上

就变成了一个类似permutation的问题, 可以想象成从长度为n的存在n个integer的array里面取数，求他们的permutaion,只不过多了一个斜线的条件:w

Solution

class Solution:
    """
    Get all distinct N-Queen solutions
    @param n: The number of queens
    @return: All distinct solutions
    """
    def solveNQueens(self, n):
        # write your code here
        if not n:
            return []
        self.resultList = []
        row = []
        self.used = [False for i in range(n)]
        self.nQueenHelper(row, n)
        result = self.getMatrix(self.resultList, n)
        return result

    def getMatrix(self, resultList, n):
        result = []                                                                                                                       
        for i in range(len(resultList)):
            string = ""
            for j in range(n):
                string += "."
            matrix = [string for j in range(n)]
            for k in range(len(resultList[i])):
                st = matrix[k]
                st = list(st)
                index = resultList[i][k]
                st[index] = "Q"
                matrix[k] = "".join(st)
            result.append(matrix)
        return result


    def nQueenHelper(self, row, n):
        if len(row) == n:
            newList = list(row)
            self.resultList.append(newList)

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

    def checkValid(self, row):                                                
        length = len(row)
        for i in range(length):
            for j in range(i+1, length):
                if abs(row[j] - row[i]) == abs(j-i):
                    return False
        return True

N Queen II

输出所有的valid的个数

简单，记录下个数就可以