51. N-Queens

class Solution: def solveNQueens(self, n): """ :type n: int :rtype: List[List[str]] """ remaining = n chosen = [] success_list = [] self.solveHelper(n, remaining, chosen, success_list) return self.print_queens(n, success_list) def solveHelper(self, n, remaining, chosen, success_list): """ 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 more choices to make. Just append the success to success list success_list.append(chosen) return else: positions = self.get_available_pos(n, chosen) # all available positions at current row if len(positions) == 0: return else: for pos in positions: # choose chosen.append(pos) # explore self.solveHelper(remaining-1, chosen) # unchoose chosen.pop() def get_available_pos(self, 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(self, n, success_list): """ Input a list of all successful configurations. Every configuration is a list, with index = row, value = which column to place queen at that row. Output: print out the actual board. """ all_res = [] for chosen in success_list: res = [] for col in chosen: row = "." * col + "Q" + "." * (n-col-1) # empty row res.append(row) all_res.append(res) return all_res