Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Kreisdrehpuzzle mathematisch lösen?
Druckversion
Druckversion
Autor
Universität/Hochschule J Kreisdrehpuzzle mathematisch lösen?
jjzun
Junior Letzter Besuch: im letzten Monat
Dabei seit: 20.07.2019
Mitteilungen: 14
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2020-05-21


Hallo,
ich habe mal eine etwas andere Frage, die mir im Kopf herumgeistert.
Und zwar habe ich in den Semesterferien folgendes Drehrätsel lösen wollen:



Es geht darum, die drei Kreisscheiben so zu drehen, dass folgende Konfiguration herauskommt:



Ich habe es zwar nach 10min durch herumprobieren gelöst, frage mich aber, ob man es nicht mit mathematischen Methoden "erschlagen" könnte.
(Teilweise aus Interesse und z.B. für den Fall, dass mir nocheinmal so ein "fieses" Rätsel begegnet.)

Da ich mathematisch noch ganz am Anfang stehe, wollte ich fragen, in welcher Weise man dieses Rätsel (am Besten lösbar) darstellen könnte?

Oder besitzt es gar keine leicht zu berechnende Lösung?

Meine bisherigen Ideen:

- als Gruppe darstellen, mit Drehoperationen für die Kreise
Problem: ich habe noch keine Kenntnisse in der Gruppentheorie

- als Graphen darstellen, in dem wir eine Permutation der Knoten suchen.

Diese Permutation muss als Verkettung der Drehungen der Kreise (Automorphismen der C_6 Teilgraphen) darstellbar sein.

Auch muss sie jeden grünen Knoten auf einen Schnittpunkt von jeweils zwei der drei Kreise abbilden. (Also ein Element des Schnittes der Knotenmengen von je zwei der C_6 Teilgraphen)

Problem: Ich kenne kein Vorgehen, welches solch eine Lösung berechenbar macht.
Wikipedia war beim Thema Automorphismen leider auch nicht sehr hilfreich, bezüglich eines Algorithmus. (Ist in NP, vllt. sogar NP-vollständig...)

Vielleicht hat ja jemand von Euch eine Idee?

Viele Grüße,
jjzun



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: 27369
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2020-05-22

\(\begingroup\)\(\newcommand\d{\mathop{}\!\mathrm{d}}\)
Hi jjzum

Von den 12 Positionen sind 6 grün, also gibt es $\binom{12}{6}=924$ Konstellationen. Jede kannst du mit einer 12-bit Kombination darstellen ($2^{12}=4096$, aber du brauchst ja nur die mit genau 6 1en).
Bilde den kompletten Nachfolger-Graphen und suche den Weg von deiner Ausgangsposition zur Zielposition.

Gruß vom ¼


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


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6005
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, eingetragen 2020-05-22


Hallo jjzun,

2020-05-21 21:05 - jjzun im Themenstart schreibt:
Problem: Ich kenne kein Vorgehen, welches solch eine Lösung berechenbar macht.
Wikipedia war beim Thema Automorphismen leider auch nicht sehr hilfreich, bezüglich eines Algorithmus. (Ist in NP, vllt. sogar NP-vollständig...)

Die Frage nach NP bzw. NP-vollständig stellt sich hier nicht, das es sich um ein einziges Problem und keine Klasse von Problemen handelt.

viertel hat ja schon einen Ansatz gegeben. Allerding kann ich mir nicht vorstellen, dass man das so einfach zu Fuß ausrechnen kann. Deshalb meine Frage: Kannst du programmieren, vorzugsweise in C?



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: 3531
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, eingetragen 2020-05-22


ich bekam gerade den Tipp "das ist doch wie Rubik's Cube in 2D", und tatsächlich kann man sich einfache "Drehungensfolgen" ausgucken, die möglichst viele der Elemente festhalten, und nur einige wenige Positionen vertauschen. Aus diesen lässt sich dann ein "Rezept" zusammenbauen, wie man sie nacheinander anwedet, um zum Ziel zu kommen. Diese Folgen liessen sich dann denke ich memorieren. Das ist an sich schon so ein bissl in Richtung Gruppentheorie, aber im Grunde braucht man dazu keine Gruppentheorie, sondern kann es auch so beschreiben.

