python - n-queens - using bitmasks


  • 0
    S
    class Solution(object):
        
        def get_bit(self, x,y,board):
            return (1 & (board[x] >> (63-y)) )
        
        def set_bit(self, x,y,board):
            board[x] |= (1 << (63-y) ) 
            return
        
        def do_n_queens(self, n, queens, board, next_row, answer):
            
            if len(queens) == n:
    
                new_board, checksum = [], ''
                for pos in sorted(queens):
                    
                    j, s = pos[1], []
                    for y in range(n):
                        s += 'Q' if y == j else '.'
                        
                    new_board.append(''.join(s))
                    checksum += ''.join(s)
                
                if checksum not in answer:
                    answer[checksum] = new_board
                return
            
            for i in xrange(next_row, next_row+1):
                for j in xrange(n):
                    if self.get_bit(i,j, board) == 0:
                        
                        new_board = board[:] 
                        self.set_bit(i,j, new_board)
                        
                        # block vertically
                        for x in xrange(n):
                            self.set_bit(x,j,new_board)
                                
                        # block diagonally downward to right
                        x,y = i-1, j-1
                        while x > -1 and y > -1:
                            self.set_bit(x,y,new_board)
                            x,y = x-1, y-1                     
                        x,y = i+1, j+1
                        while x < n and y < n:
                            self.set_bit(x,y,new_board)
                            x,y = x+1, y+1
                        
                        # block diagonally upward to right
                        x,y = i-1, j+1
                        while x > -1 and y < n:
                            self.set_bit(x,y,new_board)
                            x,y = x-1, y+1
                        x,y = i+1, j-1
                        while x < n and y > -1:
                            self.set_bit(x,y,new_board)
                            x,y = x+1, y-1
                                            
                        self.do_n_queens(n, queens + [(i,j)], new_board, next_row+1, answer)                  
                        
        def solveNQueens(self, n):
            """
            :type n: int
            :rtype: List[List[str]]
            """
            # board is an array of n 64-bit integers
            queens, board, answer = [], [0 for _ in xrange(n)] , {}
            self.do_n_queens(n, queens, board, 0, answer)
            
            return answer.values()
    
                    
                
    

Log in to reply
 

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