Last active
March 30, 2023 03:36
-
-
Save swarooprath/b44d28ee7713b3defdd0f3bbf35732da to your computer and use it in GitHub Desktop.
Succint NQueen solution
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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