Zum Beispiel: Nimmt man zwei Ringe A und B, und führt dann die Folge der Einzeldrehungen A/rechts, B/rechts, A/links, B/links durch, dann landen nach den Drehungen von 12 Kugeln derer 6 wieder an der Stelle, wo sie hergekommen sind, und die restleichen teilen sich auf zwei Dreierzyklen auf, die um ein Feld rotiert werden.

Ich nehme mal an, dass man damit insgesamt zum Ziel kommt (habe aber weder etwas ausgearbeitet, noch die sicher hilfreichen Zeichnungen erstellt). Vielleicht könnte man auf der Basis etwas erstellen.

(Ein Programm, dass das Problem mit Brute force löst, wäre dann ggf. eine gute Kontrolle bzw. könnte auch "schnellste Lösungen" finden etc.

Grüße aus dem Harz
Gerhard/Gonz  



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6005
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2020-05-22


2020-05-22 16:07 - gonz in Beitrag No. 3 schreibt:
Ein Programm, dass das Problem mit Brute force löst, wäre dann ggf. eine gute Kontrolle bzw. könnte auch "schnellste Lösungen" finden etc.

Mit einem Programm lösen heißt ja nicht "Brute Force".

Gruß
StrgAltEntf



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: 3531
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, eingetragen 2020-05-22


stimmt :)



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: 3531
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2020-05-23


Hallo jjzun,

Sagst du uns vielleicht aus welchem Spiel das ist? Und ich finde es spannend, wie man es bedient - vielleicht gibt es sogar irgendwo ein "let's play" oder so dazu?

Im Gegenzug plauden wir gerne dann mal ein bissl über die Datenstruktur, und mögliche Algorithmen :)

G.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6005
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, eingetragen 2020-05-23


2020-05-23 08:54 - gonz in Beitrag No. 6 schreibt:
Sagst du uns vielleicht aus welchem Spiel das ist? Und ich finde es spannend, wie man es bedient - vielleicht gibt es sogar irgendwo ein "let's play" oder so dazu?

Hallo Gonz,
das Puzzle scheint Teil des Adventures Machinarium zu sein.
Siehe hier.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6005
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2020-05-23


Ich habe es mal programmiert.

Vom im TS abgebildeten Startzustand benötigt man 5 Drehungen, um in den Zielzustand zu gelangen. Die Maximalzahl benötigter Drehungen, um von einem beliebigen Startzustand in den Zielzustand zu gelangen, ist 7.



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: 3531
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, eingetragen 2020-05-24


Hier ist der Plan, wie ich es programmieren würde:

(mit zwei Verbesserungen, von denen eine von StrgAltEntf im Folgepost angemerkt wurde )

- Ein Datenmodell finden, in dem alle möglichen "Stellungen" beschrieben werden können,
- Eine Beschreibung, wie die möglichen "Drehungen" auf jede dieser Stellungen wirken, das heißt eine Zuordnung der Form "Stellung A wird durch Drehung B in Stellung C überführt"
 und dann folgender Algorithmus:

- Erstelle eine Liste aller Stellungen,
- Markiere die Gewinnstellung mit "0" (im Sinne von "ist in Null Zügen lösbar"
- Führe folgendes aus und wiederhole es solange, wie du in der vorhergehenden Runde noch neue Stellungen markiert hast:

>> Für die Grundstellung, später für alle in der letzten Runde neu markierten Stellungen A und alle Drehungen B prüfe, ob die Stellung C, in die diese Drehung führt, schon markiert ist.

>> Ist sie noch nicht markiert, markiere sie mit der um eins erhöhten Markierung von A, und vermerke an der Stellung C als "Lösungzug": "Gehe mit der umgekehrten Drehung B in Stellung A".

- prüfe jetzt, ob es noch unmarkierte Stellungen gibt. Wenn ja kann von diesen Stellungen aus die Grundstellung nicht erreicht werden (in diesem Spiel gibt es aber solche Stellungen nicht).

Und fertig. Nun weiß man für jede Stellung, ob und in wievielen Zügen sie zu lösen ist, und erhält schrittweise den Weg, wie man zur Zielstellung gelangt.

Programmiert habe ichs noch nicht. Mal sehen, wieviel Zeit der Sonntag Nachmittag so bringt :)

