Schuifpuzzel altijd op te lossen?

[Dijkhuis]

Crisp heeft zo'n ouderwetse schuifpuzzel geprogrammeerd, zie [topic=380329/1/33] . Hij gooit daarbij de blokjes ruwweg door elkaar, waardoor volgens mij de puzzel in bepaalde (de helft?) van de gevallen niet meer op te lossen is.

twee vraagjes:

a) is dat zo?

b) Kun je wiskundig bepalen of de puzzel oplosbaar is (of: door welke blokjes om te draaien hij wel oplosbaar wordt.)

[joepP]

a) ja
b) ja

Ik weet alleen niet meer precies hoe het zat, en ik ben nu te lui om erover na te denken

Wat ik wél zeker weet, is dat de volgende schuifpuzzel niet oplosbaar is:

code:

 1  2  3  4
 5  6  7  8
 9 10 11 12
13 15 14

[Anoniem: 20737]

Volgens mij is een schuifpuzzel altijd op te lossen, alleen ik weet niet of dat wiskundig te bewijzen valt

[Canaria]

Niet alle schuifpuzzels zijn op te lossen, alleen als er een even aantal stukjes tov het origineel is verwisseld.(grafentheorie)

[Lord Daemon]

Als je de operator P_xy definieert als de operator die stukje x en stukje y omwisselen, dan is de puzzel alleen oplosbaar uit toestand A als je toestand A uit de begintoestand kan construeren door een even maal een operator P op de begintoestand te laten werken.

[Diadem]

haas, Lord Daemon: En nu nog een bewijs?

[crisp]

Op donderdag 24 januari 2002 12:06 schreef haas het volgende:
Niet alle schuifpuzzels zijn op te lossen, alleen als er een even aantal stukjes tov het origineel is verwisseld.(grafentheorie)

Dus als ik zeg maar een array maak met alle stukjes, en er x maal random 2 verwissel, dan is de puzzel altijd oplosbaar zolang x een even getal is?
In dat geval is mijn probleem opgelost en is mijn dank groot!

[GeeBee]

Op donderdag 24 januari 2002 13:26 schreef Lord Daemon het volgende:
Als je de operator P_xy definieert als de operator die stukje x en stukje y omwisselen, dan is de puzzel alleen oplosbaar uit toestand A als je toestand A uit de begintoestand kan construeren door een even maal een operator P op de begintoestand te laten werken.

Oftwel: als je begint met een "goede" schuifpuzzel en die door elkaar husselt volgens de regels waarmee je 'm ook kunt oplossen, dan is de verhusselde puzzel ook weer op te lossen.
Dat bedoel je toch?

[Anoniem: 13428]

Hij is inderdaad niet altijd op te lossen, als het een oneven permuatie van de stukjes betreft dan kan het niet.

Elke keer als je een stukje verschuift noem je dit een transpositie, je verwisselt als het ware het lege vakje met een ander vakje.

Stel nu dat je een gehusselde puzzel hebt en je gaat kijken hoeveel verwisselingen je nodig hebt om de puzzel goed te krijgen - dus voor dit idee mag je ook stukjes nemen die niet naast elkaar liggen - dan heb je altijd een even of oneven aantal verwisselingen nodig.

Als je van een situatie uitgaat waarin de puzzel op zich geschudt is, maar het lege hokje al wel goed zit, dan is de puzzel alleen door schuiven op te lossen wanneer het aantal verwisselingen dat je nodig hebt om deze op te lossen (dus niet door perse te schuiven, maar op te pakken, zoals hierboven) even is.

Immers het lege vakje moet net zovaak naar rechts geschoven worden als het naar links geschoven worden wil het goed uitkomen. Een beroemd voorbeeld van een puzzel die niet oplosbaar is:

code:

1  2  3  4
5  6  7  8
9  10 11 12
13 15 14

Door gewoon te wisselen, dus de 14 met de 15, los je de puzzel op. Maar dit is maar 1 zet en dat is oneven, dus door te schuiven kun je deze puzzel nooit oplossen.

[edit]

Ik kan straks misschien nog een iets formeler bewijs geven.

[edit2]

De verschillende ordeningen van de stukjes noem je permutaties en de helft is even en de helft van die permuaties is inderdaad oneven.

[Lord Daemon]

haas, Lord Daemon: En nu nog een bewijs?

Moet wel te vinden zijn. (En dan bedoel ik niet met een zoekmachine, maar zelf.) Iedere 'zet' kan je zien als een operator die het lege vakje verwisselt met een ander vakje. Met wat moeite moet je dan wel kunnen laten zien dat wat ik beweerde geldt.

Maar he, ik ben een natuurkundige - mijn stelling is empirisch afgeleid.