3. Puzzle lösen

Puzzle lösen

  • J

    Hi, ich hab hier ein Minispiel namens "Sheep Mania".
    Jetzt sitze ich hier an einem Level, welches ich nicht schaffe und suche eine Lösung/Algorithmus das systematisch zu knacken.

    Spielfeld:

    ///////////
/    #####/
/   ##   #/
/ ###    #/
/##   S ##/
/#POGGG # /
/#    G # /
/######## /
///////////

    Legende:

    '/'=Levelbegrenzung
'#'=Zaun
' '=Leeres Feld(Gras)
'O'=Zielfeld
'S'=Schaf auf Gras
'G'=Schaf auf Ziel
'P'=Spieler auf Gras
'B'=Spieler auf Ziel

    Regeln:
    Ein Zaun ist unpassierbar.
    Der Spieler kann sich nach links, rechts, oben, unten bewegen.
    Der Spieler kann ein Schaf ein Feld weiter schieben, aber ist nicht stark genug 2 Schafe die hintereinander stehen zu verschieben.
    Der Spieler kann ein Schaf nicht ziehen.

    Ziel:
    Alle Zielfelder müssen mit einem Schaf besetz sein.

    Einfaches Beispiel:

    //////// => //////// => //////// => ////////
/######/ => /######/ => /######/ => /######/
/#P   #/ => /#    #/ => /#    #/ => /#    #/
/# S O#/ => /#PS O#/ => /# PSO#/ => /#  PG#/
/######/ => /######/ => /######/ => /######/
//////// => //////// => //////// => ////////

    Eins nach unten 2 nach rechts bringt hier den Sieg.

    Hab schon einen Algorithmus geschrieben(Breitensuche), der bis zu einer Tiefe von 13 das einfache Beispiel löst(also auch Lösungen angibt die nicht möglichst wenig Züge benötigen), aber die Schrittfolge steigt mit 4^n und für das richtige Problem, was ich angegeben habe, braucht man wohl mehr als 13 Schritte.

    Wie kann man das Problem angehen?
    Sieht vieleicht schon Jemand die Lösung?

    0
  • C

    Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (auch C++0x) in das Forum Rund um die Programmierung verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.

    0
  • ?

    Das sieht Sokoban sehr ähnlich; ich vermute, dass es ähnlich komplex zu lösen ist (d.h. NP-schwer). Mit Breitensuche wirst du da nicht weiterkommen.

    Unter Umständen kommt man da mit A* bzw. IDA* weiter, aber im Grunde ist das ein Problem, an dem die KI-Leute noch sitzen. An der Universität von Alberta forscht jemand an dem Problem. Der hat da auch einige Papiere zum Thema zum Download angeboten - es sollte mich nicht wundern, wenn man seine Methode für deine Sokoban-Variante anpassen könnte. Ob sich dieser spezielle Level damit lösen lässt, steht allerdings auf einem anderen Blatt.

    0
  • J

    Ok, gut zu wissen, dass es nicht mal eben so geht.
    Dann wäre ich auch mit der Lösung alleine zufrieden, falls Jemand grad lust hat oder den "blick" und sieht wie man das Level löst ;).

    Danke.

    0
  • V

    JaykopX schrieb:

    falls Jemand grad lust hat oder den "blick" und sieht wie man das Level löst ;).

    Das war meine erste Runde Sokoban per Notepad.

    ///////////
/    #####/
/   ##   #/
/ ###    #/
/##   S ##/
/#POGGG # /
/#    G # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###    #/
/##   G ##/
/# OGGG # /
/#   SB # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###    #/
/##   S ##/
/# OGGG # /
/#  SPO # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###    #/
/##  SS ##/
/# OGBG # /
/#  S O # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###    #/
/##  SS ##/
/# OGOG # /
/#  PSO # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###    #/
/##  SS ##/
/# OGOG # /
/#   PG # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###    #/
/##  SS ##/
/# GBOG # /
/#    G # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###    #/
/##  SS ##/
/# GOGB # /
/#    G # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###    #/
/##  SS ##/
/# GGBO # /
/#    G # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###    #/
/##  PG ##/
/# GGGO # /
/#    G # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###    #/
/##   P ##/
/# GGGG # /
/#    G # /
/######## /
///////////
    0
  • J

    Öhm, da bist du aber irgendwo durch getunnelt...

    ///////////
