Matroids Matheplanet Forum Index
Moderiert von Cousinchen
Matroids Matheplanet Forum Index » Spiel & Spaß » Drehtorus-Spiel
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Drehtorus-Spiel
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1510
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-07-21


Für das Android-Betriebssystem gibt es eine Spiel-App die sich "Rubies" nennt, doch sagt dieser Werbungsname rein gar nichts über das Spiel aus. Es geht um einen quadratischen Torus mit \(n\times n\) Feldern, bei dem je \(n\) beliebige Felder immer dieselbe Farbe haben, und dessen Zeilen und Spalten sich rundqum drehen lassen.  Aus Sicht des Betrachters entstehen so \((n^2)!\big/(n!)^{n+1}\) verschiedene Stellungen, welche durch Drehungen so geqordnet werden sollen, dass die Felder jeder Farbe Ringe um den Torus bilden.

Beispiel:\[
\matrix{1&2&2 \\ 2&3&1 \\ 3&1&3} \quad\rightarrow\quad
\matrix{1&1&2 \\ 2&2&1 \\ 3&3&3} \quad\rightarrow\quad
\matrix{1&1&2 \\ 1&2&2 \\ 3&3&3} \quad\rightarrow\quad
\\ \quad\rightarrow\quad
\matrix{1&1&3 \\ 1&2&2 \\ 3&3&2} \quad\rightarrow\quad
\matrix{1&1&3 \\ 2&2&1 \\ 3&3&2} \quad\rightarrow\quad
\matrix{1&1&1 \\ 2&2&2 \\ 3&3&3}
\]

Der Fall \(n=3\)  mit 280 Konfigurationen ist für unsere Zwecke bereits schwierig genug. Ich frage mich:
(a)
Gibt es eine schnelle (dh polynomialbeschränkte) Art herauszufinden, wieviele Drehungen benötigt werden, um von einer vorgegebenen Stellung aus zum Ziel zu kommen?
(b)
Welches ist die maximale Anzahl der benötigten Drehungen für eine beliebige (nicht vorgegebene) Stellung bei vorgegebenen \(n\)?

Die Spiel-App gibt offizielle Auflösungen an, aber diese sind (überprüfterweise) nicht immer die schnellsten. Für \(n=3\) geht es anscheinend immer in 5 Zügen.


NACHTRAG:
Permutierte Stellungen wie
\[\matrix{2&2&2 \\ 1&1&1 \\ 3&3&3}, \qquad
\matrix{3&1&2 \\ 3&1&2 \\ 3&1&2}\] gelten für die Spiel-App ebenfalls als aufgelöst.


-----------------
/Kyristo meu kimgei kom nhi cumgen ta Gendmogen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 27482
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-07-22

\(\begingroup\)\(\newcommand\d{\mathop{}\!\mathrm{d}}\)
Ja, es sind bei 3×3 immer max. 5 Züge, um eine der beiden möglichen Endpositionen zu erreichen:

1 1 1          1 2 3
2 2 2   oder   1 2 3
3 3 3          1 2 3

Es sind 137 Anfangspositionen, für die tatsächlich 5 Züge nötig sind.

Läßt man nur eine der Endpositionen zu (z.B. die linke), dann sind im Extremfall 6 Züge nötig.

Ich weiß allerdings nicht, wo du die 280 Konfigurationen her hast. Laut meinem Programm sind es 1680 😲!
Und nach meiner Rechnung auch:
$$\frac{9!}{(3!)^3}=1680$$
Ohweh, bei 4×4 sind es
$$\frac{(4 \cdot 4)!}{(4!)^4}=63063000$$ Konfigurationen 😮
Da ist mein Programm wohl noch eine Weile beschäftigt…

Übrigens muß der Torus nicht unbedingt quadratisch sein. Die Anzahl der Farben und deren Häufigkeit bestimmen die Größe. Allerdings ist dann bei einem $n \times m$ Torus auch nur eine Anordnung der Farben möglich, z.B. bei 3 Farben jede 5×:

1 1 1 1 1
2 2 2 2 2
3 3 3 3 3

Gruß vom ¼


-----------------
Bild
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3630
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2020-07-22


Das ist eine schöne Sache!

