Hoeveel koninginnen passen er op een schaakdonut?

Wiskunde Hoeveel manieren zijn er om koninginnen op een gekromd schaakbord te plaatsen, zodat geen enkele koningin een andere kan slaan? Deze honderd jaar oude vraag is nu beantwoord.

Foto Getty images

Neem een schaakbord (8×8 velden) en acht koninginnen. Kun je die stukken neerzetten zónder dat er twee zijn die elkaar kunnen slaan? Twee koninginnen kunnen elkaar slaan als ze in dezelfde rij, kolom of diagonaal staan. Ja, is het antwoord.

Stel je nu voor dat dat schaakbord van goed buigzaam rubber is gemaakt. Maak van het schaakbord een koker, door twee overstaande zijden tegen elkaar te plakken. Plak vervolgens de twee cirkelvormige uiteinden ook aan elkaar zodat er een donutvorm ontstaat.

Dan blijkt dat van de oplossing op het platte schaakbord niks overblijft. Op de donut komen koninginnen op één diagonaal te liggen – dat mag dus niet.

Formule als hoogtepunt

Al sinds de negentiende eeuw houden wiskundigen zich bezig met de wiskunde op een schaakbord, maar echte vooruitgang werd pas de laatste jaren geboekt. Op 16 september postten Candida Bowtell en Peter Keevash, twee wiskundigen van de universiteit van Oxford, een lijvig document – 161 pagina’s – op de preprintserver arXiv. Daarin bewijzen ze een aantal resultaten, met als hoogtepunt een formule voor het aantal oplossingen op grote donutvormige schaakborden.

Het uitgangspunt is steeds een vierkant schaakbord, niet per se van het formaat 8×8, maar meer algemeen n×n, dat wordt hervormd tot een donut. De centrale vraag: hoeveel manieren zijn er om n koninginnen te plaatsen, zodanig dat geen enkele koningin een andere kan slaan? Het kan dus gaan om 17 koninginnen op een donutvormig bord van 17×17, om 2021 koninginnen op een bord van 2021×2021, of om welk aantal ook.

Exacte antwoorden zijn er alleen voor enkele kleine, specifieke waarden van n. Zo zijn er 4.524 oplossingen als n=13, en 1.957.725.000 als n=25. Wiskundigen zoeken naar patronen en hopen zo een algemene formule te vinden voor borden van willekeurige grootte.

In tegenstelling tot een plat schaakbord heeft een donutbord een grote mate van symmetrie. Terwijl het er op een gewoon bord toe doet of een koningin in het midden staat of ergens aan de rand, is op een donutvormig bord elk veld gelijkwaardig. Immers, op een plat bord verschillen de lengtes van de diagonalen, maar op een donut zijn alle rijen, kolommen en diagonalen precies even lang. Die symmetrie maakt het donutbord tot een interessant wiskundig object.

De Hongaarse wiskundige George Pólya, auteur van het beroemde en in vele talen verschenen boek How to solve it, bewees in 1918 wanneer het mogelijk is n koninginnen op een donutbord van formaat n×n te plaatsen: dat lukt alléén als n níét deelbaar is door 2 of 3. Op een plat 8×8-bord zijn er maar liefst 92 oplossingen, maar uit Pólya’s stelling volgt dus dat geen daarvan standhoudt als het bord de gedaante van een donut aanneemt: 8 is immers deelbaar door 2.

Pólya bewees dat er oplossingen bestaan als n geen veelvoud is van 2 of 3, maar de vraag hoevéél kon hij niet beantwoorden. Hoeveel oplossingen zijn er als n duizend en één is? Of twee miljoen en vijf? Valt er iets zinnigs over te zeggen met één enkele formule? Deze vraag is nu door Bowtell en Keevash beantwoord. Althans, ze geven een goede benaderingsformule: voor grote waarden van n, niet deelbaar door 2 of 3, zijn er ongeveer (0,0498n)n oplossingen.

Ook al geeft de formule geen exact antwoord, duidelijk wordt wel hoe extreem snel het aantal mogelijke configuraties groeit naarmate n groter wordt. Per mail legt Bowtell uit: „De groei is ‘super-exponentieel’, omdat de variabele n zowel in de basis als in de exponent voorkomt. Op een eindig aantal gevallen na geeft onze formule voor elke waarde van n een zeer accurate benadering voor het aantal oplossingen.”

Hardlopen in de buitenlucht

Bowtell begon bijna vier jaar geleden te werken aan het koninginnenprobleem – het was een van de hoofdthema’s van haar promotieonderzoek onder begeleiding van Keevash. Veel paden naar een mogelijke oplossing bleken dood te lopen. Soms had Bowtell het idee het hele probleem op te moeten geven. Niks lukte. Op die momenten was joggen de manier om de muur te doorbreken: „Hardlopen in de buitenlucht creëerde ruimte in mijn hoofd om anders tegen het probleem aan te kijken.”

Uiteindelijk vielen de puzzelstukjes dan toch op hun plaats. Bowtell en Keevash maakten veel gebruik van de zogeheten grafentheorie, een tak van wiskunde met toepassingen in onder meer de besliskunde en informatica. Een graaf is, simpel gezegd, een netwerk bestaande uit knooppunten die al dan niet met elkaar zijn verbonden. Ze formuleerden het probleem in termen van ‘koppelingen’ in zo’n netwerk. Een ‘koppeling’ is een verzameling verbindingslijnstukken zonder gemeenschappelijke knooppunten.

Het koninginnenprobleem maakt deel uit van een breed scala aan combinatorische problemen, waarbij wiskundigen zoeken naar algemeenheden en ‘asymptotische’ formules: benaderingen die steeds beter worden naarmate n toeneemt. Bowtell: „Dit soort telproblemen zijn in het algemeen erg moeilijk. Daarom kunnen onze methoden van belang zijn bij het beantwoorden van soortgelijke vraagstukken.”