N-Queens problem is a typical application of backtracking algorithm. For backtracking, we need to figure out a way to represent the candidates, a way to generate all the possible candidates and accept those valid and reject those invalid.
In this solution, the representation of the candidate is a column vector "queens", where i = queen[j] is the column index of the queen in row j. Under this representation, the way to generate all candidates is just like generate all the permutation of vector [0...n-1].
Now the rest problem is to efficiently verify the candidate. By definition, two queens cannot be in the same row or same column or same back or forward slash lines. Our representation is already making sure there would never be two queens in a row. Therefore we only need 3 dynamic sets to maintain the currently available column, back and forward slash lines.
(1) The id of a column is its index range from 0 to n-1.
(2) The id of a back slash line "" is "col - row" or "x - y"
(3) The id of a forward slash line "/" is "col + row" or "x + y"
This way we can reject a candidate in O(1) time since we can use three hash tables or three boolean arrays as the dynamic sets we need.
def solveNQueens(self, n): ans =  queens = [-1] * n columns = [True] * n + [False] # || col with dummy for boundary back = [True] * n * 2 # \\ col - row forward = [True] * n * 2 # // col + row row = col = 0 while True: if columns[col] and back[col - row + n] and forward[col + row]: queens[row] = col columns[col] = back[col - row + n] = forward[col + row] = False row += 1 col = 0 if row == n: ans.append(['.' * q + 'Q' + '.' * (n - q - 1) for q in queens]) else: if row == n or col == n: if row == 0: return ans row -= 1 col = queens[row] columns[col] = back[col - row + n] = forward[col + row] = True col += 1 # 9 / 9 test cases passed. # Status: Accepted # Runtime: 76 ms # 98.45%
Iterative solution too, line by line. But slower than yours
def solveNQueens(self, n): results = [] for i in range(n): tmp =  for ares in results: newLine = [' '] * n for ki, kj in enumerate(ares): newLine[kj] = '.' if 0 <= ki + kj - i < n: newLine[ki + kj - i] = '.' # i + j == ki + kj if 0 <= i + kj - ki < n: newLine[i + kj - ki] = '.' # j - i == kj - ki for j in range(n): if newLine[j] == '.': continue tmp.append(ares+[j]) results = tmp return [['.'*j + 'Q' + '.'*(n-j-1) for j in ares] for ares in results]