Backtracking

Backtracking is een fascinerende programmeertechniek welke kan worden gebruikt voor optimalisaties, oplossen van puzzels en het programeren 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) af. Zo'n tak kan b.v. betekenen: een stukje van een puzzel inpassen, of een zet of tegenzet overwegen in een schaakpartij. Als hij in de top van de een tak zit loopt hij het spoor weer terug in de boom tot het punt waarop hij gebleven was, waarna een volgende tak beklommen wordt. Soms wordt de volledige boom doorzocht, als dit te lang zou duren beperken we ons tot een bepaalde hoogte.

Er zijn verschillende stijlen:
a> Recursie - hierin schrijf je één routine die zichzelf aanroept. Je programma kan er soms onwaarschijnlijk simpel uit zien, en toch werkt het! Sommige primitievere programmeertalen ondersteunen dit helaas vrij slecht. Moderne talen zoals C, Delphi en Visual Basic hebben er geen enkel probleem mee.
b> Één grote 'while'-loop, dit is in vrijwel elke taal te realiseren.
c> Als je een backtrack-programmeertaal kiest zoals b.v Prolog dan de kern al voor je gedaan. Deze recursieve talen gaan meestal kwistiger met processor stack en geheugen om. Dus als je opgave te diep de boom in klimt of lang rekent is dit geen serieuze optie.

Wat kun je hier zoal mee?
De toepassingen vallen grofweg in 3 categoriën uiteen:

1) Optimalisatie-problemen uit de praktijk
- Travelling salesman / buslijn-algoritme
- Maak de best passende indeling:
--- Dating (een lijst kandidaten met een lijst tegen-kandidaten matchen)
--- Toernooi/competitie indeling (kanditaten en tegen-kandidaten uit dezelfde lijst)
--- Het incomplete block design uit het marktonderzoek (product testing)
--- Vraag en Aanbod optimaliseren
- een directory met subdirectories doorlopen en onderzoeken 2)Backtracking is succesvol toegepast in de volgende Denkspelen
- Schaken Van de oude 'Chess Challenger' kan beetje speler prima winnen, maar heb je al eens tegen 'Deep Blue' of 'Deep Fritz' gespeeld? De mens is aan de verliezende hand.
- dammen
- 4 op een rij, hiervan bestaan al onverslaanbare programma's!
- Othello / reversi
- Go, deze programma's zijn nog niet zo sterk. Een gevorderd speler verslaat de sterkste programma's op zijn pinken. Probleem bij Go is dat het erg lastig is om in in een stelling te schatten hoe het er voor staat.

Hier voelt de mens (met bezorgdheid over zijn eigen positie) dat de computer steeds meer een 'denkende machine' begint te worden. Je maakt alleen kans als je de zetten-boom dieper dan de computer kunt zien. Als de computer in staat wordt de volledige boom te doorzoeken dan speelt hij perfect!

Links:
het microskoop-spel uit The 7'st guest
3) Puzzels (en programmeerwedstrijden)
- Meetkundige legpuzzels
- Schuifpuzzels (de piano-verhuizer, loper-probleem, rubiks cube)
- Solitaire oplossen (en als dit lukt: in zo min mogelijk zetten)
- Variant op cijfers: rekenen met 5 maal het cijfer 3 : je hebt max 5 drieën tot je beschikking en een onbegrensd aantal bewerkingen: + - / * daarnaast ook machtverheffen en het faculteit-teken. het is de bedoeling om met deze middelen alle getallen van 1 t/m 100 te maken, b.v.
. ... 1 = 3 / 3
. ... 2 = 3! / 3 etc. er zitten een paar echt lastige tussen!
- Zowel een doolhof door de computer laten ontwerpen als hem er zelf doorheen laten dwalen!
- logikwis
- sudoku
- Een magisch vierkant van domino-stenen
- Zie ook het boek 'Spelen met Puzzels' uit 1978 van Pieter van Delft en Jack Botermans, voor een haast onuitputtelijke bron van breinbrekers. Het is nog regelmatig te koop bij 'de Slegte'.
- 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.

Links:
cijfers (van cijfers en letters) en andere
Het n koninginnenprobleem, magische vierkanten en andere