Grüße

Gonz



   



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6005
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2020-05-24


Hallo Gonz,

viel Spaß beim Programmieren! 😃

2020-05-24 12:06 - gonz in Beitrag No. 9 schreibt:
- Wiederhole solange es noch nicht markierte Stellungen gibt:

Achtung! Hier landest du möglicherweise in einer Endlosschleife. Denn es ist erst einmal nicht garantiert, dass jede Stellung erreichbar ist. Beispielsweise gibt es bei Rubik's Cube nicht erreichbare Stellungen. Hier hat man aber Glück, und es ist tatsächlich jede Stellung erreichbar. Zur Kontrolle, hier was ich berechnet habe, natürlich ohne Gewähr:
d = 0  1
d = 1  6
d = 2  27
d = 3  117
d = 4  309
d = 5  359
d = 6  101
d = 7  4
sum = 924
(Lies etwas: Es gibt 117 Stellungen, die mit 3 Drehungen in die Gewinnstellung überführt werden können.)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haegar90
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.03.2019
Mitteilungen: 357
Aus: Gog
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, eingetragen 2020-05-24


Hallo,

habe auch heute mal daran gebastelt.
Das ist der Anfang, allerdings basiert es noch auf Zufall.
Wenn wieder Zeit ist soll das noch in eine optimierte Suchreihenfolge umgestrickt werden 😃 ... mal sehen ob das mit diesem Ansatz klappt🙃

Kreisdrehpuzzle
Python
# Drei Ringe Rätsel, rot = 1, grün = 2
import numpy as np
from random import randrange as rg
 
lsg = np.array([[1, 1, 2, 2, 2, 2],[2, 2, 1, 1, 2, 2],[2, 2, 2, 2, 1, 1]])
jop = np.array([[1, 1, 2, 2, 2, 2],[2, 2, 1, 1, 2, 2],[2, 2, 2, 2, 1, 1]])
sol = np.array([[1, 1, 2, 2, 2, 2],[2, 2, 1, 1, 2, 2],[2, 2, 2, 2, 1, 1]])
 
# RingTurn a:= Ring 1 bis 3, b:= Anzahl Drehschritte 1 bis 5 
def rt(a,b):
    for i in range(0,b):
        kx = 0 
        for k in range(0,6):
            if k == 0:
                kx = 5
            else:
                kx = k - 1
            sol[a,k]=jop[a,kx]       
    if a == 0:
        sol[1,1]=sol[0,2]
        sol[1,5]=sol[0,4]
        sol[2,0]=sol[0,5]
        sol[2,2]=sol[0,3]       
    if a == 1:
        sol[0,2]=sol[1,1]
        sol[0,4]=sol[1,5]
        sol[2,1]=sol[1,0]
        sol[2,3]=sol[1,4]      
    if a == 2:
        sol[0,5]=sol[2,0]
        sol[0,3]=sol[2,2]
        sol[1,0]=sol[2,1]
        sol[1,4]=sol[2,3]
    for ring in range(0,3):
        for k in range(0,6):
            jop[ring,k]=sol[ring,k]    
 
 
# Zufällige Startkonstellation
def start_sol():    
    for z in range(0,5):
        rt(rg(0,3),rg(1,6))
    print('Startkonstellation: ','\n',sol)    
    print('Zielkonstellation: ','\n',lsg,'\n')
 
 
### Hauptprogramm - zu vorläufigen Prüfung 
start_sol()
ct = 0
x = 1
while not np.all(x == 0):
    ct+=1
    x = lsg - sol
    if np.all(x == 0):
        print(ct, ' Schritte')
        print(sol,'\n')
        print(sol - lsg,'\n')
    rt(rg(0,3),rg(1,6))   




