De 15-puzzel
De 15-puzzel is een frame met vijftien genummerde blokjes en één leeg vak. Schuif de blokjes terug op volgorde en hij is opgelost. Het lijkt eenvoudig, maar in 1880 veroorzaakte hij een rage, en erachter schuilt een van de mooiste bewijzen uit de recreatieve wiskunde: de helft van alle stellingen is nooit op te lossen.
De rage van 1880
De puzzel komt uit de staat New York, uit de jaren 1870; Noyes Chapman, postmeester in Canastota, wordt meestal als de uitvinder genoemd. Begin 1880 werd hij een rage, eerst in de hele Verenigde Staten en daarna in Europa.
Sam Loyds 14-15
De Amerikaanse puzzelmaker Sam Loyd beweerde later dat hij de puzzel had uitgevonden, en vertelde over een prijs van 1.000 dollar voor iedereen die hem kon oplossen met alleen 14 en 15 verwisseld. Niemand won de prijs, en niemand kon dat ook: die stelling is onoplosbaar. Zijn claim op de uitvinding klopte evenmin.
Waarom de helft van de stellingen onmogelijk is
Beschouw het lege vak als een zestiende blokje. Elke schuifbeweging verwisselt het lege vak met één blokje. Om terug te komen in zijn hoek moet het lege vak even vaak naar links als naar rechts en even vaak omhoog als omlaag, dus een stelling met het lege vak in zijn hoek ligt altijd een even aantal verwisselingen van de opgeloste volgorde af. 14 en 15 verwisselen is één verwisseling, en dat is oneven, dus geen enkele schuifbeweging kan die stelling bereiken. In 1879 bewezen William Johnson en William Story dat precies de helft van alle opstellingen bereikbaar is.
Een test voor elke stelling
Tel de paren blokjes die in de verkeerde volgorde staan als je het frame rij voor rij leest. Op een 3×3- of 5×5-bord is een stelling oplosbaar als dat aantal even is. Op een 4×4-bord tel je daar de rij van het lege vak bij op, geteld vanaf onderen: de stelling is oplosbaar als de som oneven is.
Oplossen met de computer
Een computer kan met A* een weg terug zoeken, een methode die altijd eerst de meest veelbelovende stelling bekijkt. Die schat de nog benodigde zetten op basis van hoe ver elk blokje van zijn doelvak af staat, plus twee zetten voor elk paar blokjes dat elkaar in de eigen rij of kolom blokkeert. De kortste oplossing vinden wordt op grote borden heel moeilijk. De moeilijkste stellingen van de 15-puzzel hebben 80 zetten nodig, en de 8-puzzel heeft er nooit meer dan 31 nodig.
Probeer het in PictorX
Open de 15-puzzel en klik op een blokje om het te schuiven. Schudden husselt de blokjes tot een nieuwe stelling die oplosbaar is, Oplossen speelt een oplossing zet voor zet af, en ‘Juiste blokjes tonen’ kleurt de nummers van de blokjes die al op hun plek staan. Kies ‘Loyds 14-15’ om de onmogelijke stelling te zien, en wissel met Grootte tussen 3×3, 4×4 en 5×5.
Veelgestelde vragen
Wie heeft de 15-puzzel bedacht?
Noyes Chapman, postmeester in Canastota, New York, wordt meestal als de uitvinder genoemd, in de jaren 1870. Sam Loyds latere claim op de uitvinding was onjuist.
Is de 14-15-puzzel oplosbaar?
Nee. Hij ligt één verwisseling van de opgeloste volgorde af, en elke stelling die schuifbewegingen kunnen bereiken ligt een even aantal verwisselingen af.
Hoeveel stellingen heeft de 15-puzzel?
De 16 vakjes kunnen op 20.922.789.888.000 manieren worden gevuld. Precies de helft daarvan, 10.461.394.944.000, is met schuiven te bereiken.
Uploadt PictorX iets?
Nee. De puzzel wordt op een canvas in je browser getekend. Opslaan downloadt een PNG, en Bewerken opent dat beeld in de PictorX-editor.
Gerelateerde gereedschappen
15-puzzel
Speel de klassieke 15-puzzel, de schuifpuzzel met houten blokjes, in je browser op 3×3, 4×4 of 5×5. Schud, schuif hele rijen in één keer, probeer Sam Loyds onmogelijke 14-15, of kijk hoe Oplossen hem afmaakt.
Torens van Hanoi
Verplaats in je browser een toren van schijven over drie pinnen. Eén schijf tegelijk, nooit een grotere op een kleinere. De kortste oplossing is 2ⁿ − 1 zetten.
Torens van Hanoi
De Torens van Hanoi: drie pinnen, één schijf tegelijk en nooit een grotere op een kleinere. De kortste oplossing is 2ⁿ−1 zetten. Édouard Lucas bracht de puzzel in 1883 uit.
Paardensprong
Laat een schaakpaard precies één keer op elk veld van het bord springen. Speel zelf met de hints van Warnsdorff, of kijk hoe Oplossen een open of gesloten rondgang afmaakt. Sla de route op als PNG.
Acht dames
Plaats acht dames zo op een schaakbord dat geen enkele een andere aanvalt. Probeer het zelf, kijk hoe de zoektocht met backtracking stap voor stap een oplossing vindt, en loop alle 92 oplossingen door.
Langtons Mier
Draai Langtons mier in je browser. Bekijk symmetrie, chaos en de snelweg van 104 stappen, en probeer daarna meerkleurige regels, meerdere mieren, een zeshoekig raster en turmites.
Klaar om het te proberen?
Open PictorX in uw browser - geen installatie, geen creditcard vereist om te starten.
Speel de 15-puzzel