Das Backtracking beschreibt ein Verfahren, welches genutzt wird um effizient eine Lösung zu einem Problem zu finden.

Zunächst merkt man sich jeden einzelnen Schritt und arbeitet so lange weiter, bis keine Lösung möglich ist. Nun geht man zum vorherigen Schritt und überprüft, ob dort ein Fehler enthalten ist. So geht man so lange die Schritte rückwärts der Entstehung entlang, bis man einen ohne Fehler findet und erarbeitet sich dort neue Lösungsvorschläge. Dies kann man so lange wiederholen, bis man die Lösung erarbeitet hat.

Die Implementierung erfolgt meist durch Rekursion.