Deutsch  English 

 

Was ist ein Kreuzzahlrätsel?

Kontakt/Impressum

Sie erreichen Rainer Typke, den Autor und Betreiber dieser Website, am besten per E-Mail:



Dr. Rainer Typke

Ilkantie 6

00400 Helsinki

 

Copyright/Raetselschema u. Loesung als PDF

Das Urheberrecht für alle Rätsel liegt bei den jeweiligen Autoren.

 

Möchten Sie Rätsel des Benutzers "rt" in Ihrer Zeitung abdrucken? Mit einem Premium-Abonnement können Sie PDF-Dateien der Rätsel-Schemata und Lösungen herunterladen. Bitte kontaktieren Sie Rainer Typke (Adresse: siehe oben) für weitere Informationen.

Andere Raetselseiten

Prof. William Sit ueber diese Website

Prof. William Sit von der City University New York schrieb einen sehr interessanten Artikel über Kreuzzahlrätsel, in dem auch diese Website erwähnt wird sowie die Rätsel-Typen, die sich damit lösen lassen. Ich zitiere aus seinem Artikel:

 

"Fortgeschrittene algebraische Rätsel mit Finite-Matching. In Rainer Typkes Kreuzzahlrätseln gibt es sowohl voneinander abhängige als auch unabhängige Aussagen, aber selbst für den erfahrenen Rätsel-Löser ist nicht erkennbar, wo man am besten beginnt (und vielleicht ist das auch grundsätzlich unklar), was sowohl das Lösen als auch das Schreiben dieser Rätsel schwieriger macht. In den Aussagen werden Potenzen (Quadrate und Kubikzahlen) verwendet, Primzahlen, vollkommene Zahlen, Fibonaccizahlen, Palindrome, Rückwerte, Quersummen und -produkte sowie einfache Arithmetik zur Verknüpfung von Aussagen, außerdem logische Operatoren und Ungleichungen. Diese Rätsel kombinieren also jeden Typ von Aussagen, die wir bisher betrachtet haben, und eine aussagekräftige Bezeichnung für sie ist vielleicht "fortgeschrittene algebraische Rätsel mit Finite-Matching", oder wir könnten sie, zu Ehren ihres Autors, einfach als Typke-Rätsel bezeichnen.

...

Typke hat eine systematische Lösungstechnik für Typke-Rätsel in der Form seines Kreuzzahlrätsellösers entwickelt und implementiert. Laut Typke wurde dieses Programm zunächst 1992 entwickelt und durch ihn beim Wettbewerb Jugend forscht präsentiert. Nach einigen Verbesserungen gewann das Programm zum Lösen von Kreuzzahlrätseln den zweiten Platz im Bundeswettbewerb 1994 und auch den Sonderpreis des Bundeskanzlers. Der Algorithmus hat sich seither nicht geändert, aber 2001–2002 packte Typke ihn in ein webbasiertes Programm.

Grob gesagt funktioniert der Algorithmus folgendermaßen: der Kreuzzahlrätsellöser initialisiert und verwaltet eine Liste aller möglichen Ziffern für jedes Kästchen. Diese Listen werden dann verkürzt, indem die Aussagen wiederholt in der Reihenfolge angewendet werden, in der sie eingegeben wurden. Dadurch könnten zum Beispiel erst alle Aussagen über waagerechte Zahlen angewendet werden, gefolgt durch alle Aussagen über senkrechte Zahlen; manchmal kann aber auch eine ausgeklügeltere Reihenfolge gewählt werden, z. B. für besonders große Rätsel aufgrund von Abhängigkeits-Bäumen. Wenn das Programm durch die Aussagen durchgeht, berechnet es als erstes, wieviel Arbeit eine neue Aussage durch das Ausprobieren aller möglichen in ihr vorkommenden Zahlen verursachen würde. Wenn dieser Aufwand über einem benutzerdefinierten Grenzwert (den Typke "Geduld" nennt) liegt, wird die Aussage zunächst nicht weiter beachtet, sondern stattdessen werden zuerst alle anderen Aussagen betrachtet. Danach, wenn die Aussage erneut in Betracht gezogen wird, ist möglicherweise schon mehr über die von ihr abgedeckten Ziffern bekannt, und das könnte den Aufwand unter den Grenzwert drücken. Diese Art der Auswertung aller Aussagen wird wiederholt, bis entweder in jedem Kästchen nur noch eine einzige korrekte Ziffer steht, oder bis es keine Veränderung mehr gibt. Wenn keine Ziffernliste mehr reduziert werden kann, aber manche Listen noch mehr als eine Ziffer enthalten (eine Deadlock-Situation), wird eine der Ziffern in einem ausgewählten Kästchen angenommen, und der Reduktionsprozess wiederholt sich.

