Loyd's Puzzle (Puzzle 15)

Mathematiker · Verfasst: Di 23.12.14 18:33

Hallo,
das nachfolgende Programm ist als Ergänzung zur Adventsrätselaufgabe vom 22.12.2014 gedacht.

Dieses Puzzle wurde erstmals 1878 von Sam Loyd beschrieben und wird daher auch Loyd's 15 genannt.
Es besteht aus 15 Quadraten, welche die Ziffern 1 bis 15 enthalten, die in einem 4 x 4-Quadrat angeordnet sind. Das 16. Feld bleibt frei.
Aufgabe ist es, die 15 zunächst unsortierten Quadrate durch Verschieben jeweils eines Quadrats auf die leere Position numerisch zeilenweise von links nach rechts zu ordnen.

In diesem Programm können auch andere Spielfeldgrößen untersucht werden.
Um die Spielfelder zu mischen, klickt man entweder auf den Schalter "Spielfeld mischen" oder markiert das Feld "Klick und Verschieben tauscht Felder". Im zweiten Fall kann man ein Spielfeld mit der Maus anklicken und an die von Ihnen gewünschte Position verschieben. Wird nach einer solchen Änderung ein Feld rot markiert, so ist das Puzzle nicht lösbar.
Ist das Feld "Mausklick bewegt auf freies Feld" markiert, kann man versuchen, das Puzzle selbst zu lösen.

Außerdem sucht das Programm auch nach einer optimalen Lösung.
Der Lösungsalgorithmus gehört zu den NP-Problemen, deren Laufzeit mit mehr Ausgangsdaten sehr schnell ansteigt. Findet das Programm eine Lösung, wird diese dargestellt und die Schrittfolge in einer Liste angezeigt.

Das Programm basiert auf der Lösung von Gary Darby (www.delphiforfun.org...ograms/15puzzle.htm). Ich habe nur ein paar Änderungen durchgeführt.

Viel Spaß beim Puzzlen.
Mathematiker

Einloggen, um Attachments anzusehen!

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

Horst_H · Verfasst: Di 23.12.14 22:18

Hallo,

ich wollte doch mal wissen, ob der kürzeste Weg gefunden wird.
Es sind ja 16! = 2E13 Anordnungen bei einem 4x4 Feld.Das passt ja in keinen PC rein.
Ich habe dazu 2000 Zufallszüge fürs mischen verwendet.
Dank dem Knopf "Anfangstellung" kann man das ja gut testen.
Bei einer Suchtiefe von -> Züge/Laufzeit ergibt sich folgendes bei mir:

markieren

Quelltext

1:
2:
3:
4:
5:
6:
7:
8:
9:

100->134 /  0 s
 75-> 90 /  0 s
 50-> 82 /  0 s
 33-> 66 /  0 s 
 23-> 62 /  1 s

 22-> 54 /  2 s
 20-> 54 /  6 s
 17-> 54 / 46 s

Andere "Mischungen" hatten bei Suchtiefe 37 die wenigsten Schritte, immerhin 74. ( 28 ergab 78 Schritte )

Das ist doch ganz gut.
Wenn ich daran denke, das ich bestimmt 172-mal vor mich hin geklickt habe.

Apropos mischen, warum nicht einfach Fisher-Yates-Mischen, wenn man über 100 ( 74 Schritte war bisher das höchste, aber das Bedarf mehr Untersuchungen ) bei Mischen eingibt.

Gruß Horst

Mathematiker · Verfasst: Di 23.12.14 23:18

Hallo,
der Algorithmus von Gary Darby zur Suche nach möglichst wenigen Zügen ist ziemlich gut, aber nicht optimal.
U.a. durch Ralph Udo Gasser wurde nachgewiesen, dass bei jeder Ausgangsstellung maximal 80 Züge notwendig sind. Er gab neun Konfigurationen in "Harnessing Computational Resources for Efficient Exhaustive Search" mit 80 Zügen an. 2 weitere fand Adrian Brüngger und im Juni 2009 mein Kollege Siegfried Beyer fünf weitere derartige Ausgangssitutationen. Diese sind (_ ist das freie Feld):

Zitat:

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

Für die Stellung
spiel15

findet das Programm minimal 104 bzw. 106 Züge und nicht die 80.
Die kürzeste Zugfolge wäre

Zitat:

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

Beste Grüße
Mathematiker

Einloggen, um Attachments anzusehen!

_________________
Töten im Krieg ist nach meiner Auffassung um nichts besser als gewöhnlicher Mord. Albert Einstein

