Knight's Tour Solver
Implementations and analysis of the Knight's Tour — Warnsdorff's heuristic, DFS backtracking, and a 3D generalization, with path visualizations across board sizes.
Overview
The Knight's Tour asks whether a knight can visit every square of a chessboard exactly once — an open tour ends anywhere, a closed tour returns to its start. This project collects several approaches to solving it, from a naive depth-first search to degree-based heuristics, alongside visualizations of the resulting paths.
Approach
- Warnsdorff's Rule (
Warnsdoff.ipynb) — a greedy heuristic that always steps to the square with the fewest onward moves (minimum degree), with experiments comparing tie-breaking strategies to keep the search from stalling. - DFS + backtracking (
simple.py) — a brute-force baseline that explores paths and backtracks at dead ends, bounds-checked for an 8×8 board. - Universal framework (
Universal.ipynb) — the same heuristics generalized across board sizes and shapes. - 3D extension (
3D_general.ipynb) — the tour lifted onto a three-dimensional board, with new movement rules and the added combinatorial complexity that brings.
A written guide (matrix overlays, degree heuristics, historical context) accompanies the code, and the work was presented as Hamiltonian Knight Tours (with Devin and Josh) — the full deck is below.
Tours, drawn
The path plots are the payoff — the same algorithm's character at three scales, then the jump to three dimensions.
The presentation
