Vorige week vond in Gent de conferentie Polygons, Buildings and Related Geometries plaats. Het was een speciale editie ter ere van de 60ste verjaardag van prof. Hendrik Van Maldeghem, die mijn copromotor was doorheen mijn doctoraat en die meer dan twee jaar moest wachten op dit feestelijke congres omwille van de coronasituatie toen.
We werden gevraagd een aandenken voor de meer dan 60 deelnemers te ontwerpen en te realiseren, en het mocht eens iets anders zijn dan de afgezaagde koffietas. Omdat Hendrik behalve een doorwinterd meetkundige ook een puzzelliefhebber is, zochten we naar een originele puzzel. Die hebben we gevonden in de vorm van een schuifpuzzel.
Fysieke schuifpuzzels
Schuifpuzzels zijn al lang welbekend. De allereerste en nog steeds meest gangbare versie is een schuifpuzzel van 4 bij 4 vakjes groot, met 15 blokjes en één gat. De blokjes zijn genummerd van 1 tot en met 15 en de lege ruimte laat toe om ze horizontaal of verticaal te verschuiven. De opgave bestaat erin om alle getallen in de goede volgorde te schuiven, rij per rij oplopend van 1 tot en met 15. De puzzel werd uitgevonden door Noyes Chapman rond 1880 en werd algauw een enorme rage (te vergelijken met de Rubik’s Cube 100 jaar later), niet in het minst nadat de grote puzzelexpert en oplichter Sam Loyd een prijs van $1000 uitloofde voor een oplossing van de concrete uitdaging waarbij enkel de blokjes 14 en 15 omgewisseld waren. Loyd hield trouwens — onterecht — tot zijn dood vol dat hij de uitvinder van de puzzel was. Sindsdien zijn tal van gelijkaardige puzzels verschenen met hetzelfde principe maar met bijvoorbeeld een illustratie op de voorkant of andere afmetingen.
Zoals William Johnson en William Story al in 1879 aantoonden (1) is de uitdaging die Loyd later stelde, onmogelijk — een resultaat waar Loyd zich uiteraard van bewust was toen hij de prijs van $1000 beloofde. Nogal kort door de bocht gaat het argument als volgt. Het gat kunnen we ons ook voorstellen als een blokje, gelabeld met het getal 0. Elke zet wisselt dan twee blokjes (waaronder die met label 0). Om precies twee blokjes van plaats te wisselen, ongeacht hun labels of positie, zijn er dan enerzijds een oneven aantal wissels nodig. Maar anderzijds moet het gat uiteindelijk opnieuw op de startpositie eindigen. Als je het achterliggende 4×4-bord inkleurt met een schaakbordpatroon, dan zie je dat één keer schuiven het gat van een zwarte naar een witte positie brengt of omgekeerd. Dat betekent dat er een even aantal wissels nodig zijn om het gat terug op de startpositie te brengen en zo de puzzel reglementair op te lossen. Met andere woorden, de 14-15-opgave is niet oplosbaar — er zullen altijd twee blokjes overblijven die omgekeerd moeten staan.
Met wat meer werk kun je ook aantonen dat alle configuraties met een even aantal wissels ook effectief op te lossen zijn, dus een willekeurige startconfiguratie is met 50% kans oplosbaar. Goed nieuws voor wie dat oneerlijk vindt: in die 50% van de onoplosbare gevallen kun je wél naar een heel gelijkaardige oplossing toe werken, ook met oplopend gesorteerde getallen maar met het gat linksboven in plaats van rechtsonder.
In deze context moeten we gewoonweg volgend filmpje van Henry Segerman vermelden. Segerman is een wiskundige en kunstenaar gespecialiseerd in virtual reality en 3D-printen. Tussen de tal van fascinerende video’s op zijn YouTubekanaal is bijvoorbeeld ook dit pareltje te vinden, met een aantal fabuleuze varianten van de klassieke 4×4-schuifpuzzel.
Abstracte schuifpuzzels
Vanuit wiskundig standpunt is het concept van een schuifpuzzel heel natuurlijk te modelleren in het framework van grafentheorie. We schreven hier reeds meerdere blogposts over grafen in tal van toepassingen, dus springen we meteen to the point. Los van fysieke restricties is een schuifpuzzel eigenlijk niet veel meer dan een graaf, met op de toppen een aantal gekleurde of genummerde fiches. Eén top blijft leeg, zodat de fiches telkens over een boog kunnen schuiven naar de lege top. De originele 14-15-puzzel bijvoorbeeld komt overeen met de graaf hieronder.
De schuifpuzzelschuifpuzzel die we ontwierpen voor de conferentie, begint met een heel eenvoudige graaf: de complete graaf met vier toppen. Alle vier de toppen zijn onderling verbonden; elke fiche kan dus telkens naar de vrije top worden geschoven. We gebruiken drie fiches, een gele, een rode en een blauwe. In totaal zijn er 24 mogelijke configuraties.
Waarom gebruiken we kleuren en geen getallen? Wat is de “opgeloste” configuratie? Wel … deze schuifpuzzel is zodanig eenvoudig dat het haast beledigend is om er een serieuze opgave op te plakken. Het is niet meer een speelgoedmodel voor abstracte schuifpuzzels op grafen.
Hoe halen we er dan een interessante puzzel uit? Door er een nieuwe graaf van te maken, natuurlijk! Aanschouw:
De puzzelgraaf van een schuifpuzzel is een nieuwe graaf met een top voor elke mogelijke configuratie, verbonden met een andere top als je van de ene configuratie naar de andere geraakt door juist één keer schuiven. Voor de kleine schuifpuzzel met drie fiches waren er 24 configuraties, dus de puzzelgraaf ervan heeft 24 toppen. Er zijn telkens drie zetten mogelijk, het verplaatsen van de rode fiche, de gele fiche of de blauwe fiche naar de lege top. De bogen van de puzzelgraaf kunnen op een natuurlijke manier gekleurd worden met de kleur van de fiches, zodat bijvoorbeeld de rode fiche verschuiven in de puzzel overeenkomt met een rode boog in de puzzelgraaf.
De kleine 2×2-puzzel heeft veel symmetrie en de puzzelgraaf ervan des te meer! De graaf zit vol zeshoeken, die je vindt door twee kleuren afwisselend door te schuiven. In de voorstelling hieronder komen die zeshoeken beter tot hun recht; het geheel zit getekend binnen een grote zeshoek en de bogen aan de rand “lopen door” naar de tegenoverliggende zijde. De puzzelgraaf is niet planair, maar kan wel op een koffietas (of binnen zo’n zeshoek) worden getekend.
Het is precies op deze voorstelling dat we een fysieke schuifpuzzel ontwierpen. We maakten 24 speelstukken, elk bedrukt met één van de mogelijke configuraties. Aan de puzzelgraaf voegden we één top toe in het midden en die graaf op 25 toppen drukten we op een grote muismat. De opgave: leg alle 24 stukjes willekeurig op de toppen en schuif ze over de bogen tot alles “klopt” — twee configuraties op de eindtoppen van een rode boog mogen slechts een zet met de rode fiche schelen, en hetzelfde moet gelden voor blauw en geel.
De stelling van Wilson
De originele 4×4-schuifpuzzel is slechts in de helft van de gevallen oplosbaar, terwijl je bij de kleine 2×2-puzzel van elke configuratie naar elke andere configuratie kan geraken. Hoe zit het met de grote schuifpuzzelschuifpuzzel? Op die vraag gaf Richard Wilson een heel algemeen antwoord.
Wat is het essentiële verschil tussen de oplosbaarheid van de twee puzzels? Het pariteitsargument waarom die ene instantie van de 14-15-puzzel onmogelijk is, geeft een hint: de schaakbordkleuring van de toppen betekende dat configuraties enkel oplosbaar waren als die een even aantal wisselingen vroegen. Concreet konden de toppen van de graaf wit of zwart gekleurd worden op zó een manier dat elke boog een witte en een zwarte top verbond (zodat elke verschuiving het gat verplaatste van een wit- naar een zwartgekleurde top of omgekeerd). Een graaf met die eigenschap wordt bipartiet genoemd. De graaf van de kleine 2×2-schuifpuzzel is niet bipartiet omwille van de “diagonale” bogen.
Bipartitie blijkt de cruciale factor in de oplosbaarheid van een schuifpuzzel, confer de volgende stelling van Wilson (2).
Bekijk een schuifpuzzel op een eindige “voldoende samenhangende” graaf \(G\).
- Als \(G\) een cykelgraaf op \(n\) toppen is, dan bestaat de puzzelgraaf van \(G\) uit \((n-2)!\) samenhangscomponenten.
- Als \(G\) de \(\theta_0\)-graaf is in de figuur hieronder, dan bestaat de puzzelgraaf uit zes componenten.
- Als \(G\) een andere, bipartiete graaf is, dan bestaat de puzzelgraaf uit twee componenten.
- Als \(G\) een andere, niet-bipartiete graaf is, dan is de puzzelgraaf samenhangend.
Merk op dat elke samenhangscomponent van de puzzelgraaf precies alle configuraties van de schuifpuzzel bevat die in elkaar om te vormen zijn door reglementair verschuiven. Met andere woorden, alleen in het laatste geval is elke startconfiguratie oplosbaar naar een vooropgestelde configuratie.
De cykelgrafen zijn dus speciale gevallen (en geven ook maar saaie puzzels) maar opvallend is toch die ene andere uitzondering, de \(\theta_0\)-graaf!
Kijken we nu even terug naar onze schuifpuzzelschuifpuzzel, dan zien we dat de puzzelgraaf van de kleine 2×2-puzzel helaas bipartiet is. Gelukkig moesten we sowieso een 25ste (lege) top toevoegen! Door die goed te kiezen en te verbinden met zowel een witgekleurde als een zwartgekleurde top, konden we ervoor zorgen dat de uitgebreide puzzelgraaf niet langer bipartiet is. Volgens de stelling van Wilson is elke configuratie er dus altijd verschuifbaar naar gelijk welke andere configuratie. Je kan de puzzel dus altijd met een gerust hart starten door er de stukken willekeurig op te leggen.
Merk op dat er in principe 24 oplossingen zijn voor de schuifpuzzelschuifpuzzel: je kan één van de 24 fiches op gelijk welke van de 24 originele toppen schuiven en daarna ligt de nodige positie van alle andere fiches vast.
Er is nog één techniciteitje in de stelling van Wilson. Wat wordt er precies bedoeld met “voldoende samenhangend”? Voor een abstracte schuifpuzzel op een algemene graaf zijn er weinig echte restricties, maar er zijn wel een aantal eigenschappen die je wil opleggen aan de graaf in kwestie om saaie gevallen te vermijden. Waarom je een samenhangende graaf wil, is duidelijk: de ene vrije top in de graaf blijft binnen dezelfde samenhangscomponent en daarbuiten is er dus gewoon geen geschuif mogelijk.
Het kan nog wat sterker. Een top van een graaf heet een articulatietop of splitstop (in het Engels: cut vertex) als de graaf uiteenvalt in meerdere componenten bij verwijderen van die top, zoals hieronder geïllustreerd. Zo’n graaf is dus nog maar nét samenhangend. Bij een schuifpuzzel op zo’n graaf kan geen enkele fiche de splitstop oversteken — je kan alles verschuiven binnen één component, de vrije top doen oversteken naar een andere component en dan daarbinnen verschuiven, et cetera, maar dan ben je eigenlijk gewoon een aantal losse schuifpuzzels aan het oplossen in de aparte componenten. Bij het bestuderen van schuifpuzzels op grafen hoeven we dus enkel te kijken naar 2-samenhangende grafen, zonder splitstoppen — die heten zo omdat er minstens twee toppen verwijderd moeten worden om de graaf niet-samenhangend te maken. De stelling van Wilson spreekt precies over zulke 2-samenhangende grafen.
Varianten
Op schuifpuzzels zijn er tal van varianten en originele twists bedacht. We halen er hier kort nog ene aan: een rotatiepuzzel. Een voorbeeld zijn de Hongaarse Ringen hieronder — de bedoeling is om de balletjes in de linker- en rechtercirkel door elkaar te draaien tot de opgeloste configuratie in de foto. Ook dit soort puzzels valt op precies dezelfde manier te veralgemenen naar algemene grafen: een geldige zet bestaat dan uit het doorschuiven van de fiches langs een cykel. Jaap Scherphuis leidt op zijn webpagina (3) een gelijkaardig resultaat af als de stelling van Wilson voor schuifpuzzels en ook hier blijken er enkele kleine uitzonderlijke gevallen te zijn. Chao Yang gaf een uniforme bespreking (4) van beide puzzels.
Ook al vallen deze twee soorten puzzels heel analoog te bestuderen in hetzelfde grafentheoretische kader, een concrete realisatie is natuurlijk een ander paar mouwen. De fiches in onze schuifpuzzelschuifpuzzel zitten bijvoorbeeld niet vast in een framework … maar voor een rotatiepuzzel zou dat erg onhandig zijn, gezien je daar telkens meerdere fiches ineens verschuift. Over onze concrete uitvoering en het verschil tussen theorie en praktijk volgt binnenkort een tweede blogpost!
- William Johnson, William Story, Notes on the “15” puzzle. American Journal of Mathematics, vol. 2, no. 4, 1879, p. 397–404. (↩)
- Richard Wilson, Graph puzzles, homotopy, and the alternating group. Journal of Combinatorial Theory, vol. 16, 1974, p. 86–96. (↩)
- Jaap Scherphuis, Rotational puzzles on graphs. Webpagina. (↩)
- Chao Yang, Sliding puzzles and rotating puzzles on graphs. Discrete Mathematics, vol. 311, no. 14, 2011, p. 1290–1294. (↩)
