Wir geben jetzt ein Verfahren an, das den schrittweisen Aufbau der Lösung steuert, die Bedingungen 1 und 2 überprüft und schließlich zu einer korrekten Einfärbung der Karte führt:
Wir nummerieren die Länder durch und bezeichnen sie mit 
.
Erinnerung:
Die Farben probieren wir in der Reihenfolge grün, blau, rot, gelb durch.
Algorithmus
i=1
1. Solange i<=n
2. betrachte Land 
3. Wenn noch nicht alle Farben durchprobiert
dann
färbe das Land mit der nächsten Farbe.
Wenn Bedingungen 1 und 2 erfüllt sind
dann
i=i+1
gehe zu 1.
sonst
gehe zu 3.
sonst
entfärbe Land
i=i-1
gehe zu 2.
Wir wenden dieses Verfahren jetzt auf die Karte mit n=6 Ländern von vorhin an. Im Protokollfeld unten werden die wichtigsten Statusmeldungen und Aktionen aufgelistet.
| grün |
| blau |
| rot |
| gelb |
Das Verfahren findet die Lösung bei Tachostand 012123. Beim erschöpfenden Durchsuchen hätte man dafür 411 Versuche gebraucht.
Hier dagegen haben wir nur 16 Mal die "weiter"-Taste drücken müssen. Dabei wurden 27 verschiedene Tachostände betrachtet.
Das folgende Beispiel mit n=9 Ländern demonstriert an vielen Stellen, dass die Entscheidung, ein Land mit einer bestimmten Farbe zu belegen, zwar die Bedingungen 1 und 2 erfüllt, aber dennoch in eine Sackgasse führt.
| grün |
| blau |
| rot |
| gelb |
Trotzdem sehen wir, wie der Algorithmus aus den Sackgassen herausfindet, indem er seine Spur zurückverfolgt. Daher auch der Name Backtracking = Rückverfolgung.
Die Lösung wird beim Tachostand 012312312 gefunden. Beim erschöpfenden Durchsuchen wären also 28086 Versuche notwendig gewesen.
( 
)