Es wäre ein 5x5 Feld mit 25 "Teilen" und 10 "Drehringen" vergleichbar mit dem Rubik's mit 26 Teilwürfeln und 9 drehbaren Ringen...

Gibt es überhaupt schon eine Algorithmus, wie man das lösen kann, unabhängig davon, wie viele Züge man braucht?

Grüße aus dem Harz und frohes Knobeln
Gerhard/Gonz


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1510
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2020-07-22

\(\begingroup\)\(\newcommand\d{\mathop{}\!\mathrm{d}} \newcommand\d{\mathop{}\!\mathrm{d}}\)
2020-07-22 03:40 - viertel in Beitrag No. 1 schreibt:
Ich weiß allerdings nicht, wo du die 280 Konfigurationen her hast. Laut meinem Programm sind es 1680 😲!
Und nach meiner Rechnung auch:
\(\frac{9!}{(3!)^3}=1680\)

\(280\cdot3!=1680\).
Ich bin (wie auch die Spiel-App) davon ausgegangen, dass eine Permutation der Farben irrelevant ist.

Wenn wir nur nach der Mindestqanzahl Züge suchen, die für eine beliebige Stellung benötigt werden, dann ist die Permutation der Farben ja wirklich irrelevant. Wenn wir die benötigte Zuganzahl für eine vorgegebene Stellung suchen, dann ist das freilich nicht mehr so.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3630
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-07-22


Wir hatten übrigens mal das Problem mit den "Kugeln auf drei Ringen", das sich verallgemeinert genauso liest: die Kugeln liegen jeweils auf den Schnittstellen der Ringe und können auf diesen gedreht werden:

LinkKreisdrehpuzzle mathematisch lösen?


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3630
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-07-22


Das folgende passt zu dem Beitrag von viertel aus Beitrag 1, ich habe mir nur erst einmal einen "menschen-merkbaren" Algorithmus überlegt und dessen maximale Zugzahl bestimmt, einfach um ein bisschen mit dem Problem "zu spielen".

Es einen recht einfachen Algorithmus (der sicher nicht optimal ist, aber
gut merkbar):

Man sortiert spaltenweise (zeilenweise geht natürlich genauso). Es gibt damit "fertige" Spalten, und eine, die in Arbeit ist. Die als nächste anzugehende Spalte kann frei gewählt werden.

Nun geht man die in der aktuell behandelten Spalte "fehlbesetzten" Positionen der Reihe nach an. Man sucht sich ein Feld in der passenden Farbe im unsortierten Bereich, das nicht in der Zeile des Fehlfeldes liegt (gibt es das nicht, so dreht man eine Spalte, in der sich ein passendes Feld befindet, um das neu einzugliedernde Feld aus der betreffenden Zeile herauszubekommen). Man dreht jetzt die Zeile, in der das Fehlfeld liegt, soweit, dass es in der Spalte des neu einzupassenden Elementes liegt. Dann wird die Spalte, in der das Fehlfeld und das neue Feld nun liegt, so gedreht, dass das neue Element anstelle des Fehlfeldes in dessen Zeile zu liegen kommt. Diese Zeile wird damit nur an der einen Stelle verändert, und kann nachfolgend wieder in die Ausgangsstellung zurückgedreht werden. Damit ist ein weiteres Feld eingepflegt und es geht weiter mit der nächsten Fehlstellung in der aktuellen Spalte, oder, falls diese damit "erledigt" ist, wird die nächste Spalte in Arbeit genommen.

Für das 3x3 Feld ergibt sich folgendes:

Man findet (bis auf eine Belegung, die man besonders behandeln könnte), immer zwei Elemente gleicher Farbe, die schon benachbart liegen. Mit diesen beginnen wir, und wissen dabei gleich, ob wir nach Spalte oder Zeile sortieren.

Das verbleibende Feld kann man in zwei Zügen richtigstellen, da man das "Herausdrehen" bei bisher keiner fertig sortierten Zeile/Spalte nicht braucht.

Nun geht es an die zwei verbleibenden Zeilen/Spalten. Da sich nur noch zwei Farben auf die verbleibenden 2x3 Felder verteilen, muss es jetzt eine Spalte/Zeile geben, in der nur noch ein Fehlfeld verblieben ist. Dieses muss nun korrigiert werden, indem man obigen Algorithmus verwendet. Das geht in maximal vier Zügen.