Die Strategie für die Auswahl eines solchen Kästchens muss wohlüberlegt sein, wobei sowohl der potentielle Nutzen für das Aufheben der Blockade als auch die Effizienz des Backtrackings wichtig sind. Es ist oft keine gute Idee, einfach ein Kästchen mit besonders wenigen übriggebliebenen Ziffern zu wählen, denn man kann leicht Beispiele für Rätsel finden, bei denen das keinen Nutzen hat und einfach nur die restliche Laufzeit des Algorithmus mit der Anzahl der Ziffern im ausgewählten Kästchen multipliziert. Typkes Algorithmus verwendet daher einige Zeit darauf, gute Kästchen für das Backtracking auszuwählen: in jedem Kästchen, in dem noch mehr als eine Ziffer übrig ist, wird eine Ziffer ausgewählt und dann geschaut, wie sehr sich danach durch die Auswertung aller Aussagen die Möglichkeiten weiter verringern lassen (in einer Art "Vorausschauen in die Zukunft"). Die Anzahl verbleibender Möglichkeiten vor und nach dem Auswählen eines Kästchens wird verglichen. Das geschieht für jedes Kästchen mit mehr als einer verbleibenden Ziffer, und das Kästchen, in dem die Auswahl einer einzelnen Ziffer zur größten Reduktion der Möglichkeiten geführt hat, wird letztlich ausgewählt. Diese Methode ist ein Kompromiss, in dem Effizienz und eine gute Entscheidung gegen einen ineffizienten, aber möglicherweise besseren Schritt eingetauscht wird, und bei dem die Auswahl von Kästchen, die zu keinem neuen Erkenntnisgewinn führen und dadurch Zeit verschwenden, vermieden wird. Da die Gesamtzahl der Möglichkeiten nach jeder Auswahl fällt, terminiert der Algorithmus immer. Der Beweis, dass ein Algorithmus terminiert, ist einer der wichtigsten Aspekte des Entwurfs von Algorithmen.

Immer wenn beim Lösungsprozess eine Lösung oder eine Inkonsistenz gefunden wird, wird in einer fürs Backtracking ausgewählten Zelle die nächste mögliche Ziffer eingesetzt. Auf diese Art werden alle Lösungen (wenn es welche gibt) gefunden.

Besonders wichtig für Typkes Algorithmus sind die Algorithmen zum Ausschließen von Ziffern aufgrund von Aussagen, also das Umsetzen der Aussagen in Operationen auf den Ziffernlisten. Für einfache, unabhängige Aussagen ist das sehr einfach, denn man kann schlicht die eindeutige Antwort berechnen. Für Eigenschaften wie "Primzahl", "Quadratzahl", "Fibonaccizahl" oder "volllkommene Zahl" kann man die Menge aller möglichen Belegungen bestimmen und dann die Einschränkungen für jede Ziffer erkennen. Für ein Palindrom oder einen Rückwert kann man die Schnittmengen von Ziffernmengen bilden, die das Palindrom formen. Der Aktualisierungsalgorithmus für die algebraischen Aussagen ist wahrscheinlich der komplizierteste, aber oft ist es möglich, Einschränkungen für die erste oder letzte bisher unbekannte Ziffer zu finden. Der Hauptalgorithmus kann bestimmte Heuristiken verwenden wie z. B. das Verschieben der Auswertung einer allzu komplizierten Aussage in die nächste Iteration, oder den Übergang zu schlichtem Ausprobieren, wenn die Anzahl der verbliebenen Möglichkeiten unter eine gewisse Schwelle fällt.

