Package topics.backtracking

package topics.backtracking

Backtracking algorithms — systematic exploration of solution spaces with pruning.

Backtracking builds candidate solutions incrementally and abandons a branch ("backtracks") as soon as it determines the branch cannot lead to a valid solution. This avoids the full cost of brute-force enumeration.

Key Difference from Brute Force

Brute force generates every possible candidate before checking validity. Backtracking prunes invalid branches early, often reducing the effective search space from O(n!) or O(2ⁿ) to a much smaller subset.

When to Use Backtracking

• Constraint-satisfaction problems (N-Queens, Sudoku)
• Combinatorial enumeration (permutations, subsets)
• Path-finding on graphs (Hamiltonian path, knight's tour)

General Template

void backtrack(List<T> current, List<T> remaining) {
    if (isSolution(current)) { record(current); return; }
    for (T candidate : remaining) {
        if (isValid(current, candidate)) {
            current.add(candidate);
            backtrack(current, remaining without candidate);
            current.remove(candidate);   // undo
        }
    }
}

Classes in This Package

• ChessHorseAll — finds all knight's-tour paths
• ChessHorseOne — finds one knight's-tour path
• ChessQueensAll — finds all N-Queens solutions
• ChessQueensOne — finds one N-Queens solution
• Permutations — generates all permutations
• SubsetsGivenSum — finds subsets with a target sum

Related Packages

Package	Description
topics.backtracking.times	Execution-time benchmarks for backtracking algorithms.

Classes

Class	Description
ChessHorseAll	BACKTRACKING PROBLEM: THE HORSE JUMPING PROBLEM The program calculates all the ways of moving a horse through an entire chessboard of side n
ChessHorseOne	BACKTRACKING PROBLEM: THE HORSE JUMPING PROBLEM This program calculates all the ways of moving a horse through an entire chessboard of side n
ChessQueensAll	BACKTRACKING PROBLEM: THE PROBLEM OF THE N QUEENS This program calculates one way of placing n queens on a chessboard of side n
ChessQueensOne	BACKTRACKING PROBLEM: THE PROBLEM OF THE N QUEENS This program calculates one way of placing n queens on a chessboard of side n
Permutations	BACKTRACKING PROBLEM: PERMUTATIONS OF N ELEMENTS This program generates permutations of the integer elements that are in the vector v
SubsetsGivenSum	BACKTRACKING PROBLEM: SUBSETS OF A GIVEN SUM This program, given a set consisting of n different positive integers, computes all subsets which sum a given value c