Over de paardensprong | Regel van Warnsdorff, open en gesloten rondgangen

Een oude puzzel

In de Kavyalankara, in de 9e eeuw geschreven door de Indiase dichter Rudrata, staat een vers zo op een half schaakbord dat het langs de route van een paard te lezen is. Leonhard Euler schreef in 1759 de eerste wiskundige studie van de rondgang van het paard, met manieren om rondgangen te maken en ze tot gesloten rondgangen om te vormen.

Een pad door een graaf

Zie elk veld als een punt en elke paardensprong als een lijn tussen twee punten. Een rondgang van het paard is dan een pad dat elk punt precies één keer bezoekt, wat wiskundigen een hamiltonpad noemen; een gesloten rondgang is een hamiltoncykel. In de meeste netwerken is zo’n pad heel moeilijk te vinden. Het netwerk van het paard is gul: het heeft zoveel rondgangen dat een goede regel er snel een vindt.

De regel van Warnsdorff

H. C. von Warnsdorff beschreef zijn regel in 1823: spring altijd naar het veld dat de minste vervolgzetten overlaat. Velden langs de rand hebben weinig buren, dus de regel bezoekt ze vroeg in plaats van ze geïsoleerd achter te laten. Als twee velden gelijk staan, moet er gekozen worden, en een ongelukkige keuze kan het paard toch nog laten vastlopen. In de app markeren de gouden getallen de velden die de regel zou kiezen.

Zoeken met backtracking

Oplossen volgt de volgorde van Warnsdorff, maar vertrouwt er niet blind op. Het zoekt diepte-eerst, en zodra een onbezocht veld niet meer bereikbaar is, laat het die tak los en probeert het de volgende zet. Op borden tot 10×10 vindt het meestal meteen een rondgang. Als je eigen route het paard heeft ingesloten, gaat het eerst een paar zetten terug.

Kleuren en gesloten rondgangen

Elke paardensprong verandert de kleur van het veld. Op een bord met oneven afmetingen zoals 5×5 is er één veld meer in de hoekkleur dan in de andere kleur, dus een rondgang moet beginnen en eindigen op de hoekkleur. Een gesloten rondgang is daar onmogelijk, omdat een lus die de kleuren afwisselt van elke kleur evenveel velden heeft. Op borden met even afmetingen bestaan gesloten rondgangen vanaf 6×6.

Probeer het in PictorX

Open Paardensprong en klik op een veld om te beginnen. De opgelichte velden zijn de toegestane sprongen, het gouden getal is de keuze van Warnsdorff, en het bord houdt de volgorde van je zetten bij. Grootte stelt het bord in van 5×5 tot 10×10, ‘Gesloten rondgang’ vraagt Oplossen om een lus, en Ongedaan maken neemt elke zet terug. Sla de voltooide route op als PNG.

Veelgestelde vragen

Wie bestudeerde de rondgang van het paard als eerste?

Rondgangen waren al lang bekend voordat iemand ze wiskundig bestudeerde. Leonhard Euler schreef in 1759 de eerste wiskundige behandeling, en Warnsdorff gaf zijn regel in 1823.

Is er op elk bord een rondgang?

Vierkante borden vanaf 5×5 hebben open rondgangen, en die met even afmetingen vanaf 6×6 hebben ook gesloten rondgangen. Borden van 2×2, 3×3 en 4×4 hebben helemaal geen rondgang.

Hoeveel rondgangen heeft een schaakbord?

Er zijn 26.534.728.821.064 gesloten rondgangen als een rondgang en dezelfde rondgang achterstevoren apart worden geteld. Het aantal open rondgangen is ongeveer 19,6 biljard.

Uploadt PictorX iets?

Nee. Het bord wordt op een canvas in je browser getekend. Opslaan downloadt een PNG, en Bewerken opent dat beeld in de PictorX-editor.