Acht dames, springerronde van Euler, verminkt schaakbord: de grote wiskundige puzzels van het schaakbord

Deze puzzels spelen zich af met de stukken of het raster van het schaakbord, maar hebben niets met een partij te maken: het zijn echte wiskundeproblemen, toegankelijk vanaf de middelbare school, en sommige hebben grote namen van het vak beziggehouden. Ze zijn ideaal voor een wiskundeclub, een spreekbeurt of een spreekopdracht.

Samenvattende tabel

Het achtdamesprobleem

Het achtdamesprobleem

Plaats acht dames op een bord van 8 × 8 zo dat er geen enkele een andere kan slaan: nooit twee dames op dezelfde rij, dezelfde kolom of dezelfde diagonaal.

Het probleem werd in 1848 gepubliceerd door Max Bezzel, een schaakprobleemcomponist. Franz Nauck publiceerde in 1850 de eerste oplossingen en veralgemeende het naar n dames op een bord van n × n velden. Carl Friedrich Gauss behoort tot de wiskundigen die zich ermee bezighielden.

Doel van het probleem: één opstelling vinden, en dan alle. Er bestaan er 92. Veel ervan volgen uit elkaar door draaiing of spiegeling van het bord; als je ze groepeert, blijven er 12 fundamentele oplossingen over. Hier is er één, met de dames op d8, g7, c6, h5, b4, e3, a2 en f1:

Je controleert gemakkelijk dat er één dame per rij en per kolom staat. Voor de diagonalen volstaat het na te gaan dat voor elke twee dames het verschil in kolommen nooit gelijk is aan het verschil in rijen.

Hoe los je het op?

De klassieke methode is backtracking (in het Engels backtracking): je plaatst een dame in de eerste kolom, dan een dame in de tweede kolom op een niet-aangevallen veld, enzovoort; wanneer geen enkel veld meer mogelijk is, ga je terug en verplaats je de vorige dame. Het is een zeer gewaardeerde oefening in de informaticales op de middelbare school. De versie met n dames heeft oplossingen voor elke n behalve 2 en 3: bijvoorbeeld 2 oplossingen voor n = 4, 10 voor n = 5, 4 voor n = 6, 40 voor n = 7.

Het springerprobleem van Euler

Springerprobleem

Zoek een reeks paardensprongen die precies één keer over elk van de 64 velden gaat. De route heet gesloten als het laatste veld één paardensprong van het eerste verwijderd is, zodat je de lus opnieuw kunt doorlopen.

Het probleem is zeer oud: een rondgang van het paard over een halfbord staat al in een Sanskriet verhandeling over poëtica uit de 9e eeuw, de Kavyalankara van Rudrata. Leonhard Euler wijdde er een verhandeling aan, « Solution d'une question curieuse qui ne paroit soumise à aucune analyse » (Oplossing van een merkwaardige vraag die aan geen enkele analyse onderworpen lijkt), voorgelegd in 1759 en gepubliceerd in 1766 in de verhandelingen van de Academie van Wetenschappen in Berlijn. In 1823 stelde H. C. von Warnsdorff een eenvoudige regel voor om een route te vinden: ga altijd naar het veld vanwaaruit het paard het minst aantal vervolgzetten heeft.

Op het gewone schaakbord bestaan er ontzettend veel gesloten routes: 26 534 728 821 064 als je de richting meetelt, of de helft, 13 267 364 410 532, als je een route en haar omgekeerde als hetzelfde beschouwt.

Een route om na te gaan op een bord van 5 × 5

Om te oefenen kun je met kleiner beginnen. Hier is een open route die de 25 velden van een bord van 5 × 5 bezoekt: volg de getallen van 1 tot 25, elk getal ligt één paardensprong van het vorige.

Deze route werd met de regel van Warnsdorff verkregen, en elke sprong is gecontroleerd. Uitdaging: vind een andere die in het midden begint.

Het springerprobleem op het grote examen

Het onderwerp leent zich goed voor het mondelinge examen van het baccalauréat in de specialiteit wiskunde of NSI: modellering met een graaf (de velden zijn de toppen, de mogelijke sprongen de takken), zoeken naar een pad dat alle toppen passeert, backtrackingalgoritme, regel van Warnsdorff en diens efficiëntie. Je kunt ook uitleggen waarom er op een bord van 5 × 5 geen gesloten route bestaat: het paard verandert bij elke sprong van kleur, dus een lus heeft noodzakelijk een even aantal velden, maar 25 is oneven.

Het verminkte schaakbord

De filosoof Max Black stelde het probleem in 1946 in zijn boek Critical Thinking. Je haalt twee tegenover elkaar liggende hoeken van een schaakbord weg (bijvoorbeeld a1 en h8). Kun je de 62 overblijvende velden bedekken met 31 dominostenen, waarbij elke dominosteen twee aangrenzende velden bedekt?

Antwoord: nee. Elke dominosteen bedekt noodzakelijk een witte en een zwarte velden. 31 dominostenen zouden dus 31 witte en 31 zwarte velden bedekken. De twee tegenover elkaar liggende hoeken zijn echter van dezelfde kleur: er blijven 32 velden van de ene kleur en 30 van de andere over. De betegeling is onmogelijk, zonder dat je één opstelling hoeft te proberen. Martin Gardner maakte dit probleem in 1957 in zijn rubriek in Scientific American bekend bij het grote publiek.

En als je één wit en één zwart veld weghaalt? Ralph Gomory bewees (resultaat gepubliceerd in 1973) dat de betegeling dan altijd mogelijk is, ongeacht welke twee velden je weghaalt.

Polyomino's en pentomino's

Een polyomino is een vorm die uit identieke vierkanten langs hun zijden is samengesteld; de domino heeft er twee, de pentomino vijf. De wiskundige Solomon Golomb introduceerde en bestudeerde deze vormen vanaf 1953. Er bestaan 12 verschillende pentomino's (als je aanneemt dat een stuk dat omgedraaid of gedraaid wordt dezelfde blijft), die samen 60 velden bedekken.

Een schaakbord heeft 64 velden, dus 60 + 4: je kunt dus proberen de 12 pentomino's op het bord te leggen en in het midden een vierkant van 2 × 2 vrij te laten. In 1958 liet Dana Scott dit probleem door een computer oplossen, een van de eerste toepassingen van de backtrackingmethode: er bestaan 65 oplossingen. Een andere beroemde uitdaging: de rechthoek van 6 × 10 kan op 2 339 verschillende manieren met de 12 pentomino's worden betegeld.

Hoeveel vierkanten op een schaakbord?

Het antwoord « 64 » is fout, of liever onvolledig: het telt alleen de kleine vierkanten. Je moet ook de vierkanten van 2 × 2, 3 × 3… tot het grote vierkant van 8 × 8 tellen.

Het totaal is de som van de kwadraten van de gehele getallen van 1 tot 8: 1 + 4 + 9 + … + 64 = 204. Om verder te gaan: een schaakbord bevat 1 296 rechthoeken (inclusief vierkanten), want een rechthoek wordt bepaald door het kiezen van 2 rijen uit de 9 rijen van het raster en 2 kolommen uit 9, dus 36 × 36.

Verder lezen

Deze problemen maken gebruik van precieze begrippen: pariteit, kleuring, tellen, grafen. We werken ze uit, met oefeningen voor de basisschool en de middelbare school, op de pagina de wiskundige begrippen op het schaakbord. Voor andere zeer grote getallen, zie het schaakbord van Sissa. En voor wie van raadsels houdt, biedt de blog van Le Palais des Échecs de logicaraadsels van Le Palais des Échecs, die regelmatig worden vernieuwd.