PuzzleUp

[lupo]

What's up with PuzzleUp ?
Ich versuche jetzt schon Stunden auf die Puzzle-Up Seite zu kommen.
Habt Ihr das auch, oder hat mich Mr. Halici ausgesperrt, weil ich immer nur rum-meckere!

Ich komm auch nicht drauf, keine Panik!

wie war das in den Vorjahren? gab's da den "Percentage"-Bonus noch nicht? wenn doch, wo und wie wurde der geglättet, weil im Endergebnis (und auch heuer im vorl. Scoreboard) nur ganze Zahlen dastehen?

Es wird wohl gerundet (vielleicht kaufmännisch), wie allerdings weiß ich nicht.

Es gibt 'ne schöne Formel : Z(n) = 2n x G(n-1), für n=8 kommt was raus mit (letzte Ziffer - erste Ziffer = vorletzte Ziffer) , und was G(n) bedeutet, bleibt der Spannung halber erstmal ungesagt.
Eine Frage bleibt offen: ist das die kürzeste Strategie? und das ist wohl nicht so einfach, aber das WE ist ja lang.

Wie man dieses Schachbrett-Sortier-Problem auf ein kleineres reduzieren kann, ist mir ehrlich gesagt nicht klar. Aber vielleicht meinst du das auch gar nicht. Mein erster (suboptimaler;-) Ansatz hätte für ein 3*3-Schachbrett 18 Züge gebraucht; wahrscheinlich meinst du den. Ich hatte auch einen "Beweis" dafür; leder ist er trotzdem falsch. Meine aktuelle Vermutung ergäbe 16 Züge.

[geophil]

Ich komm auch nicht drauf, keine Panik!

Du hast Recht, geht wieder

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

Mein erster (suboptimaler;-) Ansatz hätte für ein 3*3-Schachbrett 18 Züge gebraucht; wahrscheinlich meinst du den. Leider ist er trotzdem falsch. Meine aktuelle Vermutung ergäbe 16 Züge.

Da hast du wohl zweimal Recht:
Meine Formel beschreibt den trivialen Weg, und kommt auf 18 bei 3x3 - aber wie ich schon fragte: ist das der kürzeste Weg? Jetzt weiß ich: das ist nur ein oberes Limit; es geht auch drunter, bei 3x3 hab ich jetzt eine Zugfolge mit 16.
Aber, ist der noch abkürzbar? mit Diagonaltausch komm ich auf 12.

[bromp]

Das sollte doch für ein langes WE erst mal reichen, oder?

Vielen Dank, Jürgen! Hätte ich doch nur vor dem langen, internetfreien Wochenende noch mal ins Forum geschaut...

Die Roboteraufgabe finde ich richtig gut! Zum Schachbrett habe ich noch keine Idee, aber vielleicht komme ich dabei schneller vom Schlauch als bei den Queens.

Viele Grüße,
bromp

[lupo]

Die Roboteraufgabe finde ich richtig gut!

Das ist eine richtige Aufgabe mit Aha-Effekt, oder? (Allerdings muss ich zugeben, dass ich recht lange gebraucht habe, um drauf zu kommen, hab erst mal gerechnet, gezeichnet, gemacht und getan...(warum funktionieren meine Smilies nicht mehr??? ÄRGER!))

[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

[geophil]

Zunächst geht es darum, die 9 an die Stelle der 1 zu befördern ...
Da ich ... 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 ?)

Neee! natürlich nicht, da wäre ja die Spannung für die anderen weg!
aber eine kleine pn ist schon drin
Georg

[bromp]

Sabine, Dein Ansatz ist gut, allerdings enthält er meiner Meinung nach in der Mitte (diese Ungenauigkeit dient dem Schutz derjenigen Miträtsler, die noch auf der Suche nach der 16-Züge-Lösung sind) einen kleinen Denkfehler - und wenn Georgs Lösung für 16 Züge auf dem 3x3-Brett ähnlich ist wie meine, wirst Du ihn bemerken. Ich glaube auch, dass es für das 4x4-Brett eine Lösung mit 40 Zügen gibt, sofern ich mich nicht verzählt habe.

Leider ist meine untere Grenze für das 3x3-Feld zur Zeit noch 13, also noch lange nicht gut genug.

Gibt es hier im Forum eigentlich eine Spoilerfunktion? Ich kenne das aus anderen Foren: Text wird mit identischer Vorder-und Hintergrundfarbe dargestellt; um ihn lesen zu können, muss man ihn auswählen. In der Hilfe habe ich nichts dazu gefunden.

[lupo]

mit Diagonaltausch komm ich auf 12.

Erhöhe auf 10!

Ich glaube auch, dass es für das 4x4-Brett eine Lösung mit 40 Zügen gibt, sofern ich mich nicht verzählt habe.

Ist auch meine Lösung.

Gibt es hier im Forum eigentlich eine Spoilerfunktion? Ich kenne das aus anderen Foren: Text wird mit identischer Vorder-und Hintergrundfarbe dargestellt; um ihn lesen zu können, muss man ihn auswählen. In der Hilfe habe ich nichts dazu gefunden.

Ich hab schon mal Weiß als Farbe gewählt. Ist nicht ganz perfekt, aber man muss sich anstrengen um es zu lesen.
Oder so. Ist schon besser, oder?

Wer von euch hat denn schon die Robotergeschichte gelöst (oder ist durchschaut das bessere Wort?)

[geophil]

G: mit Diagonaltausch komm ich auf 12...
J: erhöhe auf 10!

wie bitte !? dann reduziere ich meine 12er-Lösung auf 10
danke für den Tipp, das ist wirklich eine brilliante Lösung Dumm, dass bei n=8 n gerade ist.

Wer von euch hat denn schon die Robotergeschichte gelöst?

Erst dachte ich, meine Lösung ist viel zu einfach! - kann gar nicht stimmen! Jetzt bei Deiner Zusatzfrage in weiß
kommen mir doch wieder Zweifel: das könnte ja doch stimmen! 1 9 0
Und dann frag ich mal: was passiert, wenn auf jeder Seite nicht 10, sondern 11 (oder 13) Roboter auf Ihren Einsatz warten?
Georg

[SabineH]

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.

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