8-Puzzle
-
Hallo ich wollte mal fragen ob es bei einem 8-Puzzle also das Spiel bei dem man auf den 9 Feldern die 8 kästchen umherschiebt ob es da immer eine Lösung gibt...
Wenn ja wie weit müsste ich da mit iterative deeping maximal Runtergehen ohne Heuristik bis ich die Lösung gefunden habe?
Danke
-
Edit:
Nanu, wie kam das denn hier hin? Falsches Topic, sorry...
-
Ne
-
spieler schrieb:
Hallo ich wollte mal fragen ob es bei einem 8-Puzzle also das Spiel bei dem man auf den 9 Feldern die 8 kästchen umherschiebt ob es da immer eine Lösung gibt...
denk es erstmal als 9-puzzle. das loch ist auch ein spielstein, der halt durchsichtig ist.
die möglichen züge sind nur vertauschungen von zwei benachbarten steinen, wobei ein stein das löch ist.
die möglichen züge sind nur vertauschungen von zwei benachbarten steinen.
unter den steinen liege ein schachbrett. also jedesmal, wenn man das loch zieht, wechselt es seine farbe von schwarz auf weiß oder von weiß auf schwarz.sei die untersuchende stellung eine, das loch auf seiner zielposition ist und sonst alle steine richtig sind aber nur die ersten beiden steine vertauscht.
nu seh ich folgendes: es braucht genau eine vertauschung, um das spel zu lösen. leider ist das loch nicht in der nähe. das loch kann ne prima rundreise machen, aber braucht dazu sicher eine gerade anzahl von vertauschungen.irgenwie hab ich im gefühl, daß man eitwas, das man in x vertauschungen lösen kann, auch in x+2 oder x+4 ode4r x+2*n vertauschungen lösen kann, aber nie in x+1 oder x+2*n+1 vertauschungen. müßte dazu mal alle möglichen stellungen klassifizieren und zeigen, daß ich von jeder geraden stellung in eine ungerade komme und von jeder ungeraden stellung in eine gerade. nur seh ich das jetzt nicht.
also bis auf ein kleines detail, an das ich glaube, ist der rest sicher. nicht jede stellung ist lösbar. schätze, jede zweite ist lösbar.
-
Aha ok Merci
Gleich noch eine Frage. Wenn ich den A* Algorithmus nehme was würde ich dann als g(n) nehmen kann mir da bei bisherige Kosten von Start zu n nichts vorstellen... Heißt das einfach die Tiefe welche ich gegangen bin denn die 4 Aktionen sollten doch alle die gleiche Gewichtung haben...
-
volkard schrieb:
müßte dazu mal alle möglichen stellungen klassifizieren und zeigen, daß ich von jeder geraden stellung in eine ungerade komme und von jeder ungeraden stellung in eine gerade. nur seh ich das jetzt nicht.
Da kannste Dich in der LA bedienen. Permutationen lassen sich in Transpositionen zerlegen. Entweder ne gerade oder ne ungerade Anzahl. Aber nie einmal so einmal so.
Beweis dazu müßte man induktiv auch ganz gut hinkriegen.
-
Hier ist es schön elementar dargelegt warum nicht alle
Anfangskonfigurationen lösbar sind.
-
hier ist schön elementar dargelegt warum nicht alle konfigurationen lösbar sind