Futoshiki
Futoshiki (japanisch 不等式 futōshiki, deutsch ‚Ungleichung‘) ist ein Logikrätsel in der Form des lateinischen Quadrats. Es wurde um 2001 in Japan entwickelt und seit 2006 durch den Guardian in Großbritannien verbreitet und bekannt gemacht.[1]
Wie bei dieser Rätselgattung üblich wird auf einem quadratischen Gitter gespielt. Ziel ist es, die Zahlen so zu platzieren, dass jede Zeile und Spalte nur exakt eine von jeder Ziffer enthält. Meist sind zu Beginn einige Ziffern angegeben. Die Besonderheit des Futoshiki sind die zwischen einigen Feldern platzierten Vergleichszeichen „<“ (Kleinerzeichen) und „>“ (Größerzeichen), die festlegen, dass der Wert des Feldes höher bzw. niedriger sein muss als der seines Nachbarn. Diese Ungleichheitsrelationen müssen zur Lösung des Rätsels berücksichtigt und somit am Ende alle erfüllt werden.
Lösungsstrategie Bearbeiten
Wie beim Sudoku gelten die Grundregeln des lateinischen Quadrats: Jede Zahl tritt in jeder Zeile und in jeder Spalte jeweils genau einmal auf. Dies schränkt die Anzahl der möglichen Werte für jede Position ein, ebenso wie die Ungleichungen.
Der erste Schritt zur Lösung des Rätsels besteht also darin, mögliche Werte aufzulisten, die auf Nicht-Duplizierung und Ungleichungen innerhalb von Zeilen und Spalten basieren. Dann kann die AB-Eliminierung sinnvoll sein, bei der Teilmengen innerhalb einer Zeile identifiziert werden, deren Wertebereich bestimmt werden kann. Wenn beispielsweise die ersten beiden Felder innerhalb einer Reihe 1 oder 2 enthalten müssen, dann können diese Zahlen von den restlichen Feldern ausgeschlossen werden. Ebenso, wenn die ersten drei Felder 1 oder 2; 1 oder 3; und 1 oder 2 oder 3 enthalten müssen, dann müssen die verbleibenden Felder andere Werte enthalten (4 und 5 in einem 5×5-Puzzle). Eine weitere wichtige Technik ist es, die Möglichkeiten offener Ungleichungen abzuarbeiten. Ein Wert auf der einen Seite einer Ungleichung schränkt den anderen ein. Beispielsweise kann sich auf der „größer als“-Seite niemals die 1 befinden, da sie das absolut kleinste Element im Rätsel darstellt. Eine Kette von Ungleichungen kann durch das Rätsel verfolgt werden, bis ein Widerspruch erreicht und somit ein Wert ausgeschlossen wird.
Literatur Bearbeiten
- Kazuya Haraguchi: The Number of Inequality Signs in the Design of Futoshiki Puzzle. In: Journal of Information Processing. Band 21, Nr. 1, 2013, S. 26–32, doi:10.2197/ipsjjip.21.26.
Weblinks Bearbeiten
Einzelnachweise Bearbeiten
- ↑ If you were seduced by sudoku, prepare for futoshiki fever. In: The Guardian. 30. September 2006, abgerufen am 19. Oktober 2019 (englisch).