2026-01-07 15:23:44 +0300 MSK

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        res = []
        state = [["."] * n for _ in range(n)]
    
        def backtrack(row: int, col: int, left: int) -> None:
            if left == 0: 
                res.append(tuple("".join(cur_row) for cur_row in state))
                return
            if row >= n or col >= n:
                return

            place = True
            for i in range(row):
                if state[i][col] == "Q":
                    place = False
                    break

            if place:
                cur_i, cur_j = row, col
                while cur_i >= 0 and cur_j >= 0:
                    if state[cur_i][cur_j] == "Q":
                        place = False
                        break
                    cur_i -= 1
                    cur_j -= 1
            
            if place:
                cur_i, cur_j = row, col
                while cur_i >= 0 and cur_j < n:
                    if state[cur_i][cur_j] == "Q":
                        place = False
                        break
                    cur_i -= 1
                    cur_j += 1

            if place:    
                state[row][col] = "Q"
                backtrack(row + 1, 0, left - 1)
                state[row][col] = "."
            
            if col + 1 == n:
                nxt_row, nxt_col = row + 1, 0
            else:
                nxt_row, nxt_col = row, col + 1
            backtrack(nxt_row, nxt_col, left)

        backtrack(0, 0, n)
        
        return res