Backtracking is een implementatie van kunstmatige intelligentie.
Backtracking is een fascinerende programmeertechniek welke kan worden gebruikt voor optimalisaties, oplossen van puzzels en het programmeren van een computer-tegenstander bij denkspelen.

Er zijn boeken over volgeschreven, maar in een notedop komt het hier op neer:

De computer doorloopt 'een boom van mogelijkheden' (met takken en zijtakken). Zo'n tak kan b.v. betekenen: een stukje van een puzzel inpassen, of een zet of tegenzet overwegen in een schaakpartij. Als hij de top van een tak heeft verwerkt, volgt hij het spoor weer terug in de boom tot het punt waarop hij gebleven was, waarna een volgende tak beklommen wordt. Een ander aspect is dat een tak soms voortijdig wordt afgewezen, als duidelijk is dat die niet succesvol zal zijn. Hierdoor kan je het proces sterk optimaliseren.

Praktijkvoorbeeld met het 8-koninginnenprobleem

1. Algemene toepassingen
• Een directory en recursief subdirectories doorlopen
• Sommige sorteeralgoritmes gebruiken recursief backtracking


Handelsreizigers-algoritme: gegeven een set bestemmingen/haltes, bereken de kortste of snelste route die al deze bestemmingen langsgaat.


• OV reisplanner en de NS-routeplanner.


• Dijkstra's algoritme Als je weet dat bepaalde haltes zonder tussen-halte met elkaar verbonden zijn, dan kan je optimaliseren.


• Auto-navigatie software (TomTom) en in Google Maps


• Internet-navigatie, hoe een HTTP of SMTP-bericht met (ongeveer) de snelste route zijn doel bereikt


• Krantenwijk in Manhatten, programmeerwedstrijd georganiseerd in 1996 door de Telegraaf


• Zie ook de Local search-methode: artikel en wiki



Schema's optimaliseren:
• landelijk OV-rooster maken voor treinstellen, treinpersoneel, baanvakken en perrons
• Optimaal lesrooster maken voor leerlingen, leraren en leslokalen
• Vraag en Aanbod optimaliseren b.v. met Lineair programmeren in Operationele Analyse.
• Het incomplete block design b.v. bij marktonderzoek, product testing:
  Stel je wilt 8 smaken laten beoordelen, maar om praktische redenen kan je maar 4 smaken per respondent laten proeven.
  Van 4 uit 8 kan je 70 combinaties maken (8 over 4 = (8*7*6*5)/(4*3*2*1) = 70) geeft 70 testgroepen, maar er is in dit geval ook een manier om met een set van 14 groepen een Balanced Incomplete Block Design te maken.
• Toernooi/competitie indeling (kandidaten en tegen-kandidaten uit dezelfde lijst)
• Dating: een lijst kandidaten met een lijst tegen-kandidaten matchen (in theorie)


2. Denkspelen met het minimax algoritme en Alpha�beta snoeien.
• Schaken. Van de oude 'Chess Challenger' kon beetje speler prima winnen, maar heb je al eens tegen 'Deep Blue' of 'Deep Fritz' gespeeld? Alleen de sterkste spelers maken nog kans tegen software uit de winkel.
• Dammen, ook bij dammen hebben alleen de spelers op wereldniveau nog kans.
• 4 op een rij, is inmiddels door de computer opgelost! Degene die begint kan altijd winnen.
• Bij Othello (reversi) maken mensen helaas al geen kans meer.
• Go (aziatisch bordspel), deze programma's beginnen aardig sterk te worden.
  Laatste nieuws: AlphaGo wint zelfs van de sterkste speler van Europa.
  In maart 2016 is er een match gespeeld tussen de huidige wereldkampioen Lee Sedol en het computerprogramma AlphaGo, AlphaGo heeft gewonnen met 4 - 1. Dit veroorzaakte nogal een schok in de go-wereld. Software van die sterkte is nog niet te koop.

Computers presteren inmiddels beter dan mensen bij de meeste denkspelen.
Mensen hebben ook een soort alpha-beta algoritme, vooral gebaseerd op intuïtie.
Je maakt misschien kans als je varianten ziet die door het computer Alpha�beta algoritme worden afgekapt, in schaaktermen: verzin een verrassend dame-offer!


3. Puzzels (en programmeerwedstrijden)
• Het 8-koninginnenprobleem (een case-study)
• Meetkundige legpuzzels, pentomino's en dergelijke. Ik heb hier enkele programma's in Windows die je kan downloaden.
• Schuifpuzzels (Rush Hour, de piano-verhuizer, loper-probleem, rubiks cube)
• Pin-Solitaire oplossen (en als dit lukt: in zo min mogelijk zetten)
• Zowel een doolhof door de computer laten ontwerpen als hem door de computer laten oplossen! Algoritmes
• Cijfers uit TV-programma 'Cijfers en Letters' oplossen
• Logikwis puzzels Met een set van aanwijzingen moet je de juiste combinaties zien te vinden.
  Extra uitdaging voor een generiek programma: hoe vertaal je de tekstuele aanwijzingen in bruikbare code voor de computer?
  Dat lukt alleen als de aanwijzingen binnen een beperkte set van model-aanwijzingen blijven.
• sudoku (zowel ontwerpen als oplossen), inleiding...
• Een magisch vierkant van domino-stenen
• Het vierkleurenprobleem. Het is bewezen dat je de landen in een landkaart met vier kleuren kunt inkleuren zonder dat er twee aangrenzende landen van dezelfde kleur zijn. Je kan het voor een gegeven kaart ook programmeren.
• Zie ook het boek 'Spelen met Puzzels' uit 1978 van Pieter van Delft en Jack Botermans, voor een haast onuitputtelijke bron van breinbrekers waarvan er veel geschikt zijn om te programmeren. Het is nog regelmatig te koop bij tweedehandswinkels.
• de computerspellen The 7th guest en The 11th hour bevatten een leuk aantal puzzels die met de computer kunnen worden opgelost, of waarin de computer een sluwe tegenstander kan zijn.

• Recursie - hierin schrijf je ��n routine die zichzelf aanroept, zodanig dat het de oefening herhaalt met een kleiner gedeelte van de opgave. Je programma kan er soms onwaarschijnlijk simpel uit zien, en toch werkt het!
  Oude of primitieve programmeertalen ondersteunden dit vrij slecht, maar de moderne talen zoals Visual Basic, C, Delphi en Java hebben er geen enkel probleem mee.
• ��n grote 'while'-loop, dit is in vrijwel elke taal te realiseren.
• Als je een backtrack-programmeertaal kiest zoals b.v Prolog dan de kern al voor je gedaan. Deze recursieve talen gaan meestal wel iets kwistiger met geheugen om.
  Dus als je opgave te groot is kunnen er geheugenproblemen optreden.