-----------------
Gruß haegar



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
jjzun
Junior Letzter Besuch: im letzten Monat
Dabei seit: 20.07.2019
Mitteilungen: 14
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, vom Themenstarter, eingetragen 2020-05-24


Hallo nochmal,

Wow, ich hätte nicht gedacht, dass so viele an diesem Problem interessiert sind! :)
Das ganze Problem scheint komplexer zu sein, je mehr ich darüber nachdenke.
Ich hatte gehofft, dass man es irgendwie einfacher lösen könnte, wenn man nur die entsprechende Gruppe fände...

Ihr habt Recht, das ist eine gute Programmieraufgabe,aber mir steht zur Zeit nicht der Sinn danach. Die Resultate für Minimale/Maximale Drehungsanzahl für beliebige Konfigurationen sehen aber sehr interessant aus!

Die Idee, wie beim Rubik's Cube spezielle Drehungen zu finden, wird in der Praxis da wohl noch am Schnellsten gehen, das werde ich mal versuchen.

Viele Grüße,
jjzun



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: 27369
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2020-05-25

\(\begingroup\)\(\newcommand\d{\mathop{}\!\mathrm{d}}\)
Noch ein Interessierter 😁

Programm in meiner Lieblingssprache APL (ist für den Uneingeweihten genauso unleserlich wie z.B. Haskell)🤢

Zeile 1..27 ist nur Vorgeplänkel:
• Definition der Start- und Zielkonstellation
• Hilfsfunktionen mit $\Delta$ für die Drehung und Ausgabeaufbereitung
In 28..52 wird nach der Lösung gesucht.
Am Ende dann der Aufruf und die Lösungssequenz für das Puzzle aus dem Themenstart. Das Feld in (X) ist jeweils der Drehpunkt, die Zahl danach gibt die Drehschritte an (2=2× rechts, -1=1× links).


\(\endgroup\)


Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6005
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.14, eingetragen 2020-05-25


2020-05-25 02:10 - viertel in Beitrag No. 13 schreibt:
Programm in meiner Lieblingssprache APL (ist für den Uneingeweihten genauso unleserlich wie z.B. Haskell)🤢

Der Code sieht ja wirklich lustig aus 😄

Wie ich sehe, bist du schon nach drei Zügen fertig, wertest aber mehrere Drehungen ums selbe Zentrum als nur einen Zug. Deine Lösung hätte ich mit 6 bewertet - das soll jetzt keine Schulnote sein 😁



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: 27369
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.15, eingetragen 2020-05-25


So sieht es aus, wenn ich nur die Züge 1 und -1 zulasse (nur Zeile [34] geändert):




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: 3531
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.16, eingetragen 2020-05-25


Ich bin diesmal langsam und möchte deshalb folgendes anmerken:

>> Es gibt zwei mögliche Datenmodelle wie mir scheint.

Man kann entweder etwas bauen nach dem Schema "Es gibt drei Ringe mit jeweils sechs Kugeln. Damit können wir auf jedem Ring einen Anfangspunkt festlegen, und beschreiben dann eine Position zB in der Form "Auf Ring A die dritte Kugel". Damit muss man beim Drehen berücksichtigen, dass die drei Ringe sich überlappen, also zB Kugel 3 aus Ring 1 auch Kugel 5 aus Ring 2 sein kein.

Man kann dann in einem der Ringe einfach drehen, indem man die Liste der Kugeln dort permutiert, ABER man muss nachher die sich ergebenden Änderungen auf die beiden anderen Ringe übertragen, sofern dort dieselbe Kugel vorhanden ist.

ODER

Man kann davon ausgehen, dass es insgesamt 12 Positionen gibt, die man zB einfach durchnummerieren kann. Die Anordnung ergibt sich dann darüber, dass es drei Ringe gibt, die jeweils Zeiger (oder einfach den Index) auf die Kugelposition der sechs im Ring liegenden Kugeln in der 12-er Liste beinhalten.

Dreht man, dann ermittelt man aus dem Ring die zu vertauschenden Indices, und führt die Änderung dann direkt in der 12-er Liste aus.



