Bactrack algorithms

Backtracking algorithm is used when there are multiple solutions to a problem and all solutions are desired. It uses brute force approach to recursively find all possible solutions to the problem and pick the ones matching a predefined set of conditions.

Solutions are found by constructing a tree structure called State Space Tree (SST) traversing Depth-First (DFS).

Abstract backtrack algorithm class

from abc import ABC, abstractmethod


class Backtrack(ABC):
    """
    This is a generic backtrack algorithms interface.

    It provides a template to solve a problem using backtrack algorithm.

    Derived class need to provide:
    * MIN_ITEMS: minimum number of items to ensure backtrack is feasible.
    """

    MIN_ITEMS = 2

    def __init__(self, items):
        if items < self.MIN_ITEMS:
            raise ValueError(f"Requires minimum {items} items")
        self.items = items
        self.state = []
        self.solutions = []
        self._solve()

    @abstractmethod
    def _get_candidates(self):
        pass

    def get(self):
        return self.solutions

    def _is_valid_state(self):
        return len(self.state) == self.items

    def _solve(self):
        if self._is_valid_state():
            self.solutions.append(self.state.copy())
            # print (f"Valid state: {state}")
            # return if only one valid solution is required

        for candidate in self._get_candidates():
            self.state.append(candidate)
            self._solve()
            # printf(f"backtracking from: {state}")
            self.state.remove(candidate)

Arrange seats for 2 Boys and 1 Girl

class python3.backtrack.ArrangeSeats(items)

Bases: Backtrack

Find all possible seat arrangements for 2 Boys and 1 Girl.

from .backtrack import Backtrack


class ArrangeSeats(Backtrack):
    """
    Find all possible seat arrangements for 2 Boys and 1 Girl.
    """

    OPTIONS = {"B1", "B2", "G1"}

    def _get_candidates(self):
        # constraint: girl cannot sit in the middle
        if len(self.state) > 1 and self.state[1] == "G1":
            return []
        return list(self.OPTIONS.difference(set(self.state)))

Place N Queens in (N x N) chess board

class python3.backtrack.NQueens(items)

Bases: Backtrack

Find valid solutions to place N queens in (N x N) chess board.

from .backtrack import Backtrack


class NQueens(Backtrack):
    """
    Find valid solutions to place N queens in (N x N) chess board.
    """

    MIN_ITEMS = 4

    def _get_candidates(self):
        candidates = set(range(self.items))
        if not self.state:
            return candidates

        next_row = len(self.state)
        for row, col in enumerate(self.state):
            # remove col indices in previous rows i.e. state
            candidates.discard(col)
            # discard diagonal candidates to current position
            dist = next_row - row
            candidates.discard(col + dist)
            candidates.discard(col - dist)
        return candidates