Die Mathe-Redaktion - 23.09.2018 14:55 - Registrieren/Login
Auswahl
ListenpunktHome
ListenpunktAktuell und Interessant ai
ListenpunktArtikelübersicht/-suche
ListenpunktAlle Links / Mathe-Links
ListenpunktFach- & Sachbücher
ListenpunktMitglieder / Karte
ListenpunktRegistrieren/Login
ListenpunktArbeitsgruppen
ListenpunktSchwätz / Top 15
ListenpunktWerde Mathe-Millionär!
ListenpunktFormeleditor fedgeo
Schwarzes Brett
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden. Mitglieder können den Matheplanet-Newsletter bestellen, der etwa alle 2 Monate erscheint.

Der Newsletter Okt. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 434 Gäste und 34 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Algorithmus für das "Verflixte Hexenspiel"
Druckversion
Druckversion
Antworten
Antworten
Autor
Kein bestimmter Bereich Algorithmus für das "Verflixte Hexenspiel"
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2885
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Themenstart: 2018-08-15


Hallo,

ich bin ( weil es hier in der Familie am Start ist ) auf das "verflixte Hexenspiel" gestoßen.

Das Spiel funktioniert so: Es gibt neun quadratische Karten, auf denen jeweils Figuren so angeordnet sind, dass an jeder Kante entweder das "Vorder-" oder "Hinterteil" einer Figur angedockt ist ( in unserem Fall sind es Hexen, es gibt das Spiel auch mit anderen Figuren ). Außerdem sind die Figuren in vier Farben eingefärbt. Die Aufgabe besteht nun darin, die Karten so in einem 3x3 Quadrat anzuordnen, dass an jeder Kante auf beiden Seiten je ein Vor- und ein Hinterteil von derselben Farbe aneinander stoßen.

Ohne Werbung für eines dieser Produkte machen zu wollen, hier findet sich bei Youtube etwas dazu:

youtu.be/Pk3P3B6qq04

Ich will das Ganze nun Programmieren. Mit etwas "brute force" geht das halbwegs, ich fange mit der mittleren Karte an ( diese kann beliebig gedreht sein, da sich die Lösungen sonst ggf. nur um eine Drehung voneinander unterscheiden ) und versuche dann im Kreis herum die Felder aufzufüllen. Ich gehe einfach den entstehenden Baum durch, es sind meist ja nicht so viele Karten die überhaupt passen. Zum Beispiel für das erste Feld, in der Mitte einer Randseite, kommen von den acht verbleibenden Karten im Mittel nur vier vor, die das betreffende Symbol tragen.

Ich habe allerdings irgendwie die Idee, dass es einfacher ginge. Man könnte sich zB vorher ausgucken, welche Karten überhaupt zusammenpassen etc, oder zählen, wie oft welche Symbole vorkommen, oder... Vielleicht hat jemand eine Idee wie es einfacher geht?

Dies ist naturgemäß keine Knobelfrage, da ich ja die Lösung selber nicht kenne. Ich würde mich aber über Anregungen freuen ( bzw. werde selber noch beisteuert, was mir so einfällt zu dem Thema :)

Grüsse aus dem Harz
Gerhard/Gonz





-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
viertel
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 04.03.2003
Mitteilungen: 26472
Aus: Hessen
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.1, eingetragen 2018-08-15


Hi gonz

Ich würde bei der Größe 3×3 nicht allzuviel Gehirnschmalz in irgendwelche Optimierungen stecken. Backtracking und fertig.

Höchstens in die Speicherung der Karten, damit die Abfrage paßt/paßt nicht fix geht.

Gruß vom ¼


-----------------
Bild



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2885
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.2, vom Themenstarter, eingetragen 2018-08-15


Hallo Viertel,

und Danke für die Antwort.

Ja klar. Die Frage ist auch eher theoretisch motiviert, praktisch gibt es keine Notwendigkeit, hier die Laufzeit zu optimieren :)

Grüsse
Gonz


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2885
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.3, vom Themenstarter, eingetragen 2018-08-21


Ich habe da mal was vorbereitet - wer mag kann sich ja mal daran probieren. Jedes Mittel ist recht! Es könnte ja auch als Programmierübung hergenommen werden...

www.land-of-fun.de/yet/index.php

