# python - n-queens - using bitmasks

• ``````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)

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)] , {}