Hallo,

Lösung vom 15.12.
Diese Aufgabe war wohl die schwerste von allen 24. Jeder, der eine Lösung gefunden hat und es sind 15 , darf sich Rätselprofi nennen.
Das berühmteste Werk über mathematische Spiele, "Cyclopedia of Puzzles" von Sam Loyd, enthält neben dem Klassiker "Spiel 15" auch das Puzzle aus der Aufgabe.
Allerdings ist Loyd nicht der Erfinder. Schon 1909 beschrieb L.W.Hardy das Puzzle und ließ es sich patentieren. Er nannte es Dad's Puzzle. Im Vorfeld habe ich das nicht erwähnt, da man sonst ganz schnell www.cs.brandeis.edu/.../zzzDadsPuzzler.html und viele andere Seiten gefunden hätte.
Bis heute wird das Rätsel immer wieder "neuerfunden" und vertrieben.

Es ist ziemlich schwierig und eine optimale Lösung ist:
1, 2, 3, 5 zwischen 3 und 4, 1, 9, 8, 6, 7, 4, 5, 1, 9, 8, 6, 7, 4 zwischen 6 und 5, 7, 6, 4, 5, 1, 3, 2, 8, 9, 5 zwischen 4 und 8, 9, 8, 5, 4, 9, 8, 4 zwischen 5 und 2, 3, 2, 4, 5, 3, 2, 5 zwischen 4 und 1, 2, 3, 9, 8, 1, 5, 4, 2, 3, 9, 8, 1, 5 zwischen 1 und 4, 7, 6, 1.
Ich habe die erste Lösung vor längerer Zeit durch sehr langes Experimentieren gefunden. Ein Programm, das die Lösung ermittelt, habe ich nie fertig bekommen.

Beste Grüße
Mathematiker

Mathematiker hat folgendes geschrieben :

Hallo, Lösung vom 15.12.

Mir hat dieses Video geholfen, da ich selber irgendwie nicht auf die Lösung kam: vimeo.com/41687828

Ich habe die Lösung aus dem Mathematikprogramm Winfunktion. Da steht es drin.
Allein hätte ich das nicht geschafft.

Anika

Dann will ich mal ein paar Worte zum Programmieren eines Solvers für dieses Puzzle sagen:

Die grundlegende Idee ist dabei, rekursiv immer wieder jede mögliche Verschiebung durchzuführen, bis irgendwann Block 1 an der gewünschten Stelle ist. Betrachten wir mal eine mögliche Lösung:

Wenn in dieser Reihenfolge entsprechend die Blöcke verschoben werden (r=right, l=left, u=up, d=down), so landet Block 1 an der gewünschten Stelle.
Die Verschiebung selbst ist nicht kompliziert zu programmieren, wenn man das Spielfeld als 2D-Array umsetzt und in den Zellen entsprechend die Nummern der Blöcke stehen.

Nur wird es leider so einfach nicht funktionieren. Dies kann man sich leicht klar machen:
Die Situationen nach r1 ist genau die selbe wie nach r1.l1.r1. Man kann nun noch Unmengen (exponentiell viele) solcher Zugmöglichkeiten angeben, die jeweils die selbe Situation ergeben.

einfaches Hashing
Man benötigt also ein Verfahren, welches r1 = r1.l1.r1 = d5.u5.r1 erkennen kann. Dies kann man (z.B.) durch eine Hashtabelle lösen. Ein eindeutiger Hashwert ist z.B. das aneinanderhängen der Zellen.

Dies ergibt einen 64-bit integer. Nun kann man in einer Hashtable diese Werte ablegen. Jedesmal nach einem Zug wird der Hashwert der aktuellen Situation bestimmt und in der Hashtabelle nachgesehen, ob dieser Wert schonmal aufgetreten ist (also falls der Wert schon enthalten ist). Auf diese Weise können wir Wiederholungen ausschließen und das Puzzle lösen lassen.

Für Flemings-Puzzle ist dies jedoch noch nicht schnell genug.

größenbasiertes Hashing
Nun kann man sich überlegen, dass es eigentlich ganz egal ist, welche Namen gleichgroße Blöcke haben. Ob nun Block 8 oder Block 9 an einer bestimmten Stelle liegt, ist für die Lösung völlig unerheblich. Es genügt also, nur die Größen im Hashwert zu vermerken.

