Backtracking is goed te illustreren met het 8-koninginnen probleem. De opgave luidt als volgt:

• Je hebt een schaakbord (van 8 x 8 vakjes), met 8 koninginnen (dames) uit het schaakspel, je kan ook pionnen of damschijven nemen.
• Plaats elk van de 8 stukken in een vakje op het bord, zodanig dat er nergens twee dames zijn die elkaar volgens de schaakregels aankijken. Ze mogen dus horizontaal, vertikaal en diagonaal niet op dezelfde lijn staan.
• De grootte (8) maakt feitelijk niet uit voor de puzzel. Je kan eventueel eenvoudiger beginnen, op b.v. een bord van 5 x 5 vakjes met 5 dames.
• De puzzel is: vind een oplossing (bij voorkeur ALLE oplossingen) om de dames op het bord te plaatsen.

Om uit te leggen hoe backtracking werkt bekijken we eerst twee voor de hand liggende alternatieven.

Brute kracht:

We genereren alle mogelijke standen met 8 koninginnen en bepalen van elke stand of dit een oplossing is. Daar zitten ook veel 'domme' standen bij met b.v. alle koninginnen op een kluitje:

De computer krijgt hier aardig wat werk aan...
Er zijn (64 over 8) standen = 64!/((64-8)!*8!) = 4.426.165.368 standen. Per stand moet er een aantal (maximaal 8*7/2= 28) koninginnenparen worden beoordeeld of deze elkaar niet aankijken. Dit gaat zeker een aardig tijdje duren.

Optimalisatie (maar nog steeds Brute Kracht):

De vorige methode kan beter, we weten immers dat er op elke kolom maar 1 koningin kan staan. We zetten nu een koningin op elke kolom en genereren alle mogelijke combinaties van standen waar 1 koningin in elke kolom staat, b.v.:

Nu zijn er 8⁸ standen = 16.777.216 standen om te evalueren. Dit is aanzienlijk beter dan de vorige, ca. 250x zo snel! Maar nog steeds een aardig klusje voor de computer.

Hoe werkt het met backtracking?

Demo: klik op run! om de puzzel aan het werk te zien

Het grote verschil is dat we elke koningin bij het neerzetten al gaan beoordelen. We gaan het stap voor stap doen. Om het verhaal niet te lang te maken nemen we een 4 x 4 bordje waar 4 koninginnen op geplaatst moeten worden. We beginnen met een leeg bord.
We beginnen bij de eerste kolom, we plaatsen een koningin op de eerste rij.

Daarna gaan we naar de volgende kolom om een koningin te plaatsen.

Dan gaan we weer een kolom verder voor de volgende koningin.

We gaan weer terug naar kolom 2 en zetten de dame een stapje verder naar rij 4.

Dan gaan we weer verder naar kolom 3. Op de eerste rij kan niet

Voor het eerst bereiken we de vierde en laatste kolom!

Dat is balen! Helaas terug naar kolom 3...

Terug naar kolom 2...

Dus nu zelfs helemaal terug naar kolom 1 en de dame een rij verder proberen...

Verder naar kolom 2, de dame kan alleen op de laatste rij.

Door naar kolom 3, de dame kan direct op de eerste rij.

Nu naar kolom 4 ... en daar komt de eerste oplossing!

Hierna is het nog niet af, we wilden eigenlijk ALLE oplossingen weten, maar voor de uitleg van het algoritme laten we het hierbij. Er zal blijken dat er een tweede oplossing is, n.l. het spiegelbeeld van deze.
Uiteindelijk (na 16 zetten) zal het programma alle rijen van kolom 1 behandeld hebben, vervolgens wil het algoritme (als het consequent is) terug naar kolom 0 en moet dan kunnen concluderen dat het klaar is.
Nog even ter vergelijking:

• Brute kracht: (16 over 4) = 16 x 15 x 14 x 13 = 43.680 standen, x 4 dames = 174.720 zetten.
• Brute kracht met optimalisatie: 4⁴ standen = 256 standen, x 4 dames = 1024 zetten.
• Backtracking: 40 zetten.

Het moge duidelijk zijn wat het snelste werkt.

Algoritme van het 'N' koninginnenprobleem (met de 'while' benadering)