Implement Backtracking SearchStep 5 of 5

N-Queens Count

12345

Step 5 - solve_n_queens

Implement solve_n_queens(n), returning the COUNT of distinct solutions as a single integer.

Place one queen per row. A column is safe when its column index and both diagonals, tracked as (row - col) and (row + col), are unused. Backtrack row by row and increment a counter each time row == n.

n = 4 gives 2, n = 1 gives 1, and n = 2 and n = 3 both give 0.

Hints
Starter code
def subsets(nums):
    res = []
    path = []
    def bt(start):
        res.append(list(path))
        for i in range(start, len(nums)):
            path.append(nums[i])
            bt(i + 1)
            path.pop()
    bt(0)
    return res


def permutations(nums):
    res = []
    used = [False] * len(nums)
    path = []
    def bt():
        if len(path) == len(nums):
            res.append(list(path))
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            path.append(nums[i])
            bt()
            path.pop()
            used[i] = False
    bt()
    return res


def combinations(n, k):
    res = []
    path = []
    def bt(start):
        if len(path) == k:
            res.append(list(path))
            return
        for i in range(start, n + 1):
            path.append(i)
            bt(i + 1)
            path.pop()
    bt(1)
    return res


def combination_sum(candidates, target):
    res = []
    path = []
    def bt(start, remaining):
        if remaining == 0:
            res.append(list(path))
            return
        if remaining < 0:
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            bt(i, remaining - candidates[i])
            path.pop()
    bt(0, target)
    return res


def solve_n_queens(n):
    """Return the COUNT of distinct solutions to the n-queens puzzle.

    Place one queen per row; a column is safe when its column and both
    diagonals are unused.
    """
    # TODO: backtrack row by row using sets for columns and the two
    #       diagonals (row - col) and (row + col); increment a counter
    #       when row == n.
    pass
Write it on a laptop

The editor and the test runner need a wide screen. Open this page on a desktop browser and your progress will be waiting.

PreviousAll challenges