Das führt übrigens auf eine Abstraktion, die weitaus kompliziertere Dinge beinhaltet, sei es mit mehr Ringen, sei es mit mehr Dimensionen, und ggf. auch "den Cube" mit erfasst.


Soweit für heute (und ich habe immer noch nichts programmiert grins)
Gonz



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: 27369
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.17, eingetragen 2020-05-25


Den zweiten Weg habe ich ja beschritten. Beschreibung dazu im Kopf meiner Funktion, die Permutationen der 3 Drehungen in Zeile [15].
Ich sehe da kein Problem mit „weitaus komplizierteren Dingen“. Es erfordert nur Konzentration, die Permutationen zu erstellen. Das Prinzip kann auf beliebige viele verschlungene Ringe angewendet werden (irgendwo habe ich sowas – glaube ich – schon mal als olympische Ringe gesehen).



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: 3531
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.18, eingetragen 2020-05-25


2020-05-25 11:50 - viertel in Beitrag No. 17 schreibt:
Es erfordert nur Konzentration, die Permutationen zu erstellen.

... und da habe ich noch im Kopf, dass man das ggf. nicht händisch machen muss, sondern "irgendwas mit modulo" machen kann ...



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: 27369
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.19, eingetragen 2020-05-25


Bei geschickter Numerierung … vielleicht🤔



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
StrgAltEntf
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 19.01.2013
Mitteilungen: 6005
Aus: Milchstraße
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.20, eingetragen 2020-05-25


Ich finde ja viertels Lösung, bei der man Drehungen um dasselbe Zentrum zu einer Drehung zusammenfasst, besser als meine und habe das noch etwas differenziert:
         0   1   2   3   4   5   6   7   8
d = 0    1
d = 1        6   6   3
d = 2           21  48  36  24   6
d = 3               66 165 126  57  34  12
d = 4                   57 152  59  12  12
d = 5                           21
In den Zeilen steht, bei wie vielen Stellungen man d Drehungen braucht, um in den Zielzustand zu gelangen. Also z. B. bei 21 + 48 + 36 + 24 + 6 Stellungen braucht man 2 Drehungen. In den Spalten steht dann, um wie viele Positionen insgesamt gedreht werden muss. Also z. B. bei 57 Stellungen braucht man 3 Drehungen und diese drei Drehungen sind entweder alle um 2 Positionen oder um 1, 2 und 3 Positionen (so wie das Beispiel aus dem TS und die Lösung von viertel aus #13).

Die Lösung von viertel aus #13 ist auch in diesem Sinne optimal.

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



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: 3531
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.21, eingetragen 2020-05-25


Das war mir auch schon aufgefallen, dass es ggf. sein kann, dass die unterschiedliche Definition, was eine "Drehung" ist, dazu führt, dass es andere optimale lösungswege für ein und dieselbe ausgangsstellung gibt?



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: 3531
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.22, eingetragen 2020-05-25


Ich musste erstmal das GUI bauen (Tipps immer willkommen). Der Solver ist noch in Arbeit...





Demnächst geht es dann auch mit den anderen Überlegungen weiter...

Grüße Gonz



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: 27369
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.23, eingetragen 2020-05-26


2020-05-25 20:00 - gonz in Beitrag No. 22 schreibt:
(Tipps immer willkommen)

Hmm, sowas ?



Ist mir klar, das zu implementieren ist den Aufwand fast nicht wert. Jedenfalls nicht animiert 😁
Aber wenn ich dir die Kugeln in zwei Farben und 4 Größen (wegen der Perspektive; ohne [also in direkter Draufsicht] sind die Rinnen für die Kugeln nur schlecht erkennbar) liefere, dann ist es machbar. Man muß dann nur die 12 Positionen einmal pixelgenau ausmessen.
Ich wollte eigentlich auch nur die Idee rüberbringen, auf die weißen Pfeile zu klicken (der sensitive Bereich kann ja großzügig gewählt werden), um eine Drehung anzustoßen.



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: 3531
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.24, eingetragen 2020-05-26


Ja genau so etwas * schmunzel
Man braucht Pfeile, das habe ich auch gemerkt, die idee, die äußeren Kugelpositionen zu nehmen, funktioniert zwar, ist aber irgendwie nicht intuitiv bedienbar....
(es sei denn man könnte die kugeln mit der maus anstoßen)

povray ist klasse :) (ist das povray?)

