Schuifpuzzel

Een schuifpuzzel

De schuifpuzzel is een puzzel, meestal op een bord van 4 keer 4 velden met 15 verschillende tegels, wat één veld leeg laat, en dan ook 15-puzzel genoemd, maar ook voorkomend in andere afmetingen. In de standaardvariant staan op de 15 tegels de getallen 1 tot en met 15. Een andere mogelijkheid is dat de tegels in één speltoestand als bij een legpuzzel een figuur vormen (voor een legpuzzel is het aantal stukjes dan erg klein, maar de moeilijkheid als schuifpuzzel en die als legpuzzel worden wel meer dan bij elkaar opgeteld: het is niet zo gemakkelijk om twee stukjes naast elkaar te krijgen om te zien of de afbeelding doorloopt; het oplossen van de legpuzzel gaat deels eerst alleen mentaal). Steeds kan een tegel naar het lege veld worden geschoven, waarmee de plaats van de tegel en die van het lege veld dus worden verwisseld.

Het spel is om eerst tegels een groot aantal keer te verschuiven, zodat ze in een schijnbaar willekeurige volgorde op het bord staan, maar daarna de tegels weer in de goede volgorde op het bord terug te schuiven.

Het spel kan online gespeeld worden, en er zijn verscheidene apps met deze puzzel.[1] Hierbij komen ook varianten zoals 3 keer 3 en 7 keer 7 voor. De speelvlakken hoeven niet vierkant te zijn, bijvoorbeeld 4 keer 7 is ook mogelijk. Naast het oplossen op zich kan het gaan om het zo snel mogelijk oplossen in tijd en/of in aantal keer schuiven. Soms wordt het in één keer verschuiven van een rijtje van twee of meer tegels als één keer schuiven geteld.

Constructie

Tegenwoordig is de puzzel vaak geconstrueerd met plastic blokjes die met rails aan elkaar zitten zodat je alleen kunt schuiven en niet kunt valsspelen door een blokje op te tillen. Dit voorkomt ook dat er onmogelijke opgaven gepresenteerd worden: bij verwisseling van twee blokjes ontstaat namelijk een onoplosbare puzzel, zie onder. Het is overigens niet onmogelijk de puzzel te demonteren.

Geschiedenis

Een onoplosbare puzzel uit Sam Loyd's Cyclopedia of 5000 Puzzles; deze wordt soms de 14-15-puzzel genoemd, naar de omwisseling van die nummers.

De oorspronkelijke uitgave bestaat uit losse blokjes in een vierkant bakje.[bron?] Men kan de blokjes eruit halen, schudden en terugdoen, waarmee soms een onoplosbaar probleem wordt gemaakt.

De puzzel is aan het einde van de 19e eeuw bekend geworden, vooral door toedoen van Sam Loyd, die claimde de uitvinder te zijn. In 1880 was de puzzel vooral in Amerika een enorme rage, zowel bij volwassenen als kinderen:

In 1880 vielen hele landstreken van de Verenigde Staten ten prooi aan een ongekende verslaving. “Het is letterlijk een epidemie geworden in het hele land,” schreef The Weekly News-Democrat in Emporia (Kansas). “Hele steden zijn afgeleid, de mensen kunnen niet slapen en worden er gek van.” De epidemie bereikte ook Europa en zelfs Australië en Nieuw-Zeeland. De News-Democrat schreef: “Geen kind zo klein of het wordt erdoor gegrepen, geen man zo sterk of verheven of hij raakt erdoor gefascineerd,”.[2]

Andere schuifpuzzels

Bij uitbreiding is een schuifpuzzel een puzzel waarin je op een bord blokjes moet verschuiven, bijvoorbeeld Rush Hour, Lunar lockout en Sokoban. De genoemde drie werken volgens hetzelfde principe als 'de' schuifpuzzel, maar kennen restricties, door opdrachten voor de speler, de vorm van de speelstenen, hindernissen op het bord of beperkingen in de beweeglijkheid.

Indeling van speltoestanden op basis van permutaties van tegels en leeg veld