Und damit ist auch fertig sortiert, da es bei 3x3 reicht, zwei Zeilen/Spalten vollständig zu sortieren.

Damit wären wir bei max. 6 Drehungen (ob eine Drehung nur um jeweils ein Element erfolgt, oder auch Anweisungen wie "die zweite Spalte um zwei Felder nach unten" als eine "Drehung" zählen, erhebt sich hier nicht, da man ja dann andersherum drehen könnte).

Soweit :)

Ich bin gespannt, ob wir Algorithmen finden können, die jeweils die optimale Lösung finden, ohne alles durchprobieren zu müssen.

Grüße
Gerhard/Gonz


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1510
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, vom Themenstarter, eingetragen 2020-07-22

\(\begingroup\)\(\newcommand\d{\mathop{}\!\mathrm{d}} \newcommand\d{\mathop{}\!\mathrm{d}}\)
2020-07-22 14:43 - gonz in Beitrag No. 5 schreibt:
Das folgende passt zu dem Beitrag von viertel aus Beitrag 1, ich habe mir nur erst einmal einen "menschen-merkbaren" Algorithmus überlegt und dessen maximale Zugzahl bestimmt, einfach um ein bisschen mit dem Problem "zu spielen".
[...]
Und damit ist auch fertig sortiert, da es bei 3x3 reicht, zwei Zeilen/Spalten vollständig zu sortieren.
Damit wären wir bei max. 6 Drehungen.

... vorausgesetzt, dass uns die Reihenfolge der Farben egal ist (für viertel ist sie anscheinend nicht egal). Aber natürlich gibt es auch für jenen Fall einen "menschen-merkbaren" Algorithmus 😃.)


2020-07-22 03:40 - viertel in Beitrag No. 1 schreibt:
Ohweh, bei 4×4 sind es
$$\frac{(4 \cdot 4)!}{(4!)^4}=63\,063\,000$$ Konfigurationen
Da ist mein Programm wohl noch eine Weile beschäftigt…

Wenn du Farbpermutationen ignorierst und umgestellte Positionen für Farbe 1 getrennt betrachtest (es gibt 10 davon), dann kommst du auf
\[10\cdot \frac{(3\cdot4)!}{(4!)^3\,3!} = 57\,750\qquad
\text{(nachträglich berichtigt)}\] Stellungen, was dein Rechner vermutlich noch bewältigt.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 27482
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-07-22


Ok, es gibt 12 Endkonfigurationen:
 1 2 3  1 1 1  1 3 2  1 1 1  2 1 3  2 2 2  2 3 1  2 2 2  3 1 2  3 3 3  3 2 1  3 3 3 
 1 2 3  2 2 2  1 3 2  3 3 3  2 1 3  1 1 1  2 3 1  3 3 3  3 1 2  1 1 1  3 2 1  2 2 2 
 1 2 3  3 3 3  1 3 2  2 2 2  2 1 3  3 3 3  2 3 1  1 1 1  3 1 2  2 2 2  3 2 1  1 1 1 
Aber dennoch 1680 Konfigurationen insgesamt.

Und mit diesen 12 Endkonfigurationen reduziert sich die maximale Zugzahl auf  4(!).
Das Beispiel im TS ist damit sogar in 3 Zügen lösbar:
  1 2 2 → 1 2 2 → 1 2 3 → 1 2 3  
  2 3 1   1 2 3   1 2 3   1 2 3  
  3 1 3   3 1 3   3 1 2   1 2 3  

Ein Beispiel für einen 4-züger (es gibt deren immerhin 108) ist (auch wenn die Ausgangsstellung einfach aussieht, ist doch „fast“ fertig😁)
  2 1 3 → 1 1 3 → 1 3 1 → 2 3 1 → 1 2 3  
  1 2 3   1 2 3   1 2 3   1 2 3   1 2 3  
  1 2 3   2 2 3   2 2 3   1 2 3   1 2 3  


[Die Antwort wurde nach Beitrag No.3 begonnen.]



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 27482
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2020-07-22