Mit dieser Lösung kann man nun auch Flemings Puzzle schnell (500ms) lösen.

Nerd-Mode Hashing
Nun hat diese Lösung noch einen "Schönheitsfehler". Man braucht eine Hashtabelle. Ich habe mir dann noch den Spaß gegönnt, und eine Hashfunktion gebaut, die 32bit-Werte erzeugt. Man braucht dann nur noch eine Maske für 2^32 bit (=128MB) und kann entsprechend die Bits setzen, wenn die Situation bereits aufgetreten ist. Ganz ohne extra Hashtabelle (deshalb ist die komplizierte Hashfunktion sogar eine Ecke schneller).

Der Code im Anhang realisiert beide Hashfunktionen (per Compiler-Direktive wählbar)

Lösungen
Das Programm bestimmt nur paarweise "vollständig unabhängige" Lösungen, d.h. wenn keine Zwischensituation (größenabhängig) die gleiche ist.

Für Floyds-Puzzle ergibt sich dann einzig die Lösung (79 Züge)


Für Flemings-Puzzle gibt es interessanterweise 8(!) Lösungen. Die kürzeste (116 Züge) ist:

Zitat:

Die Verschiebung selbst ist nicht kompliziert zu programmieren, wenn man das Spielfeld als 2D-Array umsetzt und in den Zellen entsprechend die Nummern der Blöcke stehen.

Kompliziert vielleicht nicht, aber es ist schon etwas Schreibarbeit. Ich habe mal den Quelltext zu meinem Solver angehängt. Ergebnis:

Zitat:

Winning path (67 moves) found after 37,0ms

Und natürlich die ganzen Züge. Ich habe aus Spaß auch mal Tiefensuche probiert, und er hat eine Zugfolge mit über 5000 Zügen gefunden

Meine Hash-Funktion schaut so aus:
Es wird also nur jedes zweite Feld einbezogen. Kollidierende Hashes werden von dem HashSet<T> über .Equals abgewickelt.

Da war ich mal 2 Stunden nicht im Forum (ich habe eine Demo programmiert), schon kommen die ganzen Lösungen.
Egal, meine Demolösung bringe ich jetzt trotzdem .
Eventuell ist dies nicht der optimale Weg, dafür war es meine eigene Idee .

ub60

Edit: Screenshot hinzugefügt.

Xion hat folgendes geschrieben :

Dann will ich mal ein paar Worte zum Programmieren eines Solvers für dieses Puzzle sagen: Die grundlegende Idee ist dabei, rekursiv immer wieder jede mögliche Verschiebung durchzuführen, bis irgendwann Block 1 an der gewünschten Stelle ist.

Backtracking?

Ich verwende Fachbegriffe nur, wenn ich davon ausgehen kann, dass jeder Leser auch exakt weiß, worum es sich dabei handelt, und wenn sie den Text entscheidend verkürzen. Immerhin will ich dem Leser verdeutlichen, was ich meine, und nicht, dass ich mehr Fachbegriffe kenne als er. Da "Backtracking" ein zentraler Bestandteil des Algorithmus ist, erkläre ich, was das bedeuted. Sonst könnte ich ja gleich sagen: "Der Algorithmus besteht aus Backtracking und Hashing. Die Lösung ist ...".

Ab und zu sitze ich in einer Vorlesung zu Wirtschaftspolitik und sehe, dass es in den Wirtschaftswissenschaften für jede noch so leichte Sache einen Fachbegriff gibt. Natürlich kann man prima damit angeben, wenn man in einem Satz fünf Begriffe nennt, die kein normaler Mensch benutzen würde, für Sachverhalte, die ein Grundschüler schon versteht.

In der Informatik hingegen stehen die Fachbegriffe meistens für schwierige Sachverhalte, die man nicht mal eben durch ein einfacheres Wort oder einen Nebensatz erklären kann. Backtracking gehört für mich allerdings nicht unbedingt dazu. Das liegt wohl daran, dass Informatiker es nicht nötig haben, das gegenüber mit Fachbegriffen zu verwirren, da schon die Themen selbst kompliziert genug ist

Hallo,

Xion hat folgendes geschrieben :

Dann will ich mal ein paar Worte zum Programmieren eines Solvers für dieses Puzzle sagen:

Tolle Lösung. Ich versuche seit einer Stunde zu verstehen, was Du da tust und es wird noch einige Zeit dauern, bis ich es wirklich kapiere.

