Eine gute Randomizer für Puzzle-15

Question

Ich habe ein Puzzle 15 für Menschen online konkurrieren implementiert. Mein aktueller Randomizer arbeitet mit der guten Konfiguration und bewegt die Kacheln für 100 Züge (beliebige Zahl)

Alles ist in Ordnung, aber in kurzer Zeit werden die Kacheln zu einfach gemischt und es dauert nur ein paar Züge löse das Puzzle, daher ist das Spiel für einige Leute sehr unfair, wenn sie bessere Punktzahlen in einer viel höheren Geschwindigkeit erreichen.

Was wäre ein guter Weg, um die anfängliche Konfiguration zu randomisieren, so dass es nicht "zu einfach" ist?

Answer 1

Sie können eine völlig zufällige Konfiguration erstellen (das ist lösbar) und dann einen Solver verwenden, um die optimale Sequenz von Zügen zu bestimmen. Wenn die Sequenz lang genug für Sie ist, gut, sonst erzeugen Sie eine neue Konfiguration und wiederholen sich.

aktualisiert & Details

Es gibt eine article auf Wikipedia über das 15-Puzzle und wenn es (und ist nicht) auflösbar. Kurz gesagt, wenn sich das leere Quadrat in der unteren rechten Ecke befindet, dann ist das Puzzle genau dann lösbar, wenn die Anzahl der Inversionen (eine Inversion ist ein Tausch zweier Elemente in der Sequenz, nicht notwendigerweise benachbarter Elemente) in Bezug auf die Zielpermutation ist gleichmäßig.

Sie können dann leicht einen lösbaren Startzustand erzeugen, indem Sie eine gerade Anzahl von Inversionen durchführen, was zu einem nicht so leicht zu lösenden Zustand führt, viel schneller als bei normalen Bewegungen, und das ist garantiert bleibt lösbar.

Tatsächlich brauchen Sie keinen Suchalgorithmus wie oben erwähnt, sondern eine zulässige Heuristik. Solch ein immer unterschätzt überschätzt nie die Anzahl der Züge benötigt, um das Rätsel zu lösen, d. H. Sie sind garantiert, dass es weniger Züge braucht, die die Heuristik Ihnen sagt.

Eine gute Heuristik ist die Summe der Manhattan-Abstände jeder Zahl zu ihrer Zielposition.

Zusammenfassung

Kurz gesagt, ein möglicher (sehr einfach) Algorithmus für die Startpositionen zu erzeugen könnte wie folgt aussehen:

1: current_state <- goal_state 
2: swap two arbitrary (randomly selected) pieces 
3: swap two arbitrary (randomly selected) pieces again (to ensure solvability) 
4: h <- heuristic(current_state) 
5: if h > desired threshold 
6:  return current_state 
7: else 
8: go to 2. 

Um absolut sicher zu sein, wie schwierig ein Zustand ist, was Sie brauchen mit einem Solver die optimale Lösung zu finden. Heuristiken geben Ihnen nur eine Schätzung.

Answer 2

ich tun würde, um diesen

1. Start aus der Lösung (wie du getan hast)

2. gültig wiederum in zufälliger Richtung macht

   so müssen Sie den Überblick behalten, wo die Lücke und generieren zufällige Richtung (N,E,S,W) und machen Sie den Umzug. Ich denke dieser Teil hast du auch gemacht.

3. berechnen die Zufälligkeit Ihrer Placements

   So einige Koeffizienten abhängig berechnen in der Größenordnung des Arrays. So geordnete (gelöste) Lösungen haben niedrige Werte und Zufallswerte haben hohe Werte. Die Gleichung für den Koeffizienten ist jedoch eine Frage von Versuch und Irrtum. Hier einige Ideen, was zu verwenden:

   • correlation coefficient

   • Summe der durchschnittlichen Differenz von Wert und seine Nachbarn

     1 2 4 
     3 6 5 
     9 8 7 
     
     coeff(6)= (|6-3|+|6-5|+|6-2|+|6-8|)/4 
     coeff=coeff(1)+coeff(2)+...coeff(15) 
     

   • abs Entfernung von geordneten Anordnung

   Sie kombinieren mehr nähert sich zusammen. Sie können dies in getrennte Zeilen und Spalten aufteilen und die Unterkoeffizienten dann miteinander kombinieren.

4. Schleife # 2 -Einheit Koeffizient von # 3 ist hoch genug (treshold)

   Die treshold auch die Schwierigkeit ändern verwendet werden kann.