/    #####/
/   ##   #/
/ ###    #/
/##  SS ##/
/# OGBG # /
/#  S O # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###    #/
/##  SS ##/
/# OGOG # /
/#  PSO # /
/######## /
///////////

    ...Hier auch...

    ///////////
/    #####/
/   ##   #/
/ ###    #/
/##  SS ##/
/# GBOG # /
/#    G # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###    #/
/##  SS ##/
/# GOGB # /
/#    G # /
/######## /
///////////

    ...oder du hast Schritte weggelassen die ich nicht nachvollziehen kann...

    0
  • V

    JaykopX schrieb:

    Öhm, da bist du aber irgendwo durch getunnelt...

    Jup. Fehler von mir.
    Hab's mir jetzt mit Lego nachgebaut. Und finde keine Lösung.

    0
  • V

    Doch, vielleicht doch.

    ///////////
/    #####/
/   ##   #/
/ ###    #/
/##   S ##/
/#P SSS # /
/#    S # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###    #/
/##   S ##/
/#  SSS # /
/# SP   # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###    #/
/##   S ##/
/#  SSS # /
/# SP   # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###    #/
/##  SS ##/
/#  SPS # /
/# S    # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###    #/
/##  SS ##/
/#  S PS# /
/# S    # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ### S  #/
/##  SP ##/
/#  S  S# /
/# S    # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ### P  #/
/##  SS ##/
/#  S  S# /
/# S    # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###    #/
/##  PS ##/
/#  SS S# /
/# S    # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###    #/
/##  SP ##/
/#  SS S# /
/# S    # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###    #/
/##  SP ##/
/#  SS S# /
/# S    # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###  S #/
/##  S P##/
/#  SS  # /
/# S    # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###  S #/
/##  S P##/
/#  SS  # /
/# S    # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###  S #/
/## SS  ##/
/#  PS  # /
/# S    # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###  S #/
/## SS  ##/
/#  PS  # /
/# S    # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###  S #/
/## SS  ##/
/#    PS# /
/# S    # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###  S #/
/## SS S##/
/#     P# /
/# S    # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###  S #/
/## SS S##/
/#     P# /
/# S    # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###  S #/
/## SS S##/
/#      # /
/#   PS # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###  S #/
/## SS S##/
/#      # /
/#   PS # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###  S #/
/## SP S##/
/#   S  # /
/#    S # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###  S #/
/## S  S##/
/#  SP  # /
/#    S # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###  S #/
/## PS S##/
/#  S   # /
/#    S # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###  S #/
/##  S S##/
/# SP   # /
/#    S # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###  S #/
/##  P S##/
/# S S  # /
/#    S # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###  S #/
/##    S##/
/# SSP  # /
/#    S # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ### SP #/
/##    S##/
/# SS   # /
/#    S # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ### SP #/
/##    S##/
/# SS   # /
/#    S # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ### P  #/
/##   SS##/
/# SS   # /
/#    S # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###  S #/
/##   SP##/
/# SS   # /
/#    S # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###  S #/
/##   P ##/
/# SS S # /
/#    S # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###  S #/
/##     ##/
/# SSSP # /
/#    S # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###  S #/
/##     ##/
/# SSSP # /
/#    S # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ### SP #/
/##     ##/
/# SSS  # /
/#    S # /
/######## /
///////////