Zum Rätsel vom 20.12.:
Viel muss ich nicht sagen, da alles im Programm steht. Es sind nur die 4 Hausnummern einzutragen.
Allerdings kann ich gar nicht einschätzen, wie viele Lösungen es geben wird. Ich finde es einfach, aber wer weiß ...?

Beste Grüße
Mathematiker

In Koproduktion vom Mathematiker (die viele Fleißarbeit) und mir (das "Rahmenprogramm") gibt es jetzt noch die erweiterte Version des Puzzle-Demos, in der auch die Lösung des Flemming-Puzzles visualisiert wird.

ub60

Xion, kann das sein dass du öfter was mit Lua machst? Ich frag nur wegen den Kommentaren

Tolle Defines auch.

Hallo,

Lösung vom 16.12.
Für Geübte ist das Herausfinden der Dreiecke kein Problem, für weniger Geübte kann es zur Qual werden.
Für die einzelnen Varianten von Dreiecken ergibt sich:


Abbildung 1: Es gibt 20 aneinanderstoßende Dreiecke, an den Spitzen 10 und im Inneren des Fünfecks weitere 10
Abbildung 2: Je 1 Paar anstoßender Dreiecke von 1. gibt ein neues Dreiecke, insgesamt 10
Abbildung 3: 10 aneinanderstoßende Dreiecke
Abbildung 4: Insgesamt 10 Dreiecke, die sich teilweise überlappen
Abbildung 5: Von jeder eingezeichneten Art existieren genau 10 Dreiecke
Abbildung 6: Von der gelb eingezeichneten Dreiecksart gibt es 10, von der anderen 5
Abbildung 7: 5 Dreiecke
Abbildung 8: 10 derartige Dreiecke
In der Summe existieren somit in der Ausgangsfigur genau 100 verschiedene Dreiecke.

Beste Grüße
Mathematiker

Es geht auch mit einem kleinen bisschen weniger Aufwand:

Von einer Spitze ausgehend gibt es zwei Strahlen, einmal zur anderen Spitze und einmal zur Mitte hin. Nun kann man eine kurve zeichnen, die zwischen diesen beiden Strahlen verläuft (in Rot):

Die Anzahl der Schnittpunkte ergibt die Anzahl der Dreiecke, die noch mal 10. Die drei grün markierten Linien liefern zusätzliche 3*5 Dreiecke, die jeweils eine ganze Spitze einnnehmen. Schließlich gibt es noch die 15 Dreiecke in der Mitte (siehe Mathematiker Bild 1 und 2)

70 + 15 + 15 = 100

Am Anfang habe ich leider eines doppelt gezahlt um kam auf 105

Hallo,
ich muss noch einmal etwas zur heutigen Aufgabe sagen, da es mehrere Verwirrungen gibt.

Links stehen 5 Hausnummern in verschiedenen Zahlschreibweisen anderer Sprachen. Diese geben die Hausnummer an. Die erste Nummer ist zum Beispiel in einer Sprache, die von sehr vielen Menschen im Nahen Osten und in Nordafrika gesprochen wird. Bekommt man z.B. Urlaubspost aus diesen Ländern, stellt man oft fest, dass auf der Briefmarke scheinbar nirgends eine Wertstufe steht. Sie ist aber vorhanden, nur eben nicht in unseren Ziffern.
Und deshalb hat der Weihnachtsmann eben auch das Problem, die Hausnummer des artigen Kindes zu ermitteln.

Die Hinweise rechts neben den Eingabefeldern beschreiben zusätzlich die gesuchte Zahl.
Ach so: Nicht die Anzahl der Primteiler sondern genau ein Primteiler ist bei der letzten Aufgabe gesucht.

Beste Grüße
Mathematiker

Nachtrag:
Morgen ist wieder ein Zahlenrätsel (Symbolrätsel, Kryptogramm) dran. Nicht weiter schlimm.
Einige scheinen sich ja unterfordert zu fühlen. Deshalb habe ich noch eine kleine Animation erstellt:

Was wird hier dargestellt?

Martok hat folgendes geschrieben :

Xion, kann das sein dass du öfter was mit Lua machst? Ich frag nur wegen den Kommentaren

