---

Backtracking Algorithms

A backtracking algorithm solves a Sudoku by trying to place a digit into a cell, then working out the consequences and placing other digits until the program either hits a dead end, or finds a solution. If a dead end is reached, the algorithm then removes the placed digits and tries the alternatives. This process continues until all alternatives have been tried.

Another name for backtracking is depth-first search.

Popular backtracking algorithms for Sudoku are Dancing Links, also known by its acronym DLX, and Ariadne's Thread.

This page was last modified 07:39, 16 February 2008.  

---