\(\begingroup\)\(\newcommand\d{\mathop{}\!\mathrm{d}}\)
2020-07-22 17:53 - Goswin in Beitrag No. 6 schreibt:
Wenn du Farbpermutationen ignorierst und umgestellte Positionen für Farbe 1 getrennt betrachtest (es gibt 9 davon), dann kommst du auf
$$9\cdot \frac{(3\cdot4)!}{(3!)^3\,4!} =831\,600$$ Stellungen, was dein Rechner vermutlich noch bewältigt.
Verstehe ich nicht🙁

Es sind 16 Felder zu besetzen ($16!$ Möglichkeiten), mit 4 Farben zu jeweils 4 Steinen (die nicht unterscheidbar sind).
Und das sind dann nun mal
$$\frac{16!}{4! \cdot 4! \cdot 4! \cdot 4!}=63063000 \quad \text{Konfigurationen}$$ Von jeder gilt es, zu versuchen, eine der
$$2 \cdot 4!=48 \quad \text{Endkonfigurationen}$$ zu erreichen. Beim 3×3 Feld sind es $2 \cdot 3!=12$ Endkonfigurationen.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1510
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2020-07-22

\(\begingroup\)\(\newcommand\d{\mathop{}\!\mathrm{d}}\)
2020-07-22 18:50 - viertel in Beitrag No. 7 schreibt:
Es gibt 12 Endkonfigurationen:
 1 2 3  1 1 1  1 3 2  1 1 1  2 1 3  2 2 2  2 3 1  2 2 2  3 1 2  3 3 3  3 2 1  3 3 3 
 1 2 3  2 2 2  1 3 2  3 3 3  2 1 3  1 1 1  2 3 1  3 3 3  3 1 2  1 1 1  3 2 1  2 2 2 
 1 2 3  3 3 3  1 3 2  2 2 2  2 1 3  3 3 3  2 3 1  1 1 1  3 1 2  2 2 2  3 2 1  1 1 1 
Aber dennoch 1680 Konfigurationen insgesamt.

Einverstanden. Ich versuchte nur, dem Rechner die Suche etwas zu erleichtern, aber das Ergebnis sollte immer dasselbe sein. Dabei geht es mir erst einmal um die Mindestqanzahl der Züge, mit denen ich immer eine der Endstellungen erreichen kann. Wenn ich Stellungen wiederholt untersuche, ändert das nichts an der Mindestqanzahl der Züge, (Über die Anzahl der Stellungen, die eine vorgegebene Anzahl Züge benötigen, sage ich vorqerst gar nichts, um die Sache einfach zu halten)

Bei der Formel \((n^2)!\big/(n!)^n\) werden Stellungen wie
\[
\matrix{1&1&2 \\ 2&3&1 \\ 3&3&2} \qquad
\matrix{2&2&1 \\ 1&3&2 \\ 3&3&1}
\] als verschieden gezählt. Aber das sind sie für unsere Zwecke ja nicht wirklich: wenn ich Farbe_1 und Farbe_2 vertausche, wird die Endstellung in genau der gleichen Zugqanzahl erreicht. Das war der Grund für mich, noch einmal durch \(3!\) zu teilen. Es kann natürlich durchaus angebracht sein, diese Verqeinfachung zu ignorieren, weil sie die Codierung übermäßig erschwert.

Bei der weiteren Verqeinfachung für \(n=4\) enthielt meine Formel freilich eine (nun berichtigte) Zahlenverdrehung: ursprünglich hätte es
$$9\cdot \frac{(3\cdot4)!}{(4!)^3\,3!} = 51\,975$$ heißen müssen, und bei der nun empfohlenen einfacheren Codierung einfach
$$9\cdot \frac{(3\cdot4)!}{(4!)^3} = 311\,850$$ Wenn ich für \(n=4\) Farbe_1 auf alle mögliche Positionen verteile, wobei ich Zeilenpermutationen, Spaltenpermutationen und Transpositionen als gleich ansehe, dann erhalte ich folgende 9_Fälle:

\[
\matrix{1&1&1&1 \\ .&.&.&. \\ .&.&.&. \\ .&.&.&.} \qquad
\matrix{1&1&1&. \\ 1&.&.&. \\ .&.&.&. \\ .&.&.&.} \qquad
\matrix{1&1&1&. \\ .&.&.&1 \\ .&.&.&. \\ .&.&.&.} \qquad
\\[36pt]
\matrix{1&1&.&. \\ 1&1&.&. \\ .&.&.&. \\ .&.&.&.} \qquad
\matrix{1&1&.&. \\ 1&.&1&. \\ .&.&.&. \\ .&.&.&.} \qquad
\matrix{1&1&.&. \\ .&.&1&1 \\ .&.&.&. \\ .&.&.&.} \qquad
\\[36pt]
\matrix{1&1&.&. \\ 1&.&.&. \\ .&.&1&. \\ .&.&.&.} \qquad
\matrix{1&1&.&. \\ .&.&1&. \\ .&.&.&1 \\ .&.&.&.} \qquad
\matrix{1&.&.&. \\ .&1&.&. \\ .&.&1&. \\ .&.&.&1} \qquad
\]
(O weh, ich habe mindestens einen übersehen ...)
Für jeden dieser 9_Fälle habe muss nun die restlichen \(3\cdot4=12\) Felder mit den Farben 2,3,4 füllen, und dafür gibt es insgesamt \(9\cdot12!\big/(4!)^3\) Möglichkeiten.
\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 27482
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2020-07-22


Und ich gehe das Ganze rückwärts an.

Ausgehend von den Endstellungen (12 bzw 48) baue ich die Liste auf, welche Stellungen von dort zu erreichen sind (Breitensuche).
Irgendwann treffe ich dabei auf die Ausgangsstellung und muß nun den Weg zum Zielknoten zurück gehen.

Damit kann ich auch einen Weg von jeder Stellung zu jeder anderen finden, indem ich nur eine der beiden als Endstellung vorgebe und mich bis zur anderen durcharbeite.

Da ich nicht weiß, zu welcher Endstellung der kürzeste Weg führt, muß ich den ganzen Baum (eigentlich sind es ja 12 bzw 48 Bäume) aufbauen.

Beginne ich mit der Startstellung, muß ich mich auch mit Breitensuche „durchfressen“, bis ich auf eine der Endstellungen treffe. Und ich vermute, daß ich dabei im dümmsten Fall (welche Startstellung wäre das?) auch die 63MB Stellungen abklappern muß, um bei einem der letzten Blätter einen Treffer zu haben.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3630
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2020-07-23


Wie wollen wir zählen? Wenn man auf dem 4x4 Torus zB die zweite Spalte um zwei Felder nach unten dreht - ist das ein Zug oder sind das zwei Züge?


-----------------
Heute: Keine Signatur.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 27482
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2020-07-24


Das kann eigentlich jeder halten, wie er will. Es sollte nur dabei stehen, wie gezählt wird.
Wenn „2× rechts“ als ein Zug gezählt wird, dann kann man es ja leicht umrechnen, wenn die Zugfolge angegeben ist.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1510
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, vom Themenstarter, eingetragen 2020-07-24


2020-07-23 19:43 - gonz in Beitrag No. 11 schreibt:
Wie wollen wir zählen? Wenn man auf dem 4x4 Torus zB die zweite Spalte um zwei Felder nach unten dreht - ist das ein Zug oder sind das zwei Züge?

In der Spiel-App wird das als ein einziger Zug gezählt. Man kann sogar eine Spalte beliebig viele Male hinterqeinqander hin oder herbewegen, ohne dass mehr als ein einziger Punktqabzug erfolgt. (Sehr praktisch, weil man beim Drag-and-Drop öfters zu früh oder zu spät loslässt)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Kitaktus
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 11.09.2008
Mitteilungen: 6572
Aus: Niedersachsen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2020-07-25


@Goswin:
In #9 vermisse ich soetwas wie
1 1 0 0
0 0 1 0
0 0 1 0
0 0 0 0



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1510
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, vom Themenstarter, eingetragen 2020-07-27


Dank Kitaktus berichtige ich meine obige Untersuchung.
Wenn ich für \(n=4\) Farbe 1 auf alle mögliche Positionen verteile, wobei ich Zeilenpermutationen, Spaltenpermutationen und Transpositionen als gleich ansehe, dann erhalte ich folgende 10 Fälle:

