Chronological backtracking in Python
Undoes the most recent assignment on failure, the baseline against which smarter backtracking is compared.
- File
chronological_backtracking.py, 76 lines- Level
- I0 not checked yet
- Toolchain
- Python 3.14, pytest 9
- Test framework
- pytest
- Run the tests
python3 -m pytest
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/chronological-backtracking/. The authors are listed in prov/5ZHQ6D.jsonl.
from collections.abc import Callable, Hashable, Iterator, Sequence
from typing import TypeVar
V = TypeVar("V", bound=Hashable)
Constraints = dict[tuple[int, int], Callable[[V, V], bool]]
def _consistent(a: list[V], i: int, v: V, constraints: Constraints, stats: dict[str, int]) -> bool:
for j in range(i):
pred = constraints.get((j, i))
if pred is not None:
stats["checks"] += 1
if not pred(a[j], v):
return False
return True
def solutions(
domains: Sequence[Sequence[V]],
constraints: Constraints,
stats: dict[str, int] | None = None,
) -> Iterator[list[V]]:
"""Yield every solution of a binary CSP in lexicographic order.
Variables are 0 .. m-1 and are assigned in this order. domains[i] lists
the values of variable i in the order to try them. constraints[(j, i)]
with j < i is a predicate on (value of j, value of i). The search is
chronological backtracking, run with an explicit stack. If stats is
given, it receives the counts "assignments" and "checks". Time:
O(m d^m) checks in the worst case; extra space O(m).
"""
for j, i in constraints:
if not 0 <= j < i < len(domains):
raise ValueError("constraint keys must be pairs (j, i) with j < i")
st = stats if stats is not None else {}
st.setdefault("assignments", 0)
st.setdefault("checks", 0)
m = len(domains)
a: list[V] = []
# positions[i] is the index of the next value of D_i to try
positions = [0] * (m + 1)
while True:
i = len(a)
if i == m: # @line L1
yield list(a)
if m == 0:
return
a.pop() # @line L7
continue
if positions[i] >= len(domains[i]):
positions[i] = 0
if i == 0:
return # @line L8
a.pop() # @line L8
continue
v = domains[i][positions[i]] # @line L2
positions[i] += 1
if _consistent(a, i, v, constraints, st): # @line L3
a.append(v) # @line L4
st["assignments"] += 1
positions[i + 1] = 0 # @line L5
def chronological_backtracking(
domains: Sequence[Sequence[V]],
constraints: Constraints,
stats: dict[str, int] | None = None,
) -> list[V] | None:
"""Return the lexicographically first solution, or None if there is none (lines L1 to L8, line L6 stops at the first)."""
for sol in solutions(domains, constraints, stats):
return sol # @line L6
return None
test_chronological_backtracking.py 67 lines
# SPDX-License-Identifier: MIT
# Part of https://algorithm.tamnd.com/chronological-backtracking/. The authors are listed in prov/5ZHQ6D.jsonl.
import itertools
import random
from chronological_backtracking import chronological_backtracking, solutions
def brute(domains, constraints):
out = []
for t in itertools.product(*domains):
if all(p(t[j], t[i]) for (j, i), p in constraints.items()):
out.append(list(t))
return out
def test_example_of_the_page() -> None:
domains = [[1, 2], [1, 2, 3], [1, 2, 3], [1, 2]]
constraints = {(1, 2): lambda a, b: a != b, (0, 3): lambda a, b: b < a}
stats: dict[str, int] = {}
assert chronological_backtracking(domains, constraints, stats) == [2, 1, 2, 1]
assert stats == {"assignments": 14, "checks": 24}
def test_edges() -> None:
assert chronological_backtracking([], {}) == []
assert list(solutions([], {})) == [[]]
assert chronological_backtracking([[]], {}) is None
assert chronological_backtracking([[1], [1]], {(0, 1): lambda a, b: a != b}) is None
assert list(solutions([[0, 1], [0, 1]], {})) == [[0, 0], [0, 1], [1, 0], [1, 1]]
def test_four_queens_as_csp() -> None:
n = 4
cons = {}
for j in range(n):
for i in range(j + 1, n):
cons[(j, i)] = (lambda d: lambda a, b: a != b and abs(a - b) != d)(i - j)
assert list(solutions([range(1, n + 1)] * n, cons)) == [[2, 4, 1, 3], [3, 1, 4, 2]]
def test_thrashing_family() -> None:
for d in range(2, 5):
for m in range(3, 6):
doms = [[1, 2]] + [list(range(1, d + 1))] * (m - 2) + [[1, 2]]
stats: dict[str, int] = {}
sol = chronological_backtracking(doms, {(0, m - 1): lambda a, b: b < a}, stats)
assert sol == [2] + [1] * (m - 2) + [1]
# with X_1 = 1 the search assigns every prefix of X_2 .. X_{m-1}
assert stats["assignments"] >= d ** (m - 2)
def test_random_against_brute_force() -> None:
rng = random.Random(77)
for _ in range(800):
m = rng.randrange(0, 5)
domains = [rng.sample(range(4), rng.randrange(0, 4)) for _ in range(m)]
constraints = {}
for j in range(m):
for i in range(j + 1, m):
if rng.random() < 0.5:
allowed = {(a, b) for a in range(4) for b in range(4) if rng.random() < 0.6}
constraints[(j, i)] = (lambda s: lambda a, b: (a, b) in s)(allowed)
want = brute(domains, constraints)
assert list(solutions(domains, constraints)) == want
assert chronological_backtracking(domains, constraints) == (want[0] if want else None)
What the next level needs
- the tests did not run in this build