Skip to content

Instantly share code, notes, and snippets.

@swarooprath
Last active March 30, 2023 03:36
Show Gist options
  • Save swarooprath/b44d28ee7713b3defdd0f3bbf35732da to your computer and use it in GitHub Desktop.
Save swarooprath/b44d28ee7713b3defdd0f3bbf35732da to your computer and use it in GitHub Desktop.
Succint NQueen solution
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
def solve_helper(n, slate, new_col):
nonlocal result
if new_col >= n:
result.append(slate[:]) # copy the slate, else we will have empty lists in result as elements are removed from slate
else:
for new_row in filter(lambda nr: not is_attack(slate, nr, new_col), range(n)): # find the position where the new queen in the new column is not being attacked by existing queens on the board
slate.append(new_row)
solve_helper(n, slate, new_col+1) # find all possible positions for the queen on the next column
slate.pop()
def is_attack(slate, new_row, new_col): # slate is current configuration of queens, n is the next position of queen in len(slate) column
return any([row == new_row or abs(new_row - row) == (new_col - col) for col, row in enumerate(slate)])
def to_string(soln, n): # soln is a board configuration where queens do not attack each other, n is the size of board
return ["." * soln[i] + "Q" + "." * (n-soln[i]-1) for i in range(n)]
result = []
solve_helper(n, [], 0)
return [to_string(r, n) for r in result]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment