Zo gebruik je de schuifpuzzel-oplosser
Typ het nummer van elke steen op de plek waar hij op je bord ligt, rij voor rij, en laat het gat leeg. Druk dan op Oplossen. De oplosser controleert het bord, zoekt de kortste oplossing en toont die als een lijst stenen om te schuiven. Druk op Afspelen om te kijken, of stap er met de pijlen doorheen. Schakel over naar Stenen schuiven om de puzzel zelf te spelen door op stenen naast het gat te tikken. Husselen geeft je een willekeurig bord dat op te lossen is.
Voor de kleinere 3 x 3-versie kies je 8-puzzel. Je kunt een bord ook als tekst plakken, bijvoorbeeld 5 1 2 4 9 6 3 8 13 10 7 11 0 14 15 12, met 0 of _ voor het gat.
Is elk bord op te lossen?
Nee: precies de helft van alle opstellingen is niet op te lossen, en de oplosser zegt dat al voordat hij gaat zoeken. De test gebruikt inversies: lees de stenen rij voor rij en tel de paren waarbij een groter getal vóór een kleiner getal staat.
- 8-puzzel (3 x 3): op te lossen precies als het aantal inversies even is. Een schuifzet langs een rij verandert niets; een zet omhoog of omlaag springt een steen over twee andere heen en verandert het aantal met 0 of 2.
- 15-puzzel (4 x 4): een verticale schuifzet springt een steen over drie andere heen, dus het aantal inversies verandert met een oneven getal terwijl het gat één rij opschuift. Inversies plus de rij van het gat, van onderen geteld, houdt daardoor altijd dezelfde pariteit, en op het opgeloste bord is die oneven. Een bord waarop die som even is, is nooit op te lossen.
Het bekende voorbeeld is een opgelost bord met 14 en 15 verwisseld: één inversie, gat op de onderste rij, samen 2, even, dus onmogelijk.
Hoe de oplosser de kortste oplossing vindt
De oplosser gebruikt IDA* (iterative deepening A*), een zoekmethode die alle oplossingen tot een bepaalde lengte probeert en die grens steeds verhoogt tot er een werkt. Hij wordt gestuurd door een schatting van het aantal zetten dat nog nodig is die nooit te hoog uitvalt, en daardoor is de eerste oplossing die hij vindt een kortste.
- Voor de 8-puzzel is de schatting de Manhattan-afstand (hoe ver elke steen van zijn plek ligt, in rijen plus kolommen) plus een correctie voor stenen die elkaar in hun eigen rij of kolom blokkeren (lineaire conflicten). Elke 8-puzzel wordt in een fractie van een seconde optimaal opgelost.
- Voor de 15-puzzel gaan makkelijke borden net zo; voor moeilijkere bouwt de oplosser drie patroondatabases: exacte aantallen zetten voor elke plaatsing van de stenen 1, 5, 6, 9, 10, 13, van de stenen 7, 8, 11, 12, 14, 15 en van de stenen 2, 3, 4. Bij elkaar opgeteld, en ook gecontroleerd op het bord gespiegeld langs de diagonaal, geven ze een veel scherpere schatting. Het opbouwen duurt een of twee seconden, in je eigen browser.
De meeste willekeurige 15-puzzels worden binnen een paar seconden optimaal opgelost. De moeilijkste stellingen hebben tot 80 zetten nodig en kunnen veel langer duren, dus het zoeken heeft een grens van 15 seconden. Is die bereikt, dan schakelt de oplosser over op een snelle methode (eerst de bovenste rij, dan de eerste kolom, dan de overgebleven 3 x 3 optimaal) en vermeldt hij dat die oplossing niet de kortste is.
In onze tests kwamen de uitkomsten voor de 8-puzzel overeen met een volledige tabel van de exacte afstanden van alle 181.440 oplosbare stellingen, kwamen de uitkomsten voor de 15-puzzel overeen met een tweede, onafhankelijke zoekmethode, en werd elke oplossing steen voor steen nagespeeld.
Voorbeeld
Het voorbeeldbord 5 1 2 4 / 9 6 3 8 / 13 10 7 11 / _ 14 15 12 is in 9 zetten opgelost: schuif 13, 9, 5, 1, 2, 3, 7, 11, 12. Probeer voor de 8-puzzel eens 8 6 7 / 2 5 4 / 3 _ 1: dat is een van maar twee stellingen van de 8-puzzel die 31 zetten nodig hebben, het maximum voor een 8-puzzel.
Tip om met de hand op te lossen
Los eerst de bovenste rij op, dan de linkerkolom, en laat die liggen: wat overblijft, is een kleinere puzzel. Zet de laatste twee stenen van een rij samen op hun plek door de laatste onder zijn plek te parkeren en ze dan allebei in te draaien.
Nog een puzzel waarbij elke zet telt: de Rubik's Cube oplossen met een oplosser die maximaal 22 zetten nodig heeft. Of schuif tegels tot 2048 met 2048 met AI, dat je ook een tip voor de beste zet geeft.
Oplosser getest op . Iets mis? Laat het ons weten.
Veelgestelde vragen
Waarom is mijn schuifpuzzel niet op te lossen?
De helft van alle opstellingen van de stenen is met schuiven niet te bereiken. Is het aantal inversies plus de rij van het gat (van onderen) even, dan lost geen enkele reeks schuifzetten het bord op. Bij een echte puzzel gebeurt dat als er twee stenen zijn uitgehaald en verwisseld. Verwissel twee willekeurige stenen en hij is wel op te lossen.
Hoeveel zetten kan een 15-puzzel maximaal nodig hebben?
80 zetten van één steen. Computerberekeningen hebben aangetoond dat elke oplosbare stelling van de 15-puzzel in 80 zetten of minder op te lossen is, en dat sommige stellingen alle 80 nodig hebben. Voor de 8-puzzel is het maximum 31.
Is de oplossing echt de kortste?
Als bij het resultaat bewezen optimaal staat, ja: de zoekmethode heeft gecontroleerd dat er geen kortere oplossing bestaat. Raakt de grens van 15 seconden op bij een heel moeilijk bord, dan krijg je een snelle oplossing, duidelijk gemarkeerd als niet de kortste.
Hoe tel ik inversies?
Lees de stenen rij voor rij en sla het gat over. Tel voor elke steen hoeveel stenen erna een kleiner nummer hebben. Tel al die aantallen bij elkaar op.
Stuurt de oplosser mijn bord ergens naartoe?
Nee. Het zoeken gebeurt in je browser, in een achtergrondproces; er wordt niets geüpload.