08.10.2008, 09:55
ich schrieb: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.
Ok, das ist Unsinn. Die Methode taugt nicht für geradzahlige Feldgrößen. Und auch nicht für ungeradzahlige, denn durch die ignorierten Vertauschungen sind die übrigbleibenden Zahlen schon mal umsortiert, sodass pro Zeile mindestens eine Umsortieraktion weniger nötig ist.
bromp schrieb:Leider ist meine untere Grenze für das 3x3-Feld zur Zeit noch 13, also noch lange nicht gut genug.
Was meinst Du damit? Eine untere Grenze von 13? Ich denke, die Methode, die ich oben beschrieben habe, gilt nur für die Bewegung der letzten in die erste Zeile, dazu braucht man minimal 4+2+4 Bewegungen und um die kommt man nicht rum. Dabei durchmischt man mindestens 1 Element der Zeilen 2 und 3, braucht also mindestens 1 Tausch in vertikaler Richtung. Macht 11.
Sabine