Leetcode 51. N-Queens

https://leetcode.com/problems/n-queens/

Classical problem for CS. Still DFS is a powerful tool for this problem. Besides, we already know that each line has a Q, so we can simplify the expression of board by only getting the column numbers. For example, [X Q X X, X X X Q, Q X X X, X X Q X] can be simplified as [1, 3, 0, 2]. Of course the 'X' is '.' in the problem, here only use 'X' to make it more readable.

Another aspect of this problem is how to judge the board is valid. Queen has 8 directions, checking one by one is too inefficient. Rows and columns are easy, while diagonal lines need some thought.

Solution 1 is an ordinary DFS solution, while solution 2 uses a lot Python's featured sentences and is much faster.

Solution 1:

# T:O(n!) S:O(n)
class Solution:
    # @param {integer} n
    # @return {string[][]}
    def solveNQueens(self, n):
        if n == 1:
            return [['Q']]
        Solution.ret = []
        def isValid(k, j):  # check if kth Q can be put on row k, col j
            for i in range(k):
                if board[i] == j or abs(k-i) == abs(board[i]-j):
                    return False
            return True
        
        def dfs(depth, result):
            if depth == n:
                Solution.ret.append(result)
                return
            for i in range(n):
                if isValid(depth, i):
                    board[depth] = i
                    tmp = '.' * n
                    dfs(depth + 1, result +[tmp[:i]+'Q'+tmp[i+1:]])
        board = [-1 for i in range(n)]
        dfs(0, [])
        return Solution.ret

Run Time: 196 ms

Solution 2:

# T:O(n!) S:O(n)
class Solution:
    # @return an integer
    def solveNQueens(self, n):
        self.cols = [False] * n
        self.main_diag = [False] * (2 * n)
        self.anti_diag = [False] * (2 * n)
        self.solutions = []
        self.solveNQueensRecu([], 0, n)
        return self.solutions

    
    def solveNQueensRecu(self, solution, row, n):
        if row == n:
            self.solutions.append(map(lambda x: '.' * x + "Q" + '.' * (n - x - 1), solution))
        else:
            for i in xrange(n):
                if not self.cols[i] and not self.main_diag[row + i] and not self.anti_diag[row - i + n]:
                    self.cols[i] = self.main_diag[row + i] = self.anti_diag[row - i + n] = True
                    self.solveNQueensRecu(solution + [i], row + 1, n)
                    self.cols[i] = self.main_diag[row + i] = self.anti_diag[row - i + n] = False

Run Time: 88 ms