🧩 Constraint Solving POTD:Problem of the Day: Knight's Tour Problem

[github-actions[bot]]

Problem Statement

The Knight's Tour problem asks: can a knight on a chessboard visit every square exactly once, moving according to chess rules (an L-shaped move: two squares in one direction, one square perpendicular)?

Concrete Instance:
On a standard 8×8 chessboard, find a sequence of 64 knight moves starting from square (1,1) that visits each of the 64 squares exactly once. One famous solution is the closed tour, where the knight can return to its starting square in one final move.

Input/Output:

• Input: Board size n×n, starting position (optional)
• Output: Sequence of positions [(x1,y1), (x2,y2), ..., (xn2,yn2)] representing a valid knight's tour, or "no solution" if none exists

Note: The problem is complete for certain board sizes (e.g., 8×8 always has a tour) but is NP-hard in general; solutions may not exist for small boards like 3×3.

---

Why It Matters

Historical significance: The Knight's Tour has fascinated mathematicians since the 9th century and appears in recreational mathematics, puzzle design, and algorithmic game theory.

Real-world applications:

• Robot motion planning: Scheduling collision-free paths for robotic arms or drones through discretized workspace grids
• Network routing & circuit design: Finding Hamiltonian-like paths in connectivity graphs
• Game AI: Strategic pathfinding in turn-based board games and puzzle solvers

---

Modeling Approaches

Approach 1: Constraint Programming (Graph-Based Model)

Decision variables:

• position[t] ∈ {1..n2} for each step t ∈ {1..n2}: the square visited at step t
• Alternatively: visited[x,y] ∈ {1..n2}: at which step square (x,y) is visited

Constraints:

• alldifferent(position[1..n2]): each square visited exactly once
• position[t+1] is a valid knight move from position[t] (encode via a transition table or tuple set)
• Optional: position[n2+1] = position[1] for a closed tour

Trade-offs:

• Strength: Global constraint alldifferent provides powerful domain reduction
• Weakness: The transition constraint is complex to encode as a single global constraint; typically requires reified or element constraints
• Scalability: Works well for 8×8; becomes expensive for larger boards due to the number of constraints

Approach 2: SAT Encoding (Boolean Satisfiability)

Decision variables:

• visit[x,y,t] ∈ {0,1} for each square (x,y) and step t ∈ {1..n2}: true iff the knight is at (x,y) at step t

Clauses:

• Exactly one square per step: For each t, at least one visit[*,*,t] is true; at most one via 2-CNF clauses
• Each square visited once: For each (x,y), exactly one t satisfies visit[x,y,t]
• Valid moves: If visit[x,y,t] is true, then visit[x',y',t+1] must be true for some (x',y') reachable by a knight move

Trade-offs:

• Strength: Mature SAT solvers (CaDiCaL, Glucose) with unit propagation and VSIDS heuristics scale to 8×8 and beyond
• Weakness: The encoding is more verbose (~O(n4) variables and clauses); less natural than the CP formulation
• Scalability: Excellent for medium boards (8×8); outperforms naive CP on some instances due to solver maturity

Example CP Model (MiniZinc-inspired pseudocode)

% Knight's Tour (simplified MiniZinc-like pseudocode)
int: n = 8;
array[1..n*n] of var 1..n*n: position;  % square visited at each step
set of int: KNIGHT_MOVES = {(2,1), (1,2), (2,-1), (1,-2), (-2,1), (-1,2), (-2,-1), (-1,-2)};

constraint alldifferent(position);

constraint forall(t in 1..n*n-1)(
  let var int: x1 = (position[t] - 1) div n,
      var int: y1 = (position[t] - 1) mod n,
      var int: x2 = (position[t+1] - 1) div n,
      var int: y2 = (position[t+1] - 1) mod n
  in
    (x2, y2) in {(x1 + dx, y1 + dy) : (dx, dy) in KNIGHT_MOVES, 
                  x1 + dx >= 0, x1 + dx < n, y1 + dy >= 0, y1 + dy < n}
);

solve satisfy;  % or minimize total_distance for Euclidean variant
output [show(position)];

This pseudo-code shows the key idea: sequential position tracking with L-shaped move validation.

---

Key Techniques

1. Warnsdorff's Heuristic (Greedy Ordering)

At each step, move the knight to a square from which it has the fewest onward moves. This greedy heuristic is remarkably effective for finding tours on 8×8 boards and larger, often finding a solution in linear time. However, it can fail on certain starting positions or board sizes—pure heuristic search requires backtracking as fallback.

2. Arc Consistency & Domain Reduction (CP-specific)

Compute the knight's reachability graph (edges between adjacent knight moves) and apply arc consistency algorithms to prune infeasible variable assignments. Constraint propagation tightens domains dynamically, reducing the search tree significantly compared to brute-force backtracking.

3. Symmetry Breaking & Search Space Pruning

• Exploit board symmetry: The 8×8 board has 8-fold rotational/reflective symmetry; enforce that the tour is found in a canonical form (e.g., lexicographically smallest sequence).
• Implied constraints: If no square has exactly one outgoing edge in the current partial assignment, prune immediately.
• Restart strategies: Use rapid restarts (e.g., Luby restart sequence) with different variable-selection heuristics to escape local maxima.

---

Challenge Corner

Question for you:

1. Symmetry-breaking: How would you modify the model to forbid finding symmetric copies of the same tour (e.g., rotations or reflections) without exploring the entire search space for each symmetry class?

2. Parameterization: Can you generalize the knight's tour to a directed acyclic graph where each node represents a square and edges represent valid knight moves, then find a Hamiltonian path? What additional constraints (if any) would you add for a "fairness" metric (e.g., prefer tours that visit the board edges last)?

3. Approximation: Warnsdorff's heuristic fails for small boards like 5×5. Can you design a hybrid algorithm that uses Warnsdorff as a warm-start, then applies constraint propagation to repair violations?

---

References

1. Warnsdorff, H. (1823). Des Rösselsprunges einfachste und allgemeinste Lösung. Schmalkalden. — The original paper on Warnsdorff's heuristic, still elegant after 200 years.

2. van Horn, C. (2007). "A Database of Knight's Tours" — Comprehensive catalog and analysis of known tours; see www.ktn.freeservers.com.

3. Rossi, F., van Beek, P., & Walsh, T. (Eds.). (2006). Handbook of Constraint Programming, Chapter 1 & 3. — Foundational CP reference covering modeling, propagation, and search for problems like Knight's Tour.

4. Sosic, R. & Gu, J. (1994). "Efficient Local Search with Conflict-Driven Heuristics for Constraint Satisfaction." IEEE Trans. on Knowledge and Data Engineering, 6(5), 617–633. — Seminal paper on local search + conflict analysis for CSPs; applicable to dynamic heuristic selection for the Knight's Tour.

---

Next time: We'll explore a scheduling problem with resource constraints. Until then, happy touring! ♞

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · ~10 AIC · ⌖ ~10 AIC · ⊞ 6.7K · ◷

• expires on Nov 4, 2026, 3:31 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #72953.