Viel Spass!


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 81
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.4, eingetragen 2018-08-28 18:12


Hallo Gonz,

das einfarbige Spiel kann man ohne verschieben lösen.
Beim Verschieben kommt die folgende Fehlermeldung:
 SCRIPT5009: 'merke_pos_' is not defined
index.php (1,2209)

Ansonsten finde ich das Spiel ganz nett. Was ich nicht verstehe ist, was genau du probieren möchtest. Die Frage hört sich an, als wenn du eine KI-Lösung bauen willst. Warum zeichnest du nicht ein valides Brett und mischt dann? Von der KI habe ich jedenfalls nichts mehr gesehen.

Viele Grüße



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2885
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.5, vom Themenstarter, eingetragen 2018-08-28 18:26


Hallo Scynja,

ja, ich habe das Script tatsächlich inzwischen kaputtgespielt * danke für die Rückmeldung, ich repariere das mal

Ich suchte eigentlich keine KI Lösung, sondern einen Algorithmus, der schneller ist als Backtracking ( und damit ggf. einfacher anzuwenden ist, wenn man das Spiel ohne Computerhilfe lösen möchte ). An der Version mit vier Farben, die wir hier haben, beiße ich mir wenn ich es so auf dem Tisch spiele die Zähne aus. Meine Frau hat es durch Zufall einmal gelöst, mir gelingt das nicht bisher ( wobei ich berechnet habe, dass ich wahrscheinlich so um die 10 Stunden herumprobieren müsste ).

Tatsächlich habe ich die Startdaten für das Programm so ermittelt ( eine valide Lösung per Zufall ermittelt und dann gemischt ).

Grüsse
Gonz


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1264
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.6, eingetragen 2018-08-28 23:51


Hallo gonz!

Ich kenne so ein Spiel als "Asterix". Das hab ich mal mit dem Computer gelöst.
Pascal
PROGRAM Asterix;
VAR
 a        : array[1..9,1..7] of Byte;
 t        : array[1..9,1..4] of Byte;
 benutzt  : array[1..9] of Boolean;
 weiter   : Boolean;
 i, j, Az, k : Byte;
 f,d : array[1..9] of Byte;
 taste : String;
{---------- šberprfung ob k.ter Stein zu setzen geht ----------}
PROCEDURE as(k : Byte);
 VAR
  Spalte, Zeile : Byte;
 BEGIN
  f[k]:=0;
  REPEAT
   f[k]:=f[k]+1;
   weiter:=True;
   IF benutzt[f[k]]=TRUE THEN weiter:=FALSE ELSE benutzt[f[k]]:=TRUE;
   WHILE weiter DO
   BEGIN
    d[k]:=0;
    REPEAT
     d[k]:=d[k]+1;
     FOR i:=1 TO 4 DO
      t[k,i]:=a[f[k],d[k]+i-1];
     weiter:=TRUE;
     Zeile :=k MOD Az; IF Zeile=0 THEN Zeile:=Az;
     Spalte:=((k-Zeile) DIV Az)+1;
     IF (Spalte>1) AND (ABS(t[k,3]-t[k-Az,1])<>4) THEN weiter:=FALSE;
     IF (Zeile>1)  AND (ABS(t[k,2]-t[k-1,4])<>4)  THEN weiter:=FALSE;
     WHILE weiter DO
     BEGIN
      weiter:=FALSE;
      IF k<Az*Az THEN as(k+1)
       ELSE
       BEGIN
        Write('Eine L”sung ist: ');
        FOR i:=1 TO Az*Az DO
        BEGIN
         Write(f[i],d[i],'; ');
         IF (i=3) OR (i=6) OR (i=9) THEN
           BEGIN Writeln(' ');  Write('                 '); END;
        END;
        Writeln(' ');
       END;
     END;
    UNTIL d[k]=4;
   benutzt[f[k]]:=FALSE;
   END;
  UNTIL f[k]=9;
 END;
 