In einem gewissen Maß kann man Typkes Algorithmus von Hand anwenden, zumindest für Rätsel, die eine vernünftige Größe nicht überschreiten. Für größere Rätsel, z. B. mit mehr als 9 × 9 Kästchen, wird diese Methode aber schnell mühsam. Es ist jedoch möglich, den Algorithmus zu verbessern, indem man nur die Ziffernmengen aktualisiert, die etwas mit Kästchen zu tun haben, die kürzlich verändert wurden. Bei der manuellen Anwendung der Methode ist also das Ziel, die nächsten Kästchen zu finden, für die die Anzahl der Möglichkeiten reduziert werden kann, und dann alle Kästchen zu bearbeiten, auf die das eine Auswirkung hat. In einem gut gemachten Rätsel sollte der Autor dafür gesorgt haben, dass ein solcher Pfad zur Lösung führt. Ich habe auf diese Weise viele der in Abschnitt 2 erwähnten Rätsel gelöst; diese Erfahrun erinnert mich an die "diagram-chasing technique", die für den Beweis des Kommutierens großer Diagramme in der homologischen Algebra verwendet wird!

Die Verwendung eines Computerprogramms zum Lösen von Kreuzzahlrätseln mag fragwürdig erscheinen, ist aber letztlich unvermeidbar. Um dem Leser einen Eindruck davon zu geben, was ein Computer in Sekundenbruchteilen tun kann, nehmen wir eine simple Aussage für eine vierstellige Zahl an: Eine Fibonaccizahl. Typkes Kreuzzahlrätsellöser grenzt die vier Ziffern a, b, c, d (a sei die Tausenderziffer usw.) sofort auf a ∈ { 1, 2, 4, 6 }, b ∈ { 1, 5, 7 }, c ∈ { 6, 8, 9 } und d ∈ { 1, 4, 5, 7 } ein. Wie wir später sehen werden, werden komplizierte Kreuzzahlrätsel oft mit Hilfe eines Computers konstruiert. Daher ist es nur gerecht, wenn Computer auch zum Lösen eingesetzt werden. Das Entwickeln eines eigenen Computerprogramms, selbst wenn es nur darum geht, eine einzige Aussage auszuwerten, kann eine lohnende Erfahrung sein, sowohl was die Mathematik anbelangt, als auch die Programmiersprache oder die verwendete Software.

Now, it is usually not possible to solve a crossnumber puzzle directly by entering the inter-relationships as equations with the answers to clues as unknowns into a computer algebra system such as Mathematica or Maple. First, the equations are constrained diophantine equations (the solutions are positive integers within a given range). Without a specially designed package, in general, these off-the-shelf systems will not be able to provide much additional information other than returning the same set of equations, perhaps with some trivial rearrangements of the variables. Second, the equations obtained from the clues are but one aspect of the puzzle. The layout of the grid and locations of the crossed cells provide critical information, too. To use this approach, one would have to treat the digit in each blank cell rather than the answer for each clue as an unknown. It is not easy to break a clue, say of multiplicative type y = ax, into clues for the digits of x and y. Finally, the finite-matching clues are also difficult to translate into equations. In my opinion, if one tries to carry this out, one would invariably be led to an algorithm similar to Typke’s described above.

A more formal analysis of Typke’s algorithm will lead us into constraint satisfaction problems, an active area of computer science research. ..."