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

Wanneer kan je backtracking gebruiken?

De toepassingen kunnen gegroepeerd worden:
  1. Algemene toepassingen

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

  3. travel solution
  4. Schema's optimaliseren:

  5. Denkspelen met het minimax algoritme en Alpha–beta snoeien.

  6. 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!

  7. Puzzels (en programmeerwedstrijden)
Er zijn verschillende stijlen (elk met zijn eigen voordeel):

Meer links:
- Het n koninginnenprobleem, magische vierkanten en andere
- Genetisch algoritme