n_queens
1# @leet start 2class Solution: 3 def solveNQueens(self, n: int) -> list[list[str]]: 4 """ 5 This problem involves backtracking, where we have a choice on every square 6 to either place a queen or not on the current square. 7 We need to verify if the move is legal, and then try to place the square 8 if it is, we place the queen and recurse through the rest of the board. 9 This has $O(n!)$ time complexity and $O(n^2)$ space complexity. 10 """ 11 12 def create_board(state): 13 return ["".join(row) for row in state] 14 15 def backtrack(row, diagonals, anti_diagonals, cols, state): 16 if row == n: 17 ans.append(create_board(state)) 18 return 19 20 for col in range(n): 21 curr_diagonal = row - col 22 curr_anti_diagonal = row + col 23 24 invalid_col = col in cols 25 invalid_diagonal = curr_diagonal in diagonals 26 invalid_anti_diagonal = curr_anti_diagonal in anti_diagonals 27 28 if invalid_col or invalid_diagonal or invalid_anti_diagonal: 29 continue 30 31 cols.add(col) 32 diagonals.add(curr_diagonal) 33 anti_diagonals.add(curr_anti_diagonal) 34 state[row][col] = "Q" 35 36 backtrack(row + 1, diagonals, anti_diagonals, cols, state) 37 38 cols.remove(col) 39 diagonals.remove(curr_diagonal) 40 anti_diagonals.remove(curr_anti_diagonal) 41 state[row][col] = "." 42 43 ans = [] 44 empty = [["."] * n for _ in range(n)] 45 backtrack(0, set(), set(), set(), empty) 46 return ans 47 48 49# @leet end 50 51 52def test(): 53 assert 2 + 2 == 4
class
Solution:
3class Solution: 4 def solveNQueens(self, n: int) -> list[list[str]]: 5 """ 6 This problem involves backtracking, where we have a choice on every square 7 to either place a queen or not on the current square. 8 We need to verify if the move is legal, and then try to place the square 9 if it is, we place the queen and recurse through the rest of the board. 10 This has $O(n!)$ time complexity and $O(n^2)$ space complexity. 11 """ 12 13 def create_board(state): 14 return ["".join(row) for row in state] 15 16 def backtrack(row, diagonals, anti_diagonals, cols, state): 17 if row == n: 18 ans.append(create_board(state)) 19 return 20 21 for col in range(n): 22 curr_diagonal = row - col 23 curr_anti_diagonal = row + col 24 25 invalid_col = col in cols 26 invalid_diagonal = curr_diagonal in diagonals 27 invalid_anti_diagonal = curr_anti_diagonal in anti_diagonals 28 29 if invalid_col or invalid_diagonal or invalid_anti_diagonal: 30 continue 31 32 cols.add(col) 33 diagonals.add(curr_diagonal) 34 anti_diagonals.add(curr_anti_diagonal) 35 state[row][col] = "Q" 36 37 backtrack(row + 1, diagonals, anti_diagonals, cols, state) 38 39 cols.remove(col) 40 diagonals.remove(curr_diagonal) 41 anti_diagonals.remove(curr_anti_diagonal) 42 state[row][col] = "." 43 44 ans = [] 45 empty = [["."] * n for _ in range(n)] 46 backtrack(0, set(), set(), set(), empty) 47 return ans
def
solveNQueens(self, n: int) -> list[list[str]]:
4 def solveNQueens(self, n: int) -> list[list[str]]: 5 """ 6 This problem involves backtracking, where we have a choice on every square 7 to either place a queen or not on the current square. 8 We need to verify if the move is legal, and then try to place the square 9 if it is, we place the queen and recurse through the rest of the board. 10 This has $O(n!)$ time complexity and $O(n^2)$ space complexity. 11 """ 12 13 def create_board(state): 14 return ["".join(row) for row in state] 15 16 def backtrack(row, diagonals, anti_diagonals, cols, state): 17 if row == n: 18 ans.append(create_board(state)) 19 return 20 21 for col in range(n): 22 curr_diagonal = row - col 23 curr_anti_diagonal = row + col 24 25 invalid_col = col in cols 26 invalid_diagonal = curr_diagonal in diagonals 27 invalid_anti_diagonal = curr_anti_diagonal in anti_diagonals 28 29 if invalid_col or invalid_diagonal or invalid_anti_diagonal: 30 continue 31 32 cols.add(col) 33 diagonals.add(curr_diagonal) 34 anti_diagonals.add(curr_anti_diagonal) 35 state[row][col] = "Q" 36 37 backtrack(row + 1, diagonals, anti_diagonals, cols, state) 38 39 cols.remove(col) 40 diagonals.remove(curr_diagonal) 41 anti_diagonals.remove(curr_anti_diagonal) 42 state[row][col] = "." 43 44 ans = [] 45 empty = [["."] * n for _ in range(n)] 46 backtrack(0, set(), set(), set(), empty) 47 return ans
This problem involves backtracking, where we have a choice on every square to either place a queen or not on the current square. We need to verify if the move is legal, and then try to place the square if it is, we place the queen and recurse through the rest of the board. This has $O(n!)$ time complexity and $O(n^2)$ space complexity.
def
test():