Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
4.4 Schiebepuzzle AI - Loesbarkeit feststellen
Hi,
falls noch jemand versucht dem Text von Wikipedia fuer die Invariante zur Loesbarkeitspruefung zu folgen:
Ich glaub, das steht falsch in Wikipedia.
http://en.wikipedia.org/wiki/15_puzzle
sagt
The invariant is the parity of the permutation of all 16 squares plus the parity of the taxicab distance (number of rows plus number of columns) of the empty square from the lower right corner. This is an invariant because each move changes both the parity of the permutation and the parity of the taxicab distance. In particular if the empty square is in the lower right corner then the puzzle is solvable if and only if the permutation of the remaining pieces is even.
Wenn ich das richtig sehe, ist die Invariante aber die Differenz der beiden Parity-Werte (oder Parity von der Summe, ist das gleiche),
nicht aber die Summe der beiden Parity-Werte.
Kann man sich im Prinzip auch überlegen, wenn man von einem gelösten Feld ausgeht.
Sieht das jemand anders?
Wolfgang
Sollen wir überhaupt ein algo entwickeln das beliebige nm Felder bearbeitet? Oder beschränken wir uns auf 33?
mhh,
Ich frage mich ob ein algo was für ein 15puzzle gilt auch für puzzles anderer größen gilt.
Beziehungsweise ob ein algo was für ein puzzle gerader spaltenzahl und zeilenzahl auch für eins mit ugneraden gilt.
Kann man überhaupt damit rechnen das diese puzzles immer nn sind und nicht vielleicht mal nm?
Ziemlich schwer die Aufgabe :#:
(Rhetorische) Gegenfrage: Warum ist die Größe relevant?
Dazu sagt die Aufgabenstellung recht klar:
… es gibt dazu sogar ein Bild mit einem 3x4-Feld!