Einen angenehmen Weg in den Dienstag wünscht
Gonz



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: 27369
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.25, eingetragen 2020-05-26


2020-05-26 07:12 - gonz in Beitrag No. 24 schreibt:
povray ist klasse :) (ist das povray?)
Ja. Ja. 😎



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
haegar90
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 18.03.2019
Mitteilungen: 357
Aus: Gog
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.26, eingetragen 2020-05-26


@gonz
Vielleicht lässt es sich mit turtle ganz gut darstellen und die buttons dann separat. (hier nur als prinzipielles Beispiel dazu) 🙂
Python
import turtle
 
kugel = turtle.Turtle()
kugel.shape('circle')
kugel.color("red")
 
kugel_2 = turtle.Turtle()
kugel_2.shape('circle')
kugel_2.color("green")
 
kugel.forward(60) 
for i in range(1,20):
    kugel.left(60)  
    kugel.forward(60)
    kugel_2.forward(60)
    kugel_2.left(60)
 



-----------------
Gruß haegar



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: 3531
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.27, eingetragen 2020-05-26


haegar: turtle steht auf der liste der zu erkundenden Dinge :)

Ich habe jetzt auch endlich mal einen solver gebaut, allerdings bisher ohne was drum herum. Sozusagen Jars - just another Ringe solver.

python
print("\nRinge 1.0 by gonz@gmx.biz - der Solver\n")
 
#        0 1 2
#       3 4 5 6 
#        7 8 9 
#         A B
 
ringe = [ [0,1,5,8,7,3],[6,9,8,4,1,2],[10,7,4,5,9,11] ] 
grundStellung = [0,1,0,0,1,1,0,1,1,1,0,0]
drehungen = ['A+','A-','B+','B-','C+','C-']
 
stellungen   = [grundStellung]
loesungsWege = [[]]
 
def drehe(stellung,thisDrehung):
    myRing = ringe[ord(thisDrehung[0])-ord("A")]
    if thisDrehung[1]=="+": myDir=1
    else: myDir=-1
    newStellung = [0]*12
    for loop in range(12):
        newStellung[loop] = stellung[loop]
    for loop in range(6):
        newStellung[myRing[loop]]\
                = stellung[myRing[(loop+myDir)%6]]
    return newStellung
 
print(grundStellung)
idxDone = 0
 
while len(stellungen)>idxDone:
    myStellung=stellungen[idxDone]
    for myDrehung in drehungen:
        checkStellung = drehe(myStellung,myDrehung)
        if not checkStellung in stellungen:
            newWeg = loesungsWege[idxDone]+[myDrehung]
            stellungen.append(checkStellung)
            loesungsWege.append(newWeg)
            print(checkStellung,newWeg)
    idxDone+=1
 
print("\nDone.\n")
 



 



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: 27369
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.28, eingetragen 2020-05-26


Um mal auf die eigentliche Fragestellung einzugehen:
„Mathematisch“ läßt sich das Problem nicht lösen. Es gibt keine „Formel“, die die Lösungsschritte ausspucken könnte.

Die richtige Frage wäre nach einer „algorithmischen Lösung“.
Deshalb habe ich es auch in das Unterforum Algorithmen / Datenstrukturen verschoben, Knobelecke war sowieso gänzlich falsch.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2168
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.29, eingetragen 2020-05-26


Von Hand kann man das Rätsel so lösen (von jeder Ausgangsposition):

1. Man sorge dafür, dass es zwei rote Kugeln gibt, die benachbart auf einem der drei Teilkreise liegen (o.B.d.A. auf dem unteren der drei Kreise): Wenn das nicht sowieso schon der Fall ist, dann kann man eine rote Kugel auf einem der drei Kreismittelpunkte parken und dann den Kreis um diesen Mittelpunkt (er muss dann eine weitere rote Kugel enthalten) drehen, bis dies erfüllt ist.
r = rot, x = beliebig
 x x x