gerd8888 · Verfasst: Mi 24.12.14 16:57

Es gibt 1*2*3 ... *15*16 Möglichkeiten (Leerfeld mit berücksichtigt) das Spielfeld zu bestücken.
Interessant waere vielleicht zu wissen, bei welcher Konstellation, wieviel Schritte max. benötigt werden.
Mit Brute Force langsam die Schrittzahl um 1 erhöhen, würde ein sicheres und das schnellste Vorgehen gewährleisten.
Denn wenn man nur die Zahlen der Reihenfolge anordnet dauert das evt. länger.

Wie sollte man sonst vorghen, wenn einem der Darby Algorithmus nicht ausreicht? Gibt's da noch andere Lösungsmöglichkeiten?

Gerd

Horst_H · Verfasst: Do 25.12.14 11:15

Hallo und O Du fröhliche,

user profile icon

Mathematiker hat doch oben mehrere Stellungen in seinem Zitat angegeben.
Man beginnt oben links und macht bei erreichnen des rechten Randes in der Zeile darunter weiter.
Die oberste Stellung ist darunter als 4x4-Bild dargestellt
Wenn den ganzen Beitrag nochmals in Ruhe durchliest, dem Link folgst und nach "Harnessing Computational Resources for Efficient Exhaustive Search" suchst, sind zum Großteil Deine Fragen beantwortet,
80 Züge scheint ein oberes Limit zu sein.

Gruß Horst

gerd8888 · Verfasst: Fr 26.12.14 13:57

Diese 80 Schritte, wo Mathematiker mehrere Stellungen angibt, sind also amtlich. Kuerzer wird es nicht gehen!?
Ein Kollege sagte zu mir damals: "Warum das Rad neu erfinden". So ist das bei dem Rätsel letztendlich doch auch?

Eine Frage habe ich noch zu der hashunit. Diese Zeile finde ich immer am interessantesten:

markieren

Delphi-Quelltext

1:
2:
3:
4:

begin
    result:=1;
    for i:=1 to length(s) do result:=((result shl 4)+ ord(s[i])) mod maxhash{length(Objects)};
end;

Hat Aehnlichkeiten mit dem Elfhash, nur ist obiger kürzer. Ob er auch besser ist?

markieren

Delphi-Quelltext

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

Function elfhash(Const Value: String): Cardinal; // ELF-Hash
Var
  i: Integer;
  x: Cardinal;
Begin
  Result := 0;
  For i := 1 To Length(Value) Do Begin
    Result := (Result Shl 4) + Ord(Value[i]);
    x := Result And $F0000000;
    If (x <> 0) Then
      Result := Result Xor (x Shr 24);
    Result := Result And (Not x);
  End;
End;

Gerd

Horst_H · Verfasst: Fr 26.12.14 20:49

Hallo,

die Speicherbelastung durch das Programm ist etwas merkwürdig.
Der Speicher wird nicht freigegeben, wohl nur als "deleted" markiert, aber auch nicht vollständig neu benutzt.
Beispielsweise habe ich bei 200.000 Schritten abgebrochen und dann nochmals gemischt und neu suchen lassen.Nach 100.000 Suchschritten nimmt der Speicher wieder zu.
Die entstehende Datenmenge ist gewaltig, da wäre Feinschliff nötig, aber das andere Programm soll ja 2000-fach schneller sein. Das lohnt wohl kaum ;-)

Gruß Horst

Horst_H · Verfasst: So 28.12.14 11:04

Hallo,

auf wikipedia wurde auch dies verlinkt:
Large-Scale Parallel Breadth-First Search
Dort wurden 2004 alle Lösungen zu dem Loyd Puzzle 15 in 30 Tagen gefunden mit Beschreibung der entsprechenden Hardware Probleme.
Interessant wäre, wie lange die vollständige Überprüfung heute mit SSDs dauern würde.
Im Kapitel "Efﬁcient Permutation Encoding" wird die Bestimmung der Nummer einer lexikografischen Permutation in linearer Zeit gezeigt, die nur eine relativ ( n! ) dazu eine sehr kleine Tabelle ( 2^n) braucht.
Das kann man ja als Ausgangspunkt für den Hash-Wert nehmen.
Ein Problem vom vorgestellten Programm ist auch der enorme Speicherbedarf für jeden neuen Knoten, max.85 MB für 2E5 Knoten.
Bei 2 GB war bei mir Schluß.

Gruß Horst

	Mitgliederliste
	Gruppen
	Das Team
	Richtlinien
	Synonyme