Recursive and Iterative clean code with Bit Manipulation and Backtracking in python


  • 0

    The main idea is using maskCol, maskLDRU, maskLURD to represent the state of line cols, left-down to right-up, left-up to right-down each.

    Recursive solution

    class Solution(object):
        def search(self, x, maskCol, maskLDRU, maskLURD, n, r):
            for y in xrange(n):
                bitCol, bitLDRU, bitLURD = 1 << y, 1 << x + y, 1 << n - 1 + y - x
    
                if not (bitCol & maskCol or bitLDRU & maskLDRU or bitLURD & maskLURD):
                    r[x][y] = 'Q'
    
                    if x == n - 1:
                        self.r.append([''.join(row) for row in r])
                    else:
                        self.search(
                            x + 1, maskCol | bitCol, maskLDRU | bitLDRU,
                            maskLURD | bitLURD, n, r)
                    r[x][y] = '.'
    
        def solveNQueens(self, n):
            self.r = []
            self.search(0, 0, 0, 0, n, [['.'] * n for _ in xrange(n)])
            return self.r
    

    Iterative solution

    class Solution(object):
        def solveNQueens(self, n):
            r, stack, solution = [], [[0] * 5], [['.'] * n for _ in xrange(n)]
    
            while stack:
                x, y, maskCol, maskLDRU, maskLURD = stack.pop()
                solution[x][(n + y - 1) % n] = '.'
    
                bitCol, bitLDRU, bitLURD = 1 << y, 1 << x + y, 1 << n - 1 + y - x
                if not (bitCol & maskCol or bitLDRU & maskLDRU or bitLURD & maskLURD):
                    solution[x][y] = 'Q'
    
                    if x == n - 1:
                        r.append([''.join(row) for row in solution])
                    else:
                        if y + 1 < n:
                            stack.append([x, y + 1, maskCol, maskLDRU, maskLURD])
    
                        stack.append([
                            x + 1, 0, maskCol | bitCol, maskLDRU | bitLDRU,
                            maskLURD | bitLURD])
                        continue
    
                    solution[x][y] = '.'
    
                if y + 1 < n:
                    stack.append([x, y + 1, maskCol, maskLDRU, maskLURD])
    
            return r

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.