PuzzleUp

[SabineH]

Es gibt 'ne schöne Formel : Z(n) = 2n x G(n-1)

Genau! Die taugt als obere Grenze und ist für das 8x8 Gitter schon ordentlich hoch und damit außerhalb der Aufmal-Möglichkeiten.

Aber, ist der noch abkürzbar? mit Diagonaltausch komm ich auf 12.

Ein Gedanke für eine untere Grenze, nunächst fürs 3x3 Schachbrett:

Code:

123           987
456    -->    654
789           321

Zunächst geht es darum, die 9 an die Stelle der 1 zu befördern. Dazu braucht es genau 4 Züge, egal wie. Selbiges gilt für die 7 um sie an die Stelle der 3 zu befördern. Für den Tausch 8 gegen Stelle der 2 braucht man 2 Züge. Damit hätten wir die unterste Zeile in die oberste transportiert.
Jetzt vergesse ich mal für einen Moment, dass bei dieser Sortieraktion der alte Inhalt von Zeile 1 und 2, der jetzt in Zeile 2 und 3 steht, ziemlich durcheinander geraten ist und nehme an, der wäre noch wie ursprünglich sortiert:

Code:

123
456

Dann wende ich obiges Verfahren auf die zwei verbleibenden Zeilen nochmal an. Diesmal brauche ich genau 3 Züge um die 6 an die (neue) Position der 1 zu befördern, selbiges gilt für die Vertauschung von 4 und 3. Für 5 und 2 benötige ich 1 Zug. Wenn ich nochmal ignoriere, dass die letzte Zeile ineinander vertauscht sein kann, habe ich also mindestens (4+2+4) + (3+1+3) = 8+7 = 15 Züge gemacht. Drunter gehts nicht (meiner Meinung nach), denn die Methode macht nichts weiter als die Summe der Distanzen zwischen der Position im alten Feld und neuen Feld zu bestimmen. Diese sind bei der Vertauschung zweier horizontal oder vertikal benachbarter Zahlen nur von der Größe des Gitters abhängig. Für das 4x4 Schachbrett braucht man dann mindestens 56 = (6+4+4+6)+(5+3+3+5)+(4+2+2+4)+(3+1+1+3) Züge, für 8x8 480.
Da ich (für's 3x3) die Vertauschungen innerhalb der Zeilen 2 und 3 ignoriert habe, diese aber auftreten, dürfte 16 die Minimallösung sein (die ich aber noch nicht gefunden habe - würdet ihr sie hier im Forum posten ?)

Gespannt, ob ihr mir die Methode für's (unerreichbare) Minimum abnehmt,
Sabine