51. N-Queens

class Solution: def solveNQueens(self, n): """ :type n: int :rtype: List[List[str]] """ def solveHelper(self, n, remaining, chosen): """ A helper function, in order to pass results as an argument. It returns a list, whose index is the row number and value indicates which column to place queen at that row. """ if remaining == 0: # no choice to make. Just return the result list. return chosen else: positions = get_available_pos(n, chosen) # all available positions at current row if len(positions) == 0: return -1 else: for pos in positions: # choose chosen.append(pos) # explore self.solveHelper(remaining-1, chosen) # unchoose chosen.pop() def get_available_pos(n, chosen): """ Input a list of what we have chosen. Return a list of available positions. """ available = [] curr_row_id = len(chosen) # just a coincidence that len(chosen) no need to +1. This var is the index of current row. for i in range(0, n): if i in chosen: # conflict with queen in this column continue elif (i + curr_row_id) in [chosen[j] + j for j in range(len(chosen))]: # conflict with left diagonal continue elif (i - curr_row_id) in [chosen[j] - j for j in range(len(chosen))]: # conflict with right diagonal continue else: available.append(i) return available def print_queens(chosen): """ Input a list of what we have chosen. Print out the actual board. """ res = []