4x4 Schiebepuzzle
BitMover
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 *
Aber warum kann man folgende Position nie erreichen ?
1 2 3 4
5 6 7 8
9 10 11 12
13 15 14 *
Mir fehlt irgendwie die Idee für den richtigen Beweis.
Für ein 3x3-Puzzle hab ich eine Lösung. Aber die will hier nich so ganz
funktionieren.
Hat jemand eine Idee ?
Matthias Irmscher
werden die Puzzles nicht mit dieser Stellung ausgeliefert?
Die Stellung kann eigentlich erreicht werden, weil in diesem Fall der
Unordnungsparameter U=1 ist, d.h. ein Zahlenpaar ist in der falschen
Anordnung. Wenn man nun ein Paar verschiebt, ändert sich U um 2, weil
gleichzeitig auch ein anderes Paar seine relative Anordnung zueinander
ändert. Somit kann U nie gleich 0 sein. Das bedeutet gleichzeitig, daß das
Rätsel unlösbar ist weil nur bei U=0 alle Zahlen in der richtigen
Reihenfolge sind.
Jedenfalls habe ich mal gelesen, daß die Dinger unlösbar sind, wenn nicht,
hilft Dir der Unordnungsparameter sicherlich in deinem Beweis.
-MATTHIAS
BitMover <ne...@bitmover.de> schrieb in im Newsbeitrag:
8kcuo...@enews3.newsguy.com...
Franz Bauer
wrote:
>Jeder kennt so ein Schiebepuzzle mit den Zahlen 1-15
> 1 2 3 4
> 5 6 7 8
> 9 10 11 12
>13 14 15 *
>
>Aber warum kann man folgende Position nie erreichen ?
> 1 2 3 4
> 5 6 7 8
> 9 10 11 12
>13 15 14 *
Hi!
Zeigen lässt es sich über eine Invariante.
Sei U der "Unordnungsparameter", der angibt, wie viele Zahlenpaare
miteinander vertauscht sind. Bei der ersten Anordnung ist U=0 weil
alle Zahlen geordnet sind. Wenn du jetzt 2 Steine verschiebst, und dir
U wieder ansiehst, wirst du merken dass U immer gerade ist. Wenn du
dir allerdings deine 2. Anordnung ansiehst, ist U=1.
Ich hoffe mit diesem Ansatz kommst du weiter.
Franz Bauer
--
Franz Bauer
Usenet!
Franz Bauer
--
Franz Bauer
>Hi!
>
>Zeigen lässt es sich über eine Invariante.
>Sei U der "Unordnungsparameter", der angibt, wie viele Zahlenpaare
>miteinander vertauscht sind. Bei der ersten Anordnung ist U=0 weil
>alle Zahlen geordnet sind. Wenn du jetzt 2 Steine verschiebst, und dir
>U wieder ansiehst, wirst du merken dass U immer gerade ist. Wenn du
>dir allerdings deine 2. Anordnung ansiehst, ist U=1.
>Ich hoffe mit diesem Ansatz kommst du weiter.
Wenns dich interessiert: Das umgekehrte Rätsel hat Sam Loyd
"erfunden", und dem 1000$ versprochen, der es lösen könne.
Das ganze steht alles sehr anschaulich in "Fermat's letzter Satz" von
Simon Singh beschrieben.
Franz Bauer
--
Daniel Stolze
BitMover wrote:
> Aber warum kann man folgende Position nie erreichen ?
> 1 2 3 4
> 5 6 7 8
> 9 10 11 12
> 13 15 14 *
>
> Für ein 3x3-Puzzle hab ich eine Lösung. Aber die will hier nich so ganz
> funktionieren.
schau doch mal im Internet nach, zum Beispiel
http://www.cut-the-knot.com/pythagoras/fifteen.html
da kann man auch nett puzzlen
viel Spass dabei wünscht Daniel
Herbert Fichtner
wrote:
>Jeder kennt so ein Schiebepuzzle mit den Zahlen 1-15
> 1 2 3 4
> 5 6 7 8
> 9 10 11 12
>13 14 15 *
>
>Aber warum kann man folgende Position nie erreichen ?
> 1 2 3 4
> 5 6 7 8
> 9 10 11 12
>13 15 14 *
>
>Mir fehlt irgendwie die Idee für den richtigen Beweis.
>Für ein 3x3-Puzzle hab ich eine Lösung. Aber die will hier nich so ganz
>funktionieren.
>
>Hat jemand eine Idee ?
>
Der Versuch eines Beweises:
Betrachte die Reihenfolge der Zahlen in einer Schlangenlinie
----
|
----
|
----
|
----
Also z.B. in der Lösungsstellung: 1 2 3 4 8 7 6 5 9 10 11 12 _ 15 14
13. Die Position des leeren Feldes spielt keine Rolle, da man es, ohne
die Reihenfolge der Zahlen zu verändern, an jede Stelle der Schlange
schieben kann. Nun sieht man, dass ein horizontaler Zug die
Reihenfolge nicht ändert. Ein vertikaler Zug führt zu einer zyklischen
Vertauschung von 1, 3, 5 oder 7 Zahlen. Dieses sind alles gerade
Permutationen (Produkt einer geraden Anzahl von Transpositionen). Die
Vertauschung von "14" und "15" ist eine ungerade Permutation und kann
damit nicht erreicht werden.
Gruß
Herbert
--
Was bis jetzt über ShowView-Codes bekannt ist:
http://www.isis.de/members/~fichtner/ShowView/
Markus Schick
schlimmsten Fall zu bestimmen?
Eine untere Schranke ergibt sich einfach durch die Zahl der möglichen Züge
pro Stellung und der Zahl der möglichen (erreichbaren) Stellungen:
Als Zug definiere ich: "bewegen" des Leerfeldes in horizontaler oder
vertikaler Richtung (nicht unbedingt nur um einen Platz)
Dann sind in der Ausgangsstellung 6 Züge möglich und in jeder weiteren 3, da
man nicht zweimal hintereinander horizontal (bzw. vertikal) ziehen muss (das
kann man dann zu einem Zug kombinieren).
Um jetzt jede der 16!/2 = 10461394944000 erreichen zu können, muss ich evtl.
mindestens 27 Züge machen, denn mit 26 erreiche ich maximal 6·3^25 =
5083731656742 verschiedene Stellungen. Und nichteinmal diese, da ich viele
Stellungen auf verschiedenen Wegen erreiche.
Ich vermute, dass 27 noch bei weitem zu wenig ist. Aber wie kann man diese
Zahl besser abschätzen und wie lässt sich das auf andere Puzzles
verallgemeinern (z.B. auf Rubik's Cube).
Man muss wahrscheinlich die Nullzüge (Zyklen) irgendwie berücksichtigen.
(*dichter Nebel*)
Mit dem Computer kann man zwar theoretisch alles durchprobieren, aber ob man
das Ergebnis noch zu Lebzeiten bekommt ... ;-)
Grüße
Markus
Juergen Meurer
und sorry für den Alias.
cu, Juergen Meurer
Franz Bauer <Gre...@gmx.net> schrieb in im Newsbeitrag:
nq6kmsc088dm5c96e...@4ax.com...
Juergen Meurer
Herbert Fichtner <fich...@mail.isis.de> schrieb in im Newsbeitrag:
8kd95s$29j64$1...@ID-28456.news.cis.dfn.de...
Juergen Meurer
unter
http://www.informatik.uni-freiburg.de/~edelkamp/inhalt/node20.html#SECTION00
312000000000000000 findest du eine Beschreibung eines heuristischen
Verfahrens zur bestmöglichen Lösung.
cu, Juergen Meurer
Markus Schick <markus...@eplus-online.de> schrieb in im Newsbeitrag:
B590242B.819F%markus...@eplus-online.de...