Question: https://oj.leetcode.com/problems/n-queens/
Question Name: N-Queens
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | class QueenSolution(object): ''' A class to store the intermediate status towards the N-Queen solutions ''' __slots__ = ("board","col","diagF", "diagB") def __init__(self, board, col, diagF, diagB): self.board = board * 1 # Board contents, board[i] means there is # a queen in position (i, board[i[) self.col = col # Used columns self.diagF = diagF # Used forward diagonal self.diagB = diagB # Used backward diagonal return def toForm(self): ''' Transfer the board from the class-inside formation to the required form. ''' res = [] size = len(self.board) for i in self.board: if i == -1: res.append("."*size) else: res.append("."*i + "Q" + "."*(size - i - 1)) return res class Solution: # @return a list of lists of string def solveNQueens(self, n): # Handle some special cases if n == 1: return [["Q"]] if n == 2 or n == 3: return [] result = [QueenSolution([-1]*n, 0, 0, 0)] for row in xrange(n): # Add the queens row by row temp = [] for preState in result: for col in xrange(n): # Try each position # Column conflicts if (1<<col) & preState.col != 0: continue diagF = 1 << (col - row + (n-1)) # Forward diagonal conflicts if diagF & preState.diagF != 0: continue diagB = 1 << (row + col) # Backward diagonal conflicts if diagB & preState.diagB != 0: continue # Find a valid intermediate status preState.board[row] = col temp.append(QueenSolution(preState.board, (1<<col) | preState.col, diagF | preState.diagF, diagB | preState.diagB)) result = temp # Prepare for working with the next row return [record.toForm() for record in result] |
Will your bitwise approach make the algorithm faster in terms of time complexity?
I think my algorithm runs O(N!), as same as permutation and it’s recursive as well…
No, time complexity is the same. In practice, bit operations might be faster.