Historische diepgang: De Knight's Tour is een wiskundige reeks waarin een paard elk veld op een schaakbord precies één keer bezoekt. Het is zowel een strategische uitdaging als een klassiek probleem in de recreatieve wiskunde.
Oorsprong:
Dit probleem is verre van een moderne ontdekking. De vroegst bekende oplossingen dateren uit de 9e eeuw, van meesters uit Bagdad zoals Al-Adli en As-Suli. In de 9e-eeuwse Indiase literatuur demonstreerde de Kasjmirse dichter Rudrata deze wiskundige esthetiek in zijn werk Kavyalankara, waarin hij een gedicht schreef dat de volgorde van de tocht van een ridder volgde.
Westerse literatuur:
In de 13e eeuw zette koning Alfonso X van Castilië complexe manoeuvres gebaseerd op de beweging van de ridder in zijn beroemde Libro de los Juegos (Spelboek). De moderne wiskundige basis van het probleem werd echter in 1759 gelegd door Leonhard Euler, wiens analyse nu wordt erkend als een van de hoekstenen van de grafiektheorie.
Kenmerken:
Gesloten rondleiding: Als het paard eindigt op een veld dat precies één ridderzet verwijderd is van het startveld, kan het onmiddellijk opnieuw beginnen met de ronde.
Open Tour:
Als het paard elk veld bezoekt maar eindigt op een veld vanwaar het niet in één zet het beginpunt kan bereiken.
Dit probleem, dat in 1848 door Max Bezzel werd gesteld en de aandacht trok van genieën als Carl Friedrich Gauss, werd in de jaren 1970 door een van de vaders van de moderne computerwetenschap, Edsger W. Dijkstra, omgezet in een “programmeermanifest”.
In zijn baanbrekende werk, Opmerkingen over gestructureerd programmeren (1972) gebruikte Dijkstra het 8 Queens Probleem om aan te tonen hoe een algoritme systematisch kan worden opgebouwd door middel van een proces dat hij “stapsgewijze verfijning” noemde.”
De kracht van terugkrabbelen:
Volgens Dijkstra is deze aanpak de eerste belangrijke mijlpaal in het verfijnen van het “trial-and-error” proces tot een foutloze logische volgorde die een co
Legende en oorsprong:
Het verhaal gaat dat toen de uitvinder van het schaakspel, Sissa bin Dahir, het spel aan de koning van India presenteerde, de koning hem vroeg welke beloning hij wilde. Sissa deed een ogenschijnlijk bescheiden verzoek: “Ik wil één graankorrel voor het eerste vierkant van het schaakbord, twee voor het tweede, vier voor het derde, en voor elk volgend vierkant, twee keer de hoeveelheid van het vorige.” De koning wees dit verzoek in eerste instantie af omdat hij dacht dat het slechts “een handvol tarwe” was; toen het rekenwerk begon, werd het echter duidelijk dat noch de schatkist noch de hele tarwevoorraad van de wereld voldoende zou zijn om aan deze vraag te voldoen.
Historisch verslag: Ibn Khallikan (1256)
De eerste bekende schriftelijke vermelding van dit beroemde verhaal werd in 1256 gedocumenteerd door de beroemde biograaf en historicus Ibn Khallikan. Ibn Khallikan verwerkte deze gebeurtenis niet alleen als een verhaal, maar ook als bewijs van hoe wiskunde de grenzen van de verbeelding verlegt.
Wiskundige realiteit:
Dit verzoek voor de 64 vakjes op het schaakbord is het zuiverste voorbeeld van geometrische progressie (exponentiële groei). Het bedrag op elk veld wordt berekend met de formule 2n-1 . De vergelijking voor de totale hoeveelheid tarwe is als volgt:
63
∑
i=0
2i = 264 - 1
Het enorme getal dat deze berekening oplevert is:
18,446,744,073,709,551,615
Waarom is het zo belangrijk?
Strategische les: Dit probleem is een oude wijze les die leiders en strategen leert hoe kleine veranderingen (“verdubbeling”) in de loop van de tijd kunnen veranderen in onbeheersbare krachten.