x r r x
 x x x
  x x 


2. Jetzt kann man den unteren Kreis (mit den zwei benachbarten roten Kugeln) drehen, bis diese am "Rand" liegen, also die anderen beiden Kreise keine der beiden Kugeln enthalten. Ab jetzt muss man den unteren Kreis nie wieder drehen und nur noch die vier anderen roten Kugeln in die Zielpositionen bringen.
r = rot, x = beliebig
 x x x
x x x x
 x x x
  r r 

3. Wiederhole Schritt 1, d.h. sorge dafür dass von den übrigen zwei Kreisen mindestens einer (o.B.d.A. der linke Kreis) zwei benachbarte rote Kugeln enthält.
r = rot, x = beliebig
 x r x
x x r x
 x x x
  r r 

4. Man sieht leicht, dass es sogar möglich ist zu erreichen, dass der linke Kreis drei rote Kugeln in einer Reihe enthält. Man sorge dafür, dass dies der Fall ist und drehe den linken Kreis dann so lange, bis der rechte Kreis nur noch eine einzige rote Kugel (also die vierte der übrigen roten Kugeln) enthält. Das ist möglich, weil es überhaupt nur drei Positionen auf dem linken Kreis gibt, die nicht auch auf dem rechten Kreis liegen.
r = rot, x = beliebig
 x r x                     r x x               r r x             r x x
x r r x --drehe links->   r r x x --rechts->  r x x x --links-> r x x x 
 x x x                     x x x               x x x             r x x
  r r                       r r                 r r               r r

EDIT: Falls an dieser Stelle auf dem rechten Kreis gar keine rote Kugel liegt, verfahre man wie in Beitrag No.31.

5. Man drehe den rechten Kreis (mit nur einer roten Kugel) so lange, bis dessen rote Kugel genau eine Drehung von der Schnittmenge des rechten und linken Kreises entfernt ist.
r = rot, x = grün
 r x r                 
r x x x  
 r x x                 
  r r                  

6. Drehe den linken Kreis um eine Position in die richtige Richtung um zu erreichen, dass beide Kreise jetzt zwei benachbarte rote Kugeln enthalten.
r = rot, x = grün
 r x r                    r r r   
r x x x --drehe links->  r x x x  
 r x x                    x x x             
  r r                      r r              

7. Drehe den rechten Kreis, bis alle roten Kugeln auf dem rechten Kreis in der Zielposition sind. Anschließend drehe noch den linken Kreis bis das Ziel erreicht ist (falls nötig).
r = rot, x = grün
 r r r                     r x r   
r x x x --drehe rechts->  r x x r  
 x x x                     x x x             
  r r                       r r              



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: 3531
Aus: Harz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.30, eingetragen 2020-05-27


Nuramon:

Klasse, und das kann man sich sogar merken :)

Um es zu programmieren (wenn man das denn will) kann man dann einige der Schritte noch genauer fassen oder wieder in Teilschritte zerlegen, bis man bei einer Folge von "Drehungen" ist :)



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
Nuramon
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 23.01.2008
Mitteilungen: 2168
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.31, eingetragen 2020-05-27


Mir fällt gerade auf, dass ich zwischen 4. und 5. noch einen Sonderfall übersehen habe, nämlich könnte man bei
r=rot, x=grün
 r x x
r x r x
 r x x
  r r
landen, also alle vier roten liegen auf dem linken Kreis und keine auf dem rechten.
Das kann man aber so beheben:
r=rot, x=grün
 r x x              x r x                     x x x                r x x
r x r x --links -> r x x x -- 2mal rechts -> r x x r  -- links -> r x x r
 r x x              r r x                     r r x                r x x
  r r                r r                       r r                  r r
und dann kann man bei 5. weitermachen.



Eine Notiz zu diese Forumbeitrag schreiben Notiz   Profil  Quote  Link auf diesen Beitrag Link
jjzun hat die Antworten auf ihre/seine Frage gesehen.
jjzun hat selbst das Ok-Häkchen gesetzt.
Neues Thema [Neues Thema]  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]