LC 37 & LC 51

Solution to LeetCode 37 Sudoku Solver and LeetCode 51 N-Queens.

LeetCode 37

Sudoku Solver (Hard) [link]

LeetCode 51

N-Queens (Hard). [link]

We use a recursion tree to decide where to put the queen for each row. The depth and the width of the tree are O(n). The stopping criteria is 1) queens in the same row, 2) queens in the same column, 3) queens in the same diagonal line.

class Solution:
    def solveNQueens(self, n: int) -> List[List[str]]:
        if not n: return []
        board = [['.']*n for _ in range(n)]
        res = []

        def isValid(board, row, col):
            # check col
            for i in range(n):
                if board[i][col] == 'Q':
                    return False
            # check upper left
            i = row-1
            j = col-1
            while i >= 0 and j >= 0:
                if board[i][j] == 'Q':
                    return False
                i -= 1
                j -= 1
            # check upper right
            i = row-1
            j = col+1
            while i >=0 and j < n:
                if board[i][j] == 'Q':
                    return False
                i -= 1
                j += 1
            return True
            
        def backtrack(board, row, n):
            if row == n:
                tmp_res = []
                for tmp in board:
                    tmp_res.append("".join(tmp))
                res.append(tmp_res)
                return 
            
            for col in range(n):
                if not isValid(board, row, col):
                    continue
                board[row][col] = "Q"
                backtrack(board, row+1, n)
                board[row][col] = "."

        backtrack(board, 0, n)
        return res