{---------- Initialisierung ----------}
 BEGIN
  Az:=3;                                      {a[x,y] :: x Stein , y Bild}
  a[1,1]:=1; a[1,2]:=7; a[1,3]:=6; a[1,4]:=3; {y = 1 AsterixKopf   }
  a[2,1]:=3; a[2,2]:=2; a[2,3]:=6; a[2,4]:=5; {y = 2 ObelixKopf    }
  a[3,1]:=6; a[3,2]:=8; a[3,3]:=3; a[3,4]:=1; {y = 3 MirakulixKopf }
  a[4,1]:=8; a[4,2]:=3; a[4,3]:=2; a[4,4]:=5; {y = 4 Legion„rsKopf }
  a[5,1]:=8; a[5,2]:=6; a[5,3]:=1; a[5,4]:=3; {y = 5 AsterixRumpf  }
  a[6,1]:=8; a[6,2]:=1; a[6,3]:=2; a[6,4]:=5; {y = 6 ObelixRumpf   }
  a[7,1]:=5; a[7,2]:=6; a[7,3]:=3; a[7,4]:=4; {y = 7 MirakulixRumpf}
  a[8,1]:=7; a[8,2]:=8; a[8,3]:=1; a[8,4]:=4; {y = 8 Legion„rsrumpf}
  a[9,1]:=6; a[9,2]:=1; a[9,3]:=4; a[9,4]:=7;
  FOR i:=1 TO 9 DO
  BEGIN
   FOR j:=1 TO 3 DO
    a[i,j+4]:=a[i,j];
  END;
  FOR i:=1 TO 9 DO
  benutzt[i]:=FALSE;
  weiter:=TRUE;
{---------- HAUPTPROGRAM ----------}
  k:=1;
  Writeln(' ');
  Writeln('Hier kommen die L”sungen fr ''Asterix'':');
  Writeln('++++++++++++');
  Writeln('+          +  - die Abbildung links entspricht der Position 1');
  Writeln('+          +  - fr die Position 2 wird der Stein im');
  Writeln('+       +  +    Gegenuhrzeigersinn um 90 Grad gedreht');
  Writeln('+        + +    usw.');
  Writeln('++++++++++++');
  as(k);
  readln(taste);
END.
erzeugt die Ausgabe:
txt
Hier kommen die L”sungen fr 'Asterix':
++++++++++++
+          +  - die Abbildung links entspricht der Position 1
+          +  - fr die Position 2 wird der Stein im
+       +  +    Gegenuhrzeigersinn um 90 Grad gedreht
+        + +    usw.
++++++++++++
Eine L”sung ist: 13; 41; 52;  
                 61; 82; 24;  
                 72; 91; 32;  
 
Eine L”sung ist: 34; 93; 74;  
                 22; 84; 63;  
                 54; 43; 11;  
 
Eine L”sung ist: 53; 21; 33;  
                 42; 83; 92;  
                 14; 62; 73;  
 
Eine L”sung ist: 71; 64; 12;  
                 94; 81; 44;  
                 31; 23; 51; 

Viele Grüße
Ronald



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2885
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.7, vom Themenstarter, eingetragen 2018-08-29 09:13


Hallo Roland,

das ist nett :) Wie ich sehe hast du die Spielkarten nummeriert. Das hilft natürlich sehr, wenn man Backtracking manuell durchführen möchte...

Ich bleibe für mich mal dran, auch, weil das Ganze mein aktuelles Probeprojekt für "Gonz goes Apps" ist, mal ganz unabhängig davon, dass es irgendwie Spass macht :)

Ich habe aktuell drei Programme am laufen: Eins prüft Lösungen, und kann auch das Spielfeld zufällig belegen und dann lösen, um eine Statistik zu erzeugen, wie viele Zweige man wohl so im Backtracking durchlaufen muss ( dies ist in Pascal geschrieben ), ein PHP Programm, das ein vorgegebenes Kartenset in die Grafiken umsetzt, und eben das Javascript, dass einem ein vorgegebenes Spiel im Browser präsentiert ( sagte ich, dass ich JS nicht mag? grins ).

Es wird mich also noch ein wenig beschäftigen :)

Grüsse
Gonz


-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Delastelle
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 17.11.2006
Mitteilungen: 1264
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.8, eingetragen 2018-09-01 21:28


Hallo gonz!

Zu beachten:
wenn das Spiel gut gestaltet ist, gibt es nur wenige Lösungen. Bei meinem Asterixspiel kann beispielsweise die 1er-Karte nur in einer bestimmten Position an einer der 4 Ecken des Plans liegen. Falls ich in der Mitte mit Karte 1 angefangen hätte, gäbe es keine Lösung.
Deshalb habe ich bei meinem Asterix-Spiel mit dem Backtracking auch links oben angefangen.