\[
\matrix{1&1&1&1 \\ .&.&.&. \\ .&.&.&. \\ .&.&.&.} \qquad
\matrix{1&1&1&. \\ 1&.&.&. \\ .&.&.&. \\ .&.&.&.} \qquad
\matrix{1&1&1&. \\ .&.&.&1 \\ .&.&.&. \\ .&.&.&.} \qquad
\\[36pt]
\matrix{1&1&.&. \\ 1&1&.&. \\ .&.&.&. \\ .&.&.&.} \qquad
\matrix{1&1&.&. \\ 1&.&1&. \\ .&.&.&. \\ .&.&.&.} \qquad
\matrix{1&1&.&. \\ 1&.&.&. \\ .&.&1&. \\ .&.&.&.} \qquad
\\[36pt]
\matrix{1&1&.&. \\ .&.&1&1 \\ .&.&.&. \\ .&.&.&.} \qquad
\matrix{1&1&.&. \\ .&.&1&. \\ .&.&1&. \\ .&.&.&.} \qquad
\matrix{1&1&.&. \\ .&.&1&. \\ .&.&.&1 \\ .&.&.&.} \qquad
\matrix{1&.&.&. \\ .&1&.&. \\ .&.&1&. \\ .&.&.&1} \qquad
\]
Für jeden dieser 10 Fälle habe muss nun die restlichen \(3\cdot4=12\) Felder mit den Farben 2,3,4 füllen, und dafür gibt es insgesamt \(~10\cdot12!\big/(4!)^3 ~=~ 346\,500~\) Möglichkeiten.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 18.09.2008
Mitteilungen: 1510
Aus: Chile, Ulm
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, vom Themenstarter, eingetragen 2020-07-28


Satz:
Es sei ein \(m\times n\)-Torus mit den Einträgen \(0,1,\ldots,mn-1\) an beliebigen Orten. Dann lassen sich diese Einträge mittels Torusdrehungen der Spalten und Zeilen genau dann für jede Stellung in die natürliche Reihenfolge\[
\matrix{
0      &1       &2       &\ldots & n-1   \\
n      &n+1     &n+2     &\ldots &2n-1   \\
\vdots &\vdots  &\vdots  &\ddots &\vdots \\
(m-1)n &(m-1)n+1&(m-1)n+2&\ldots &mn-1   }
\]bringen, wenn \(mn\) gerade ist.

Beweisschema:
Die ungeqordneten Zahlenqeinträge seien zeilenweise hinterqeinander aufgelistet, und definieren so eine Umstellung, die gerade oder ungerade sein kann. Zeilendrehungen im Torus definieren gerade Umstellungen, wenn \(n\) ungerade ist, und ungerade Umstellungen, wenn \(n\) gerade ist; bei Spaltendrehungen verhalten sich bezüglich \(m\) analog.
Wenn nun \(mn\) ungerade ist, dann können Torusdrehungen keine ungeraden Umstellungen der Eintragsliste erzeugen, und die Hälfte der möglichen Stellungen ist nicht lösbar. Wenn hingegen \(mn\) gerade ist, genügt es zu zeigen, dass die Umstellungen \(\pi\!\cdot\!(0,1)\longrightarrow\pi\!\cdot\!(1,0)\) und \(\pi\!\cdot\!(0,n)\longrightarrow\pi\!\cdot\!(n,0)\) immer zu erreichen sind. Wenn wir ohne Allgemeinheitsverlust \(m\) gerade ansetzen, geht das (Zählfehler vorbehalten) mit maximal \(4m+2\) Torusdrehungen. \(~\square\)


Ich schlage vor, die Suche nach einer Gesamtqordung unterschiedlicher Einträge strenges Drehtorusspiel zu nennen (Oder klingt Torusdrehspiel besser?). Das strenge Drehtoruspiel mit geradem \(mn\) ließe sich sehr schön als Bildpuzzle umsetzen; ich kenne freilich keine solche Implementierung.

Da die Anzahl der Startstellungen für das strenge Drehtorusspiel mit \((m\!\cdot\!n)!\) doch recht hoch ist (wir haben \((3\!\cdot\!4)!=479\,001\,600\)), wären wir da wohl gezwungen, uns auf den Fall \(3\times4\) zu konzentrieren. Welche Startstellungen können wir wegrationalisieren, weil sie gleich viele Drehungen benötigen als andere, um zur Grundstellung zu gelangen?



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Goswin hat die Antworten auf ihre/seine Frage gesehen.
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2020 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]