Schuifpuzzel

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken
Een schuifpuzzel.

De schuifpuzzel is een puzzel op een bord van 4 keer 4 vierkante velden met 15 verschillende tegels en een leeg veld. 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. De puzzel is vaak zo geconstrueerd dat je alleen kan schuiven, en niet kan "valsspelen" door een tegel op te tillen. De puzzel is ook als app verkrijgbaar.[1] 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 twee of meer tegels als één keer schuiven geteld. Het minimaal benodigde aantal keer schuiven is, afhankelijk van de beginstand, maximaal 80 (eentegelverschuivingen) of 43 (meertegelverschuivingen).[2][3]

De puzzel is aan het einde van de 19e eeuw bekend geworden, vooral door toedoen van Sam Loyd, die claimde de puzzel te hebben uitgevonden.

Bij uitbreiding is een schuifpuzzel een puzzel waarin je op een bord blokjes moet verschuiven, bijvoorbeeld Rush Hour en Lunar lockout.

Wiskundige behandeling[bewerken]

We bekijken het algemenere geval van een puzzel met m bij n velden. Het aantal denkbare speltoestanden (het geheel van de posities van de mn elementen: mn - 1 tegels en het lege veld) is (mn)! 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.

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 een verwisseling van een tegel en het lege veld is en dus een verandering van de pariteit van de permutatie, en ook een verandering van 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.

Als m en n minstens twee zijn, of m = 1 en n = 3 of omgekeerd, dan zijn er twee equivalentieklassen.

Als m = 1 heeft elke equivalentieklasse slechts n elementen, en zijn er dus ( n - 1 )! equivalentieklassen; voor n = 1 en n = 2 dus één (en analoog met m en n verwisseld).

Neem hierna aan dat m en n minstens twee zijn.

De complexiteit van de puzzel is in zoverre niet al te groot, dat deze, afgezien van de laatste twee regels, regel voor regel kan worden opgelost: als op de eerste k van de m regels (met k < m - 1) de tegels op de juiste uiteindelijke plaats terecht zijn gekomen, dan is de puzzel (als die oplosbaar is) verder op te lossen zonder die tegels nog te verschuiven.

Als er nog maar twee regels over zijn geldt logischerwijs hetzelfde in de dwarsrichting, waarna een triviale 2 bij 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.

Geval waarbij sommige tegels identiek zijn[bewerken]

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.

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.