///////////
/    #####/
/   ##   #/
/ ###    #/
/##   P ##/
/# SSSS # /
/#    S # /
/######## /
///////////
    0
  • J

    :). Stimmt 👍 .

    0
  • I

    Bei der Gelegenheit, volkard, bist du imstande, deinen Lösungsalgorithmus zu nennen?

    0
  • V

    ipsec schrieb:

    Bei der Gelegenheit, volkard, bist du imstande, deinen Lösungsalgorithmus zu nennen?

    Ja Nein, denn er ist fehlerhaft.
    Der Algo ist Backtracking mit kleinem Orakel.

    Angefangen hat es mit:

    ///////////
/    #####/
/   ##   #/
/ ###    #/
/##   S ##/
/#P SSS # /
/#    S # /
/######## /
///////////

    Ich benenne die Kisten mal.

    ///////////
/    #####/
/   ##   #/
/ ###    #/
/##   3 ##/
/#P 124 # /
/#    5 # /
/######## /
///////////

    Und schau, welche Züge erlaubt sind:

    Wobei ich die offensichtlichen GehtNicht, weil ich nicht zwei Schafe schieben kann und weil ich nicht dahinter komme, weglasse.

    Es gibt bestimmte Muster, die klar der Tod sind.

    1H Gefahr! Eventuell komme ich nie mehr hinter die Herde, so daß ich 2 niemals nach links bekommen kann. Wie kann ich noch hinter die Herde kommen? 1H1R? Nein! Der Viererblock ist der Tod. 1H2H? Brächte nur was, um 1H2H2H zu machen, aber 2 in der Ecke ist der Tod. Oder für 1H2H4R, aber 5 und 4, die eine Ecke so einschließen sind der Tod. Also ist 1H2H schlecht. 1H5R ist der Tod. Also ist 1H schlecht.

    1R Ist der sofortige Tod, da jetzt 1 und 5 auf der Grundlinie liegen. Von so eine Linie kann man ein Schaf nicht wegkriegen.

    2H Danach kann man in Richtung hinter die Herde nur noch mit 2H, 4R oder 5R kommen, alle drei sind der offensichtliche Tod.

    Und so weiter. Es blieb als Anfangszug nur 5L.

    Aber das Schwierige ist, saubere Schlußregeln zu bekommen, ab wann man sich ausgesperrt hat.
    Das hier

    ///////////
/    #####/
/   ##   #/
/ ### 1  #/
/##  2P ##/
/#  3  4# /
/# 5    # /
/######## /
///////////

    trennt ja die Gebiete a und b in

    ///////////
/    #####/
/   ##bbb#/
/ ###c1bb#/
/##aa2Pb##/
/#aa3bb4# /
/#a5bbbb# /
/######## /
///////////

    Ich muß aber nach a kommen, um 5 nach links schieben zu können.

    3L natürlich verboten, weil die beiden linken a ein neues Gebiet aufmachen, in das ich reinmüßte, aber das geht nicht.
    3H? Nee, die 3 könnte ich nur von der Wand machen, wenn die 2 da weg wäre, und zwar nach unten, das ginge nur, wenn die 1 da weg ware.
    Aber dann stünde es so:
    ///////////
    / #####/
    / ## #/
    / ### #/
    /## 3P1 ##/
    /# 2 4# /
    /# 5 # /
    /######## /
    ///////////
    Und das gehz nicht, wegen 3 in der Ecke ist der Tod, 2 am Boden auch, das 14-Päärchen an der Wand auch. Und 4 am Boden auch. Und ich muß auf die andere Seite, mindestens noch für die 5.

    Ähnliche Überlegungen führen dazu, daß

    ///////////
/    #####/
/   ##   #/
/ ### 1  #/
/##  2P ##/
/#  3  4# /
/# 5    # /
/######## /
///////////

    schon tot ist.
    Ist aber nicht so. Hab mich von Vermutungen leiten lassen. Das Orakel orakelt zu defensiv. Deswegen hatte ich angenommen, es sei unmöglich.

    0
Anmelden zum Antworten