Concise Python Backtracking


  • 0

    Since we're traversing by row, we just need to keep hashtables of columns, and diagonals used. In storing diagonals, we can use the pattern where all down-to-up( / ) cells will have a distinct row + col sum for each diagonal. For up-to-down diagonal cells ( \ ) I just reduce the position to the most up-left position and store that.

        def solveNQueens(self, n):
    
            def backtrack(r, C, U, D, board, n, res):
                if r == n:
                    res.append([''.join(r) for r in board])
                else:
                    for c in range(n):
                        u, d = r + c, (r-c, 0) if r > c else (0, c-r) 
                        if c not in C and u not in U and d not in D:
                            board[r][c] = 'Q'
                            C.add(c); U.add(u); D.add(d)
                            backtrack(r+1, C, U, D, board, n, res)
                            C.remove(c); U.remove(u); D.remove(d)
                            board[r][c] = '.'
            
            if not n: return []
            board = [["." for _ in range(n)] for _ in range(n)]
            res = []
            backtrack(0, set(), set(), set(), board, n, res)
            return res
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.