51. N-Queens - Solved

class Solution: def solveNQueens(self, n): """ Loop through all rows Every solution is represented by a list The list index represent rows. """ success_list = placeQueens(n, 0, [], []) for elem in success_list: # every element has length = n print(elem) def placeQueens(n, rid, result, success_list): """ rid is the id of the current row result is what we have till now success_list is to store success histories """ if rid == (n-1): # reached the end success_list.append(result) # end return success_list else: positions = get_available_positions(n, rid, result) if len(positions) == 0: return [] # now rid != (n-1), so should be empty for pos in positions: result.append(pos) placeQueens(rid+1, result, success_list) def get_available_positions(n, rid, result): """ Helper function. Given previous results, get all possible positions current element can be at. Return a set. """ positions = set(range(n)) # all possible indexes restrictions = [] for i in range(rid): # loop till the current row. Check influence of all historical queens delta = rid - i # number of rows between the two queens left = result[i] - delta # restricted element on the left diagonal. Absolute index. middle = result[i] # restricted element in the vertical line. Absolute index. right = result[i] + delta # restricted element on the right diagonal. Absolute index if left >= 0: restrictions.append(left) if right <= n-1: restrictions.append(right) restrictions.append(middle) return positions - set(restrictions)