Permutation Puzzle Swap Cubies

Question

Ich habe kürzlich ein Online-Puzzle RAVEL gestartet . Es ist eine 3D-Anordnung von Würfeln, die in Farbreihenfolge angeordnet werden müssen. Ein legaler Schritt besteht darin, eine Zeile, Spalte oder Spur mit einer beliebigen Anzahl von Leerzeichen zu verschieben. Die Würfel, die am Ende herausgeschoben werden, werden am anderen Ende eingesetzt.

Ich schlage vor, dass Sie RAVEL besuchen , auf die Registerkarte "Experimentator" klicken und einige RAVELs in verschiedenen Dimensionen ausprobieren, damit Sie das Folgende besser verstehen.

Ich vermute, dass alle Permutationen lösbar sind, aber weil ich es nicht genau weiß, mische ich das RAVEL mit einer Reihe von zufälligen legalen Bewegungen.

Frage eins:

Ist es notwendig, mit legalen Schritten zu mischen? Oder könnte ich es einfach mit zufälligen Swaps mischen und es noch lösbar haben? Anders ausgedrückt: Ist die Vermutung wahr, sind alle Permutationen lösbar?

Meine zweite Frage hat mit Lösungstechniken zu tun. Ich löse RAVELs Schicht für Schicht mit Ad-hoc-Methoden, um Cubies an ihren Platz zu bringen, ohne die Positionen bereits platzierter Cubies zu verändern. Aber in der letzten Ebene verwende ich formalisierte Methoden für die letzten Cubies.

Der Zyklus 3-Algorithmus

Dieser Algorithmus zyklisiert die Positionen von drei Cubies und lässt alle anderen Cubies an Ort und Stelle. Der Abstand zwischen den drei Würfeln spielt keine Rolle, solange sie einen rechten Winkel bilden: Würfel 1 und 2 in derselben Zeile, Würfel 2 und 3 in derselben Spalte.

Der Algorithmus:

• Ziehen Sie den grünen Würfel an die Spitze (blaue Position).
• Ziehen Sie den roten an die Scheitelposition.
• Ziehen Sie den Scheitelpunkt an die Stelle, an der Grün begonnen hat.
• Ziehen Sie den Scheitelpunkt an die Stelle, an der Rot begonnen hat.

Die Zahlen im Bild zeigen die Reihenfolge der Bewegungen. Um in die entgegengesetzte Richtung zu fahren, schalten Sie 1 mit 2 und 3 mit 4.

Tauschen Sie zwei Cubies

Oft können Sie das RAVEL nur mit den oben beschriebenen Verfahren lösen. Aber manchmal bleiben Paare von getauschten Würfeln übrig. Ich kenne keinen allgemeinen Algorithmus zum Austauschen von Paaren, der für alle Größen von RAVEL funktioniert. Ich habe es geschafft, einige Beispiele zu lösen, indem ich einfach weggeschleudert und alles versucht habe.

Ich habe ein Verfahren gefunden, um einen Paartausch bei RAVELs durchzuführen, bei dem eine der Dimensionen gleich 4 ist.

Das Bild zeigt die Abfolge der Bewegungen zum Vertauschen der roten und grünen Würfel. Die vertikale Abmessung muss vier betragen.

Frage zwei:

Können Sie einen Pair-Swap-Algorithmus erstellen, der für RAVELs aller Größen funktioniert?

☺ ☺ ☺

Answer 1

Dieses Puzzle ist eine 3D-Version eines Puzzles, das in Simon Tathams Puzzlesammlung unter dem Namen Sixteen erhältlich ist . Dieses Rätsel wurde hier bereits besprochen: Techniken zum Lösen von Zeilen-Spalten-Gleiträtseln

Die Antwort dort gilt auch hier, daher werde ich nicht ins Detail gehen.

Frage 1:

Jede Permutation mit gleichmäßiger Parität ist möglich und mit den 3-Zyklen leicht lösbar. Wenn alle Dimensionen ungerade sind, ist jede Bewegung eine gerade Permutation, sodass keine ungeraden Permutationen möglich sind. Insbesondere ist in diesem Fall kein einzelner Swap möglich. Wenn mindestens eine Dimension gerade ist, sind auch ungerade Permutationen verfügbar, sodass alle Permutationen lösbar sind.

Frage 2:

Wenn eine oder mehrere Dimensionen gerade sind, ist eine Verschiebung entlang einer solchen Dimension eine ungerade Permutation. Daher können Sie eine solche Verschiebung durchführen und die meisten verschobenen Teile mit 3 Zyklen lösen und einen einzigen Tausch erhalten.
Angenommen, A ist eine Bewegung, die eine Zeile mit verschiebt$2n$ Blöcke, B ist eine Verschiebung einer sich kreuzenden Linie von Blöcken, und B 'ist die Umkehrung von B. Dann wird die Bewegungssequenz BAB'A wiederholt $n-1$ Zeiten, gefolgt von BAAB'A, bewirken den Austausch von zwei benachbarten Blöcken in der A-Linie.