Eigentlich nicht, hab nur einmal bisher Lua benutzt (in Zusammenarbeit mit Delphi, richtig cool).
//Edit: Ah, ich glaube zu verstehen, was du meinst. Ich hab mir angewohnt bei Kommentaren, die zu einem Block Code gehören, dies auch zu kennzeichnen. Fast eine Art begin/end für Kommentare

Martok hat folgendes geschrieben :

Tolle Defines auch.

Danke

Hallo,
ich muss auch noch einmal auf die Puzzle zurückkommen.
Auf der Seite www.cs.brandeis.edu/...ES/zzzRedDonkey.html wird eine verschärfte Form von Flemings Puzzle vorgestellt: "Super Century".


Es ergibt sich durch Verschiebung der Ausgangssituation. Ziel ist das gleiche wie bei Flemings Puzzle.

Xions geniales Programm funktioniert hier ebenso perfekt. Es ermittelt von 10 möglichen auch die kürzeste Lösung

Ich bin erneut begeistert, dass man solche komplizierten Puzzle in Bruchteilen von Sekunden lösen kann.

Sollte es jemanden interessieren, habe ich in ub60s Demonstrationsprogramm dies auch noch eingebaut.

Beste Grüße
Mathematiker

Hallo,

Lösung vom 17.12.
Diese Aufgabe ist eine reine Fleißaufgabe.
Für das Löchersetzen und -füllen muss man x-mal auf die Lochkarte klicken. Die endgültige Lösung ist



Auf den Lochkarten wurden die Ziffern 0 bis 9 durch ein Loch an der Stelle 0 bis 9 markiert. Für die Buchstaben galt, je nach Rechnersystem:
A ... I : Loch bei A und 1 bis 9
J ... R : Loch bei B und 1 bis 9
S ... Z : Loch bei 0 und 2 bis 9
Dabei ist die Zeile A die oberste, die Zeile B die zweite. Für die Sonderzeichen gab es spezielle Codes.

Beste Grüße
Mathematiker

Hallo,

die Aufgabe von morgen ist etwas "Spezielles".
Ich erwarte 0 Uhr und maximal 10 Sekunden eigentlich die erste Lösung, d.h. heute Nacht, wenn man mitmachen will, wird es auf Geschwindigkeit ankommen.
Allerdings kann es auch sein, dass einige gar keine Lösung finden.

Bei einem Test mit Schülern fanden etwa 25 % die Lösung sofort, weitere 25 % mit etwas Anleitung und der Rest gar nicht.
Was mag das wohl sein?

Beste Grüße
Mathematiker

@Mathematiker:
Gibt es eigentlich noch Tipps zum Fahnenschwenker?
Teil 1 war ja einfach, aber dann
So was ist mir noch nicht untergekommen, was ist das?

ub60

Hallo,

ub60 hat folgendes geschrieben :

Gibt es eigentlich noch Tipps zum Fahnenschwenker? ... So was ist mir noch nicht untergekommen, was ist das?

Die Figur "winkt" mit den Fahnen einige Zeichen aus einem internationalen "Alphabet".

Beste Grüße
Mathematiker

Nachtrag:
Da Rätsel offensichtlich gern willkommen sind, habe ich noch eins, das nicht mehr in den Adventskalender passte:

Wie alt ist Knobelix ?
Knobelix war ein Gallier, der zur gleichen Zeit wie Asterix und Obelix lebte und sich ebenso wie diese gern einen Spaß mit den Römern erlaubte.
Im Gegensatz zu Asterix und Obelix verprügelte er keine Römer, sondern stellte ihnen Knobelaufgaben, die sie meistens nicht lösen konnten. Das ärgerte die Römer.
Sie verhafteten Knobelix wegen Schlauheit und brachten ihn zum Richter. Damit ein ordnungsgemäßer Prozess stattfinden konnte, musste der Richter zunächst Namen, Wohnsitz und Alter des Verhafteten wissen. Knobelix nannte dem Richter seinen Namen (Knobelix) und seinen Wohnort (Lutetia). Sein Alter gab er dem Richter nur in Form des folgenden Rätsels an:

Waagerecht
I. Ist um CCXL kleiner als 1 senkrecht
II. Endet so, wie IV waagerecht beginnt
III. Quadratzahl
IV. Quadrat- und Kubikzahl
Senkrecht
I. Vielfaches von CCLXXV
II. Vielfaches von LV
III. XIII * XLVII
IV. Alter von Knobelix