Viele Grüße
Dlanor



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2885
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.9, vom Themenstarter, eingetragen 2018-09-02 09:34


Ja, sowas kann man gut machen. Mir ist beim Lösen auch schon aufgefallen, dass erstmal eine Tabelle mit der Anzahl von Farben und Unter/Oberteilen hilft, Teile zu identifizieren, die nur auf bestimmten Plätzen liegen können, und dann natürlich auch kleine Bauversuche, zB ob bestimmte angrenzende Kanten eines Teils beide im Inneren des Spielfelds liegen können, sprich ob es überhaupt eine Möglichkeit gibt, sie durch drei andere Teile zu einem 2x2 Feld zu ergänzen. Gibt es dabei genau eine Möglichkeit, dann ist man einiges weiter, alternativ kennt man zwei Kanten, die am äußeren Rand des Spielfelds liegen müssen und damit an einer Ecke.

Man kann dann andersherum natürlich auch Sets von Spielkarten so konstruieren, dass sie eben solche Möglichkeiten beinhalten, zB indem man von einer bekannten Lösung ausgeht und die Randfelder die ja beliebig gestaltet werden können so hernimmt, dass die gewünschte Anzahl von Alternativlösungen entsteht oder solche "Anfasser" für das Lösen.

Da ja Weihnachten naht und ich immer gerne mathematische Basteleien verschenke....

Grüsse und einen schönen Sonntag
Gerhard/Gonz




-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 81
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.10, eingetragen 2018-09-16 02:58


Hallo Gonz,

ich habe es einmal versucht (es ist aber noch nicht mobiloptimiert):
sigmanek.net/features/cursedWitch

Allerdings bin ich mir nicht sicher, ob es hundertprozentig korrekt funktioniert. Die Validierung basiert auf 20+ if-Abfragen in denen ich die Himmelsrichtungen abgleiche. Sobald die Applikation größer wird, muss ich es wohl auf modulo umschreiben.

Aber zurück zum eigentlichen Thema: Wie kann ich erkennen, ob und wie viele Lösungen es gibt? Wann ist die Lösung bei dem gewählten Setting (2 Symbole) eindeutig? (Mit eindeutig meine ich, dass alle anderen Lösungen durch Drehen des gesamten Feldes oder durch vertauschen identischer Teile auf eine Lösung zurückführbar ist.)


Wie viele Symbole brauche ich bei einer 4x4, 5x5, nxm Matrix mindestens, damit es eine eindeutige Lösung geben kann?



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2885
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.11, vom Themenstarter, eingetragen 2018-09-16 10:25


Hallo Scynja!

Bei mir funktioniert dein Script prima :) Und ist wirklich schön gemacht.

Ich habe keine theoretische Aussage dazu, wie man ohne es auszuprobieren herauszubekommen, wie viele Lösungen ein spezielles Puzzle dieser Art hat (ich habe ein Pascal Programm geschrieben, das mit "brute force" durchprobiert und mitzählt, wie viele Lösungen es gibt), und ob es effizientere Lösungsverfahren als "trial and error" und backtracking gibt.

Deshalb hatte ich ja den Thread hier gestartet :) Vielleicht lassen sich ja doch noch die eine oder andere Erkenntnis dazu finden.

Grüsse aus dem Harz
Gerhard/Gonz



-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
matph
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 20.11.2006
Mitteilungen: 5368
Aus: A
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.12, eingetragen 2018-09-16 13:29


Hallo,

Etwas einfacher, starte mit einer möglichen Lösung und Mische die Teile.

Hier ein kleines Beispiel smile

--
mfg
matph


-----------------
Wir müssen wissen, wir werden wissen. Hilbert
Das Buch der Natur ist in der Sprache der Mathematik geschrieben. Galilei



  Profil  Quote  Link auf diesen Beitrag Link
Scynja
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.02.2011
Mitteilungen: 81
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.13, eingetragen 2018-09-16 20:21


Interessant matph,
Ich habe es durch Schummeln hinbekommen (beim transform: rotate hingeguckt und alle erst einmal richtig hingedreht).
Du hast quasi die Druckversion implementiert.



  Profil  Quote  Link auf diesen Beitrag Link
gonz 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-2018 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. 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]