Haufig kann man bei Suchproblemen Teillösungen betrachten und schrittweise zu einer Problemlösung erweitern. Unterschiedliche Teillösungen bieten oft unterschiedliche Möglichkeiten, sie zu erweitern, so dass der sogenannte Suchraum aller (Teil-)Lösungen als Baumstruktur aufgefasst werden kann. Die Blätter dieses Baumes sind Teillösungen, die nicht mehr erweitert werden können. Diese können erfolgreiche Problemlösungen darstellen oder Fehlschläge. Die inneren Knoten des Baumes entsprechen Teillösungen und deren Nachfolgeknoten entsprechen ihren Erweiterungen.
Beim Lösen eines Sudoku-Puzzles zum Beispiel, entsprechen vollständig ausgefüllte Puzzles den Blättern im Suchbaum und konfliktfrei ausgefüllte Puzzles den Lösungen. Die inneren Knoten sind teilweise ausgefüllte Puzzles, die dadurch erweitert werden können, dass ein bisher freies Feld mit einer Ziffer belegt wird.
Die Verzweigungen im Suchbaum entstehen durch Alternativen bei der Erweiterung von Teillösungen und Backtracking ist eine Technik, diese Alternativen systematisch auszuprobieren. Dazu merkt man sich bei der Auswahl einer Alternative, welche weiteren Alternativen es gibt. Bei einem Fehlschlag nimmt man dann die zuletzt vorgenommene Auswahl zurück und probiert stattdessen die nächste Alternative. Diese Rückkehr zur zuletzt betrachteten Alternative gibt der Programmiertechnik Backtracking ihren Namen.
Ein Algorithmus, der mit Hilfe von Backtracking nach der ersten Lösung eines Problems sucht, kann durch Kombination einer Schleife mit Rekursion formuliert werden. Er gibt zurück, ob eine Teillösung lösbar ist und muss mit einer initialen Teillösung aufgerufen werden.
Teillösung lösbar?
Falls Teillösung vollständig ist,
gib zurück, ob Teillösung gültig ist.
Durchlaufe jede Erweiterung der Teillösung.
Falls Erweiterung lösbar,
gib wahr zurück.
Gib falsch zurück.
Die Schleife, die die Erweiterungen einer Teillösung durchläuft, enthält in ihrem Rumpf einen rekursiven Aufruf des Algorithmus, um zu testen, ob die Erweiterungen lösbar sind. Falls keine der Erweiterungen lösbar ist, ist die Teillösung auch nicht lösbar, in diesem Fall wird also falsch zurück gegeben. Dieser Algorithmus basiert auf Unter-Algorithmen
Unterschiedliche Backtracking-Algorithmen unterscheiden sich im Wesentlichen in diesen drei Aspekten, während das Grundgerüst gleich bleibt.