We bekijken het geval van een rechthoekige (eventueel vierkante) puzzel met m rijen en n kolommen (een bord van m×n velden). Het aantal denkbare speltoestanden (het geheel van de posities van de mn elementen: mn - 1 tegels en het lege veld) is de faculteit van het aantal velden, oftewel mn! mogelijkheden. Twee speltoestanden worden als equivalent gedefinieerd als de ene door een aantal malen schuiven in de andere kan worden overgevoerd. Deze relatie is inderdaad een equivalentierelatie.

Er zijn verschillende manieren om een speltoestand, en de overgang van de ene naar de andere, te beschrijven, en de mogelijkheid of onmogelijkheid om die overgang met schuiven te bereiken daarin uit te drukken.

Eén manier is om de overgang te beschouwen als een permutatie van mn elementen, namelijk de posities van de tegels en die van het lege veld. Per zet is die permutatie altijd oneven, want elke zet verwisselt een tegel en het lege veld. Als twee speltoestanden equivalent zijn is de pariteit van de permutatie van de mn elementen die de ene in de andere overvoert gelijk aan die van de manhattanafstand tussen de lege velden van de twee speltoestanden (anders gezegd: het dezelfde of een andere kleur hebben van de twee lege velden bij een schaakbordpatroon). Dit volgt eenvoudig uit de observatie dat één keer schuiven de pariteit van de permutatie verandert, en ook de pariteit van de genoemde manhattanafstand (een verandering van de kleur van het lege veld bij een schaakbordpatroon).

Omgekeerd, als van twee speltoestanden de pariteit van de permutatie van de mn elementen die de ene in de andere overvoert gelijk is aan die van de manhattanafstand tussen de lege velden van de twee speltoestanden, en m en n zijn minstens twee, of m = 1 en n < 4 of omgekeerd, dan zijn de twee speltoestanden equivalent.[3]

Draaiingen en spiegelingen van de spelpositie

We kunnen van spiegelingen en draaiingen van de spelpositie (waarbij het uiteraard alleen gaat om de totale positie, niet om de standen van de tegels) beredeneren of deze met schuiven zijn te bereiken. Voor deze eigenschappen behandelen we voor m en n de waarden 2 t/m 5; ze gelden ook voor grotere zijden modulo 4, dus als bij de waarden van m en n, onafhankelijk van elkaar, een viervoud bijgeteld wordt.[4]

Spiegelen in de horizontale as komt neer op n(int(m/2)) verwisselingen, terwijl het lege veld bij een schaakbordpatroon dezelfde kleur houdt desda m oneven is; m + n(int(m/2)) moet dus oneven zijn, dit is het geval bij een speelveld van 2×3, 2×5, 3×2, 3×4, 5×2, 5×3, 5×4, 5×5, maar niet bij een speelveld van 2×2, 2×4, 3×3, 3×5, 4×2, 4×3, 4×4, 4×5. Spiegelen in de verticale as geldt uiteraard analoog, met m en n verwisseld, het kan met schuiven bijvoorbeeld wel bij een speelveld van 3×5, maar niet bij een speelveld van 5×3.

180 graden draaien komt neer op int(mn/2) verwisselingen, terwijl het lege veld bij een schaakbordpatroon dezelfde kleur houdt als m+n even is, het kan dus met schuiven als m+n+int(mn/2) even is. De draaiing is met schuiven te bereiken bij gelijke waarden en als minstens één 2 is, en niet in de gevallen 3×4, 4×3, 3×5, 5×3, 4×5, 5×4. De gevallen waarin het wel kan zijn die waarbij spiegelen in de horizontale as en spiegelen in de verticale as allebei wel of allebei niet kan.

Vierkant speelbord

Het bovenstaande toegepast op een vierkant speelbord:

  • Spiegelen in de horizontale of verticale as kan met schuiven desda n een viervoud plus 1 is.
  • 180 graden draaien kan altijd.

Verder geldt bij een vierkant speelbord:

90 graden draaien komt neer op int(n²/4) cyclische verwisselingen van steeds 4 elementen, die oneven permutaties zijn, terwijl het lege veld bij een schaakbordpatroon dezelfde kleur houdt desda n oneven is. De draaiing is dus met schuiven te bereiken desda int(n²/4) + n oneven is, dit is als n geen viervoud is.

Spiegelen om een diagonale as komt neer op (n²-n)/2 verwisselingen, terwijl het lege veld bij een schaakbordpatroon dezelfde kleur houdt. De spiegeling is met schuiven te bereiken desda n een viervoud of een viervoud plus 1 is. De gevallen waarin het kan zijn die waarbij spiegelen in de horizontale as en 90 graden draaien allebei wel of allebei niet kan.

Indeling van speltoestanden op basis van volgorde van tegels langs een pad

Als een volgorde van alle velden langs een zichzelf niet doorsnijdend pad van horizontale en verticale lijnstukken wordt gekozen (zoals bijvoorbeeld de zigzagvolgorde aangegeven met de groene lijn in de figuur), dan is voor de indeling in twee equivalentieklassen alleen de volgorde van de mn - 1 tegels langs dit pad van belang; de mn bijbehorende speltoestanden, corresponderend met de plaats van het lege veld, zijn duidelijk equivalent. De indeling van speltoestanden kan dan worden gereduceerd tot een indeling in permutaties van de mn - 1 tegels.

Als m en n minstens twee zijn dan zijn de met schuiven mogelijke permutaties de even permutaties, die de alternerende groep vormen.

Als m = 1 heeft elke equivalentieklasse slechts één permutatie van tegels, en zijn er dus ( n - 1 )! equivalentieklassen. Alleen voor n = 3 geldt dan dat er twee equivalentieklassen zijn en dat de met schuiven mogelijke permutaties de even permutaties zijn (de identiteit is dan de enige even permutatie). Voor grotere n zijn de even permutaties, behalve de identiteit, met schuiven niet mogelijk. Voor kleinere n is er maar één equivalentieklasse. Een en ander geldt uiteraard analoog met m en n verwisseld.

Zigzagvolgorde van de 16 velden, met een speltoestand waarbij de eerste 9 tegels in de standaardvolgorde staan, met twee mogelijke zetten

In de figuur zijn twee voorbeelden van zetten aangegeven:

  • De blauwe pijl: De tegel schuift vier plaatsen naar voren, van de tweede naar de zesde positie in de rij van 15 (met negeren van de positie van het lege veld). Het tegelnummer als functie van de plaats in de rij van 15 gaat van bijvoorbeeld (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15) naar (1, 3, 4, 5, 6, 2, 7, 8, 9, 10, 11, 12, 13, 14, 15), wat neerkomt op de even permutatie (6 5 4 3 2) van de plaatsen of de inverse even permutatie (2 3 4 5 6) van de tegelnummers.
  • De rode pijl: De tegel schuift twee plaatsen terug, dit is de even permutatie (9 8 7) van de tegelnummers.

Op een bord van 2 bij 3 zijn er 720 speltoestanden, waarbij dit aantal gereduceerd wordt tot 120 als weer de plaats van het lege veld buiten beschouwing wordt gelaten. Omdat het pad gesloten kan worden is cyclische verwisseling triviaal, zodat we ons kunnen beperken tot het bekijken van 24 cykels. Bij elk van deze drie aantallen is de helft vanuit een gegeven startsituatie een mogelijke stand. De cykel verandert niet bij zetten langs de rand van het speelbord, maar alleen als een tegel wordt geschoven naar de tegenover liggende plaats in de cykel (wat neerkomt op cyclische verwisseling van drie opeenvolgende tegels langs de rand, met handhaving van de directe opeenvolging langs de rand van twee van de drie, en van de overige twee van de vijf tegels). Vanuit een bepaalde cykel zijn 5 cykels met één zo'n zet te bereiken, 5 met twee en 1 (namelijk de omgekeerde cykelvolgorde) met drie. De 12 cykels kunnen gerelateerd worden aan de 12 hoekpunten van een icosaëder, waarbij een zet correspondeert met een verplaatsing langs een ribbe. Elk zijvlak correspondeert met een tegelpaar dat in dezelfde volgorde direct achter elkaar staat in de drie cykels corresponderend met de drie hoekpunten van het zijvlak. De overige drie tegels zijn in die drie cykels steeds cyclisch verwisseld.

Een gesloten pad langs alle velden, zoals hierboven op een bord van 2 bij 3, kan alleen bij een even aantal velden. Het al of niet bereikbaar zijn van spelstanden kan dan in termen van cykels van mn-1 tegels plaatsvinden in plaats van in termen van permutaties van mn-1 tegels. Dit reduceert het aantal gevallen van (mn-1)! naar (mn-2)!

Nummering van tegels

Vaak zijn de tegels van een 15-puzzel genummerd van 1 tot en met 15, met als mogelijke speltoestand (vaak de doeltoestand), regelsgewijs gelezen (steeds van links naar rechts), de numerieke volgorde, en met het lege veld in de laatste regel. De bereikbare speltoestanden zijn dan dus die waarbij, in zigzagvolgorde gelezen, de tegelvolgorde een oneven permutatie van de numerieke volgorde is. Dit is bijvoorbeeld niet het geval als de tegels, regelsgewijs gelezen (steeds van links naar rechts), in numerieke volgorde staan, en het lege veld zich in de eerste regel bevindt. In zigzagvolgorde gelezen is dit namelijk een tegelvolgorde die met vier verwisselingen kan worden verkregen uit de numerieke volgorde.

Er zijn puzzels vervaardigd waarvan de tegels niet genummerd zijn. Zo is er een reclamepuzzel met de letters TEMP-OZAK-DOEK-JES. Als deze niet oplosbaar blijkt te zijn, is het probleem te verhelpen door twee identieke letters te verwisselen (zie ook onder). Er is er ook een met de familie Flintstone (Fred, Wilma, Betty en Barney). Elke persoon staat op vier tegels afgebeeld, behalve Barney, die kleiner is en op drie tegels staat. Men kan de personen in verschillende volgorden zetten. Niet elke volgorde is mogelijk.

Stapsgewijze oplossing

Neem hierna aan dat m en n minstens twee zijn. Het probleem is om vanuit een bepaalde spelstand een bepaalde equivalente doelspelstand te bereiken (vaak een standaardstand met bijvoorbeeld het lege veld rechtsonder).

De complexiteit van de puzzel is in zoverre niet al te groot, dat deze, afgezien van de laatste twee of drie regels, regel voor regel kan worden opgelost: als bovenaan en/of onderaan aansluitend hele regels tegels op de juiste uiteindelijke plaats terecht zijn gekomen (zonder regels waar het lege veld moet komen), dan is de puzzel (als die oplosbaar is) verder op te lossen zonder die tegels nog te verschuiven.

Vervolgens geldt logischerwijs hetzelfde in de dwarsrichting, waarna een 2×3 of 3×2 puzzel overblijft.

Het op de juiste uiteindelijke plaats terecht laten komen van een rij tegels (de eerste na het voltooide deel van de puzzel) kan, als er nog minstens 3 regels over zijn, ook weer tegel voor tegel, behalve bij de laatste twee tegels: daar moet men vóór het plaatsen van de voorlaatste tegel al de plaatsing van de laatste voorbereiden. Men kan bijvoorbeeld de tegel die op de voorlaatste plaats moet komen eerst op de laatste plaats terecht laten komen en de tegel die op de laatste plaats moet komen eronder, dan de voorlaatste plaats leeg maken, en dan de laatste twee tegels op hun plaats schuiven.

Bij het uiteindelijke oplossen van de 2×3 of 3×2 puzzel is er minder manoeuvreerruimte. Los van de zetten langs de rand van dit bordje van 6 velden kan nog drie keer een oversteek naar de andere kant van de cykel van 5 tegels nodig zijn, zie boven. Met twee daarvan kan het probleem worden gereduceerd tot het oplossen van een resterende 2×2 puzzel. Als de twee tegels die aan een van de korte zijden van de rechthoek terecht moeten komen in de ligging langs de rand direct achter elkaar staan, maar in de verkeerde volgorde (gezien in de goede volgorde staan er dus drie tussen) dan kan dit aantal van drie eerst gereduceerd worden tot één door een van de twee eerstgenoemde tegels de oversteek te laten maken. Vervolgens kan die ene er tussenuit gehaald worden door die de oversteek te laten maken. Als de twee op hun plaats gedraaid zijn resteert als laatste fase het oplossen van de resterende 2×2 puzzel, wat triviaal is. Als van de doelspeelstand niet bekend was of die te bereiken zou zijn, en men heeft dat ook nog niet uitgerekend, dan wordt dat nu duidelijk. Als twee tegels identiek zijn dan is er altijd een oplossing. Een onoplosbare resterende 2×2 puzzel betekent dat de twee exemplaren verwisseld moeten worden, zie onder.

Optimale zettenreeksen

Voor een bord van 4 keer 4 is het volgende aangetoond over optimale zettenreeksen:

  • Bij eentegelverschuivingen is elke positie in 80 zetten op te lossen. Er zijn zes posities die 80 zetten vereisen.[5]
  • Bij meertegelverschuivingen is elke positie in 43 zetten op te lossen. Er zijn zestien posities die 43 zetten vereisen.[6]

Geval waarbij sommige tegels identiek zijn

Een bijzondere situatie doet zich voor als van de mn - 1 tegels er twee hetzelfde uitzien. Stel dat in de puzzel tegels worden onderscheiden door de teksten erop dan zou dit dus neerkomen op twee tegels met dezelfde tekst. Dan moet een speltoestand in de zin van configuratie van tegelexemplaren onderscheiden worden van een speltoestand in de zin van configuratie van teksten: er zijn dan steeds twee denkbare configuraties van tegelexemplaren met dezelfde configuratie van tekst (bij een denkbeeldige verwisseling van de identieke tegels ziet het resultaat er hetzelfde uit), met één in de ene en één in de andere equivalentieklasse. Vanuit elke denkbare configuratie van tegelexemplaren is dus een bepaalde configuratie van tekst te bereiken. Als de puzzel niet oplosbaar lijkt omdat uiteindelijk alle tegels goed liggen op twee na die onderling zijn verwisseld, dan moeten de twee identieke tegels verwisseld worden (men kan dus niet zonder meer de puzzel regel voor regel oplossen, zoals in het geval van allemaal verschillende tegels). Als bijvoorbeeld bij een 2 bij 3 puzzel de oplossing "de. dag" is en de beginstand "add eg." dan blijkt uiteindelijk dat de eerste d van "add eg." op de eerste regel moet terugkomen, en de tweede d op de tweede regel moet komen. Bij een grotere puzzel kan het lastig zijn in een vroeg stadium te bepalen welk exemplaar van twee identieke tegels op de ene en welk op de andere plaats moet komen. Men probeert dan één mogelijkheid, en als dat niet lukt kan men zoals gezegd alsnog de twee verwisselen. Bij de triviale speelborden van 1 bij 3 en 2 bij 2 werkt het hetzelfde. Deze gevallen zijn nuttig als illustratie, alleen is het daar direct duidelijk welk exemplaar op welk van de twee doelvelden moet komen.

Als vier tegels twee aan twee gelijke teksten hebben zijn er steeds vier denkbare configuraties van tegelexemplaren met dezelfde configuratie van tekst, met twee in de ene en twee in de andere equivalentieklasse. Vanuit elke denkbare configuratie van tegelexemplaren zijn er dan steeds twee configuraties van tegelexemplaren met een bepaalde configuratie van tekst te bereiken. Als de puzzel niet oplosbaar lijkt omdat uiteindelijk alle tegels goed liggen op twee na die onderling zijn verwisseld, dan moet één paar van twee identieke tegels verwisseld worden.

Als drie tegels dezelfde tekst hebben zijn er steeds zes denkbare configuraties van tegelexemplaren met dezelfde configuratie van tekst, met drie in de ene en drie in de andere equivalentieklasse. Vanuit elke denkbare configuratie van tegelexemplaren zijn er dan steeds drie configuraties van tegelexemplaren met een bepaalde configuratie van tekst te bereiken. Als de puzzel niet oplosbaar lijkt omdat uiteindelijk alle tegels goed liggen op twee na die onderling zijn verwisseld, dan moeten twee van de drie identieke tegels verwisseld worden.

Trivia

De Franse naam voor de puzzel wordt internationaal gebruikt voor een operatie in de combinatoriek: jeu de taquin.

Zie de categorie 15 puzzle van Wikimedia Commons voor mediabestanden over dit onderwerp.