• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

Backtracking

Contents

  • The Structure
  • Backtracking vs DFS
  • Backtracking vs B&B
  • Runtime Complexity
  • n Queens
  • Maze finding
  • Sudoku
  • See also
  • Footnotes

Backtracking is a concept for solving discrete constraint satisfaction problems (CSPs). Those problems don't have an optimal solution, but just solutions which satisfy the constraints. The idea of backtracking is to try a solution. If it doesn't work, go back and try something else.

Backtracking is often implemented with recursion, but does not need to use recursion.

The Structure

Typically, when you apply backtracking, it looks like this:

partial_solutions = [initial_solution_draft]  # stack or queue
while partial_solutions:
    partial_solution = partial_solutions.pop()
    if is_complete(partial_solution):
        return partial_solution
    for choice in choices(partial_solution):
        extended_solution = extend(partial_solution, choice)
        if is_valid(extended_solution):
            partial_solutions.append(extended_solution)
return None  # Constraints could not be satisfied

As you can see, it is essentially just a way to brute-force the problem.

The rest of the article consists of examples. I checked the n-queens example for correctness, but not the others.

Backtracking vs DFS

When you apply Backtracking, you first define a solution space. This might happen implicitly, e.g. by defining a data structure. For example, in the n-queens problem the solution space is all permutations of the number from 0 to (n-1). Everything else is guaranteed not to be a solution. And most of the permutations are also no solutions.

Depth First Search (DFS) is a graph traversal algorithm. It is one way to search in the solution space for a solution that satisfies the constraints. It is the typical choice to iterate the solution space. Other search algorithms are Breadth First Search (BFS) and A*.

Backtracking vs B&B

Branch-and-Bound (B&B) is a concept to solve discrete constrained optimization problems (COPs). They are similar to CSPs, but besides having the constraints they have an optimization criterion. In contrast to backtracking, B&B uses Breadth-First Search.

B&B is a label correction algorithm. It is a search algorithm which uses a lower bound and an upper bound for the search. Think of a shortest-path problem.

One part of the name, the bound, refers to the way B&B prunes the space of possible solutions: It gets a heuristic which gets an upper bound. If this cannot be improved, a sup-tree can be discarded.

With the lower bound, the minimum length of a given partial solution from source to sink can be calculated. If that minimum length is longer than another answer which was already found, then the calculation at that point can be aborted.

With the upper bound, one can extend the partial solutons. Essentially, one can make the pruning described before more efficient. We don't have to find a concrete solution anymore, but for partial solutions we already know the distance they will take at most.

Runtime Complexity

Assume that you have to go $n$ steps and at every step you have $a \geq 2$ choices. This means the runtime is exponential - $\mathcal{O}(\alpha^n)$.

If you add more rules to is_valid - excluding more solutions - you reduce $\alpha$. This can mean a huge speedup.

n Queens

The n Queens puzzle is probably the most common example. You have a n×n chess board and n queens. You need to place the queens on the chess board in such a way that they don't threaten each other.

A queen threatens another queen if it is…

  • … in the same row
  • … in the same column
  • … in the same diagonal

If you say that the first coordinate x is the row and the second one, y, is the column, then you can easily determine if they threaten each other:

from typing import List, Tuple


def all_n_queens_solutions(n: int) -> List[Tuple[int, ...]]:
    """
    Find all possible solutions to the n-queens problem.

    Parameters
    ----------
    n : int

    Returns
    -------
    all_solutions : List[List[int]]
        Each inner list represents a single solution.
        The first digit of it is the column of the queen in the first row.
        The second digit is the column of the queen in the second row, ...

    Note
    ----
    Columns are 0-based.

    Examples
    --------
    >>> all_n_queens_solutions(1)
    [(0,)]
    >>> all_n_queens_solutions(2)
    []
    >>> all_n_queens_solutions(3)
    []
    >>> all_n_queens_solutions(4)
    [(1, 3, 0, 2), (2, 0, 3, 1)]
    """
    solutions = []
    solution_queue: List[Tuple[int, ...]] = [()]  # contains valid partial solutions
    while solution_queue:
        solution = solution_queue.pop(0)
        if len(solution) < n:
            for i in range(n):
                if not is_new_threatening(solution, x=len(solution), y=i):
                    new_solution = solution + (i,)
                    solution_queue.append(new_solution)
        else:
            # It's finished!
            solutions.append(solution)
    return solutions


def is_new_threatening(solution: Tuple[int, ...], x: int, y: int) -> bool:
    for x_old, y_old in enumerate(solution):
        if is_threatening(x_old, y_old, x, y):
            return True
    return False


def is_threatening(x1: int, y1: int, x2: int, y2: int) -> bool:
    """
    Check if the positions are threatening each other.

    Examples
    --------
    >>> is_threatening(0, 1, 1, 0)
    True
    """
    same_row = x1 == x2
    same_col = y1 == y2

    delta1 = min(x1, y1)
    major_coords1 = (x1 - delta1, y1 - delta1)
    delta2 = min(x2, y2)
    major_coords2 = (x2 - delta2, y2 - delta2)
    same_diagonal_major = major_coords1 == major_coords2

    delta1 = x1
    delta2 = x2
    minor_coords1 = (x1 - delta1, y1 + delta1)
    minor_coords2 = (x2 - delta2, y2 + delta2)
    same_diagonal_minor = minor_coords1 == minor_coords2
    same_diagonal = same_diagonal_major or same_diagonal_minor
    return same_row or same_col or same_diagonal
n solutions (A000170)
1 1
2 0
3 0
4 2
5 10
6 4
7 40
8 92
9 352
10 724
11 2680
12 14200

Maze finding

In order to find a solution in a maze, one can apply depth first search (DFS). DFS can be seen as a specific form of backtracking (source).

from typing import Optional, List, Tuple


def find_way_out(
    maze, current_pos: Position, current_path: Tuple[Position, ...] = None
) -> Optional[Tuple[Position, ...]]:
    if is_exit(current_pos):
        return current_path
    if current_path is None:
        current_path = [current_pos]
    # Implement possible_paths for your problem
    for next_step in possible_paths(maze, current_pos):
        next_pos = step(current_pos, next_step)
        if next_pos == current_path[-1]:
            # We just came from this position
            continue
        solution = find_way_out(maze, next_pos, current_path + (next_pos,))
        if solution is None:
            return solution
    # We didn't find a way out
    return None

The reason why I used a tuple is to prevent modification. This way, I can be sure that the recursive calls work on copies.

Once Python hits a recurision depth of about 500, you will see a RecursionError. So if we need to make more than 500 steps, this will not work anymore. Hence an iterative soltuion is better. Please note that it is still backtracking and that it is still DFS. It's just not recursive anymore:

from typing import Optional, List, Tuple


def find_way_out(
    maze, current_pos: Position, current_path: Tuple[Position, ...] = None
) -> Optional[Tuple[Position, ...]]:
    if is_exit(current_pos):
        return current_path
    if current_path is None:
        current_path = [current_pos]
    explore = [(current_pos, current_path)]
    while explore and not is_exit(current_pos):
        current_pos, current_path = explore.pop()
        for next_step in possible_paths(maze, current_pos):
            next_pos = step(current_pos, next_step)
            if next_pos == current_path[-1]:
                # We just came from this position
                continue
            explore.append((next_pos, current_path + (next_pos,)))
    return None

Sudoku

from collections import Counter
from typing import List, Iterable, Optional, Tuple


class SudokuBoard:
    def __init__(board: List[List[int]]):
        # A board is a 9x9 matrix which has values in 1 to 9.
        # The value 0 denotes that the cell is empty
        assert len(board) == 9
        for row in board:
            assert len(row) == 9
            for el in row:
                assert 0 <= el <= 9
        self.board = board
        assert self.is_valid()

    def set(self, x: int, y: int, digit: int):
        assert self.board[x][y] == 0
        assert digit in list(range(1, 10))
        self.board[x][y] = digit
        if not self.validate_position(x, y):
            raise ValueError(f"You can't set {digit} at ({x}, {y})")

    def is_valid(self) -> bool:
        """Check if the sudoku-rule is fulfilled."""
        # Check Rows and columns
        for index in range(9):
            if not (self.validate_row(index) and self.validate_column(index)):
                return False

        # Check blocks
        for i in range(3):
            for j in range(3):
                # (i, j) is the top-left element of the block
                if not is_valid_sudoku_set(get_block(self.board, i, j)):
                    return False
        # All fine :-)
        return True

    def validate_row(self, row_index: int) -> bool:
        return is_valid_sudoku_set(self.board[row_index])

    def validate_column(self, column_index: int) -> bool:
        col = []
        for row_index in range(9):
            col.append(self.board[row_index][column_index])
        return is_valid_sudoku_set(col)

    def validate_position(self, x: int, y: int) -> bool:
        """Make sure the given position doesn't break the board."""
        if not (self.validate_row(x) and self.validate_column(y)):
            return False

        i = (x // 3) * 3
        j = (y // 3) * 3
        if not is_valid_sudoku_set(get_block(self.board, i, j)):
            return False
        return True

    def is_solved(self) -> bool:
        return all(el != 0 for row in self.board for el in row) and self.is_valid()

    def get_first_zero_position(self) -> Optional[Tuple[int, int]]:
        for row_index, row in enumerate(self.board):
            for col_index, element in enumerate(row):
                if element == 0:
                    return (row_index, col_index)


def is_valid_sudoku_set(numbers: Iterable) -> bool:
    c = Counter(numbers)
    for digit, count in c.items():
        if digit == 0:
            continue
        elif digit in [1, 2, 3, 4, 5, 6, 7, 8, 9]:
            if count > 1:
                return False
        else:
            raise RuntimeError(f"Value '{digit}' found, but expected int in [0, 9]")
    return True


def get_block(board: List[List[int]], i: int, j: int) -> Iterable[int]:
    for di in range(3):
        for dj in range(3):
            yield board[i + di][j + dj]


def solve_sudoko(board: SudokuBoard) -> Optional[SudokuBoard]:
    stack = [board]  # we want a DFS
    while stack:
        board = stack.pop()
        if board.is_solved():
            return board
        for x, y in board.get_first_zero_position():
            for digit in range(1, 10):
                new_board = SudokuBoard(copy(self.board))
                try:
                    new_board.set(x, y, digit)
                    stack.append(new_board)
                except ValueError:
                    # Setting digit at that position would make the board invalid
                    continue

You can solve Sudoku with GLPK, the GNU Linear Programming Kit, as well.

See also

  • Google OR-Tools: The N-queens Problem
  • cs.StackExchange: Backtracking vs Branch-and-Bound
  • StackOverflow: Difference between 'backtracking' and 'branch and bound'

Footnotes


  1. Kevin Buchin: Backtracking / Branch-and-Bound. In Algorithms (2IL15) – 2014. ↩

Published

Mär 30, 2020
by Martin Thoma

Category

Code

Tags

  • Algorithms 13
  • Backtracking 1
  • Branch-and-Bound 2
  • Constraint-satisfaction 2
  • COP 3
  • CSP 3
  • Operations Research 1

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor