0052-n-queens-ii

Try it on leetcode

Description

The n-queens puzzle is the problem of placing n queens on an n x n chessboard such that no two queens attack each other.

Given an integer n, return the number of distinct solutions to the n-queens puzzle.

 

Example 1:

Input: n = 4
Output: 2
Explanation: There are two distinct solutions to the 4-queens puzzle as shown.

Example 2:

Input: n = 1
Output: 1

 

Constraints:

  • 1 <= n <= 9

Solution(Python)

class Solution:
    def __init__(self):
        self.lookup = {}
        for i in range(1, 10):
            self.lookup[i] = self.__totalNQueens(i)

    def totalNQueens(self, n: int) -> int:
        return self.lookup[n]
    def __totalNQueens(self, n: int) -> int:
        board = [[0] * n for _ in range(n)]
        res = 0
        def is_valid(row, col):
            # Check same column
            for r in range(row):
                if board[r][col] == 1:
                    return False

            # Check upper-left diagonal
            r, c = row - 1, col - 1
            while r >= 0 and c >= 0:
                if board[r][c] == 1:
                    return False
                r -= 1
                c -= 1

            # Check upper-right diagonal
            r, c = row - 1, col + 1
            while r >= 0 and c < n:
                if board[r][c] == 1:
                    return False
                r -= 1
                c += 1

            return True
        def backtrack(row):
            if row == n:
                return 1

            count = 0

            for col in range(n):
                if is_valid(row, col):
                    board[row][col] = 1

                    count += backtrack(row + 1)

                    board[row][col] = 0

            return count
        return backtrack(0)

Dry Run