... newer stories
Sudoku, Teil 3
wuerg, 16.09.2006 19:53
In den letzten Tagen begegneten mir Sudoku, bei denen meine im Teil 2 dargestellten Methoden versagten, die ich nur durch weitergehende Überlegungen lösen konnte. Und damit meine ich nicht so einfache Kombinationen wie in diesem Diagramm:
Grundsätzlich ist diese Vorgehensweise nicht neu. Es werden alle zulässigen Kombinationen innerhalb eines Blockes, einer Zeile oder einer Spalte in der Hoffnung überprüft, auf irgendwelche Beziehungen zu stoßen. Im Teil 2 betrachtete ich ein einfaches Beispiel:
Normalerweise gibt es eine solche eindeutige Kombination nicht, man sucht auch nicht ewig nach ihr, sondern betrachtet nur die Zeilen und Spalten der Matrix, in der sich nur ein o befindet. Das sind die nackten Einer (rot) oder die versteckten Einer (grün). Hier nun die aktuelle Lage im mittleren Block:
Für einen Menschen ist es mühsam, alle verbleibenden Möglichkeiten zu finden, und für den Computer (besser: den Pogrammierer) ist es schwer, daraus die einfachen Schlußfolgerungen zu ziehen. Deshalb suchen beide lieber nackte oder versteckte Paare. Ein nacktes Paar bezieht sich auf zwei Felder, in denen nur zwei gemeinsame Ziffern möglich sind. Hier sind es die Felder D und E mit den Ziffern 7 und 9. Ein verstecktes Paar wird aus zwei Ziffern gebildet, die nur in zwei gemeinsamen Felder vorkommen können. Hier sind es die Zifern 2 und 6 in den Feldern C und F.
Was hat man davon? Der Computer sieht solche nackten Paare leidenschaftlos und entfernt die beiden Ziffern, wo sie nunmehr nicht mehr vorkommen können. Ob ihm diese Streichung etwas einträgt oder nicht, interessiert ihn nicht. Doch hier stellt er im nächsten Schritt im Feld B eine 4 als nackten Einer fest. Die Folge ist eine 1 als nackter Einer in Feld A. Die restlichen vier Felder bleiben erst einmal offen. Auch der Rest des Sudoku wird mit den üblichen Einer-Methoden bewältigt.
Im Gegensatz zum Computer oder Buchhalter liegt es mir oder gar den meisten Menschen mehr, die versteckten Paare zu finden. Man geht einfach alle noch möglichen Ziffern durch, und wenn eine davon nur in zwei Felder paßt, dann merkt man sich diese oder malt die Ziffer zwischen die Felder, notfalls an eine Verbindungslinie. Ein Glücksfall ist eine zweite Ziffer mit den gleichen Feldern. Dann hat man einen verstecktes Paar gefunden.
Der Nutzen ist im Prinzip der gleiche wie beim Einer: Wenn beide Felder eines Paares in einem zu überprüfenden Objekt vorkommen, liefern sie die gleichen Beschränkungen wie zwei Einer. Doch wie findet man solche (versteckten) Paare? Normalerweise beim Abgrasen aller Blöcke, Zeilen und Spalten nach Ziffern, die nur noch zwei Felder haben. Das ist jedoch recht mühsam, und besser nutzt man Besonderheiten: Im aktuellen Beispiel kommen die Ziffern 2 und 6 in der linken und der mittleren Spalte bereits vor. Im Block bleibt für sie deshalb nur die rechte Spalte, wo aber nur zwei Felder frei sind.
Und wie geht es dann weiter? Ganz allgemeinen ist ein Paar eine nützliche Information für später. Oft sind es zwei Felder, die sowohl in einem gemeinsamen Block als auch in einer gemeinsamen Zeile oder Spalte liegen, so daß es direkt zu weiteren Schlüssen kommen kann. Und manchmal hat man Glück, wie im aktuellen Beispiel. Durch 2 und 6 in den Feldern C und F findet die 1 nur noch in Feld A Platz. Sitzt sie dort bleibt der 4 nur Feld B. Und schon ist man mit dem versteckten Paar genauso weit wie der Computer mit dem nackten, das man als Mensch dann natürlich auch schnell findet.
Mit dieser leicht fortgeschrittenen Überlegung gibt es in der Folge keine Probleme mehr:
Teil 2: Einer
Teil 3: Paare
Teil 4: Raster
+-------+-------+-------+ | 1 2 # | . . . | 4 5 6 | | . . . | . . . | . . . | | . . . | . 3 . | . . . | +-------+-------+-------+Im rechten Block kann die 3 nur in der mittleren Zeile stehen, womit im linken Block für die 3 nur noch die mit # bezeichnete Postion bleibt. Das hätte auch eine vollständige Überprüfung der ersten Zeile (blaue Methode) erbracht. Natürlich fand der Computer oftmals von mir übersehene einfache Lösungen, doch nicht immer. Und es tröstet mich, daß in diesem Sudoku
+-------+-------+-------+ | . 6 7 | 2 5 . | . . 8 | | . 2 . | . . . | . . . | | . . . | 6 1 . | . 5 . | +-------+-------+-------+ | 3 . . | . . . | . . . | | 2 . 4 | . . 5 | 8 1 . | [1] | . . . | 8 . . | 4 3 . | +-------+-------+-------+ | . 3 2 | . . 8 | 9 . . | | 7 . 1 | . 2 . | . . 5 | | . . . | . 6 . | 3 . . | +-------+-------+-------+der Computer an der gleichen Stelle ins Grübeln kam wie ich:
+-------+-------+-------+ | . 6 7 | 2 5 3 | 1 . 8 | | 1 2 5 | . 8 . | 7 6 3 | | . . 3 | 6 1 7 | 2 5 . | +-------+-------+-------+ | 3 . . | . . . | 5 . . | | 2 . 4 | . 3 5 | 8 1 6 | [2] | . . . | 8 . . | 4 3 . | +-------+-------+-------+ | 6 3 2 | 5 . 8 | 9 . 1 | | 7 . 1 | 3 2 . | 6 . 5 | | . . . | . 6 . | 3 . . | +-------+-------+-------+Irgendwann hätte ich eine Fortsetzung gefunden, und sei es durch Fallunterscheidung, habe aber aufgegegeben, weil ich unbedingt wissen wollte, ob der Computer an dieser Stelle noch eine einfache Kombination findet. Auch er kam mit den Methoden des 2. Teils nicht weiter, fand aber zwei sogenannte nackte Paare, eines davon im mittleren Block, obwohl darin gemeinerweise nur drei Ziffern stehen:
| 2 6 | 5 8 1 | 3 7 | --+-------+-------+-------+-- | 1 | | 1 2 | 3 | 4 | 4 | 4 6 | 5 | 7 9 | 7 9 | 9 | --+-------+-------+-------+-- 2 | | +---+ | +---+ | 8 | | | 3 | | | 5 | | 1 4 | 7 9 | +---+ | +---+ | 6 --+-------+-------+-------+-- | +---+ | | 1 2 | 4 | | 8 | | | 6 | | +---+ | 7 9 | 9 | 3 --+-------+-------+-------+-- | 5 3 | 2 6 | 8 |Zweimal nackt (rot) stehen 7 und 9 unten links und müssen in der einen oder anderen Weise diese beiden Felder füllen, daß sie in den anderen Stellen (grün) nicht mehr vorkommen können, wo die kleinen 7 und 9 also gestrichen werden können. Und nicht immer hat man Glück wie hier, denn danach steht die 4 (blau) allein nackt da, und man ist einen Schritt weiter.
Grundsätzlich ist diese Vorgehensweise nicht neu. Es werden alle zulässigen Kombinationen innerhalb eines Blockes, einer Zeile oder einer Spalte in der Hoffnung überprüft, auf irgendwelche Beziehungen zu stoßen. Im Teil 2 betrachtete ich ein einfaches Beispiel:
| . 8 . | | . 4 . | | 2 4 5 7 8 | | ----+-------+---- --+---------- --+-------+-- 3 5 | A B C | 4 . A | . . . o . | 7 2 8 | . 2 | 1 3 9 | 8 . B | o . . o . | 1 3 9 | . 9 | 6 D E | 3 . C | o . . . o | 6 5 4 | ----+-------+---- D | o . o o . --+-------+-- | 2 . 7 | E | o o . . o | | | 8 . 5 |Die fetten schwarzen Ziffern waren vorgegeben, die freien Felder sind mit A bis E gekennzeichnet, und die Matrix in der Mitte gibt durch o wieder, welche Ziffer in welchem Feld noch möglich ist. Es gibt nur eine einzige Auswahl von fünf o, daß in jeder Zeile und Spalte genau eines steht. Sie ist blau hervorgehoben.
Normalerweise gibt es eine solche eindeutige Kombination nicht, man sucht auch nicht ewig nach ihr, sondern betrachtet nur die Zeilen und Spalten der Matrix, in der sich nur ein o befindet. Das sind die nackten Einer (rot) oder die versteckten Einer (grün). Hier nun die aktuelle Lage im mittleren Block:
| . 5 . | | 2 8 3 | | 6 1 7 | | 1 2 4 6 7 9 möglich ----+-------+------ --+---------------------- . 3 | A B C | 5 . . A | o . o . o o 1 1 1 1 2 4 | D 3 5 | 8 1 6 B | . . o . o o 4 4 4 4 . . | 8 E F | 4 3 . C | o o o o . o 2 2 6 6 ----+-------+------ D | . . . . o o 7 9 7 9 | 5 2 8 | E | . . . . o o 9 7 9 7 | 3 6 . | F | o o . o . o 6 6 2 2Diesmal gibt es keine eindeutige Lösung für den ganzen Block, vielmehr bleiben vier Möglichkeiten, die rechts dargestellt sind. Man erkennt sofort A=1 und B=4. Daß sich 7 und 9 die Felder D und E sowie 2 und 6 die Felder C und F teilen, muß man nicht unbedingt im Kopf behalten, denn mit A=1 und B=4 geht es an anderer Stelle weiter.
Für einen Menschen ist es mühsam, alle verbleibenden Möglichkeiten zu finden, und für den Computer (besser: den Pogrammierer) ist es schwer, daraus die einfachen Schlußfolgerungen zu ziehen. Deshalb suchen beide lieber nackte oder versteckte Paare. Ein nacktes Paar bezieht sich auf zwei Felder, in denen nur zwei gemeinsame Ziffern möglich sind. Hier sind es die Felder D und E mit den Ziffern 7 und 9. Ein verstecktes Paar wird aus zwei Ziffern gebildet, die nur in zwei gemeinsamen Felder vorkommen können. Hier sind es die Zifern 2 und 6 in den Feldern C und F.
Was hat man davon? Der Computer sieht solche nackten Paare leidenschaftlos und entfernt die beiden Ziffern, wo sie nunmehr nicht mehr vorkommen können. Ob ihm diese Streichung etwas einträgt oder nicht, interessiert ihn nicht. Doch hier stellt er im nächsten Schritt im Feld B eine 4 als nackten Einer fest. Die Folge ist eine 1 als nackter Einer in Feld A. Die restlichen vier Felder bleiben erst einmal offen. Auch der Rest des Sudoku wird mit den üblichen Einer-Methoden bewältigt.
Im Gegensatz zum Computer oder Buchhalter liegt es mir oder gar den meisten Menschen mehr, die versteckten Paare zu finden. Man geht einfach alle noch möglichen Ziffern durch, und wenn eine davon nur in zwei Felder paßt, dann merkt man sich diese oder malt die Ziffer zwischen die Felder, notfalls an eine Verbindungslinie. Ein Glücksfall ist eine zweite Ziffer mit den gleichen Feldern. Dann hat man einen verstecktes Paar gefunden.
Der Nutzen ist im Prinzip der gleiche wie beim Einer: Wenn beide Felder eines Paares in einem zu überprüfenden Objekt vorkommen, liefern sie die gleichen Beschränkungen wie zwei Einer. Doch wie findet man solche (versteckten) Paare? Normalerweise beim Abgrasen aller Blöcke, Zeilen und Spalten nach Ziffern, die nur noch zwei Felder haben. Das ist jedoch recht mühsam, und besser nutzt man Besonderheiten: Im aktuellen Beispiel kommen die Ziffern 2 und 6 in der linken und der mittleren Spalte bereits vor. Im Block bleibt für sie deshalb nur die rechte Spalte, wo aber nur zwei Felder frei sind.
Und wie geht es dann weiter? Ganz allgemeinen ist ein Paar eine nützliche Information für später. Oft sind es zwei Felder, die sowohl in einem gemeinsamen Block als auch in einer gemeinsamen Zeile oder Spalte liegen, so daß es direkt zu weiteren Schlüssen kommen kann. Und manchmal hat man Glück, wie im aktuellen Beispiel. Durch 2 und 6 in den Feldern C und F findet die 1 nur noch in Feld A Platz. Sitzt sie dort bleibt der 4 nur Feld B. Und schon ist man mit dem versteckten Paar genauso weit wie der Computer mit dem nackten, das man als Mensch dann natürlich auch schnell findet.
Mit dieser leicht fortgeschrittenen Überlegung gibt es in der Folge keine Probleme mehr:
+-------+-------+-------+ | . 6 7 | 2 5 3 | 1 . 8 | | 1 2 5 | . 8 . | 7 6 3 | | . . 3 | 6 1 7 | 2 5 . | +-------+-------+-------+ | 3 . . | 1 4 # | 5 . . | | 2 . 4 | . 3 5 | 8 1 6 | | . . . | 8 . # | 4 3 . | +-------+-------+-------+ | 6 3 2 | 5 . 8 | 9 . 1 | | 7 . 1 | 3 2 . | 6 . 5 | | . . . | . 6 . | 3 . . | +-------+-------+-------+Das Diagramm zeigt mit # das versteckte Paar aus 2 und 6 an. Es hat die rote 1 und die rote 4 zur Folge.
+-------+-------+-------+ | . 6 7 | 2 5 3 | 1 . 8 | | 1 2 5 | . 8 . | 7 6 3 | | . . 3 | 6 1 7 | 2 5 . | +-------+-------+-------+ | 3 . . | 1 4 # | 5 . . | | 2 9 4 | 7 3 5 | 8 1 6 | [3] | . . . | 8 9 # | 4 3 . | +-------+-------+-------+ | 6 3 2 | 5 7 8 | 9 4 1 | | 7 . 1 | 3 2 . | 6 . 5 | | . . . | . 6 1 | 3 . . | +-------+-------+-------+In der mittleren Spalte gibt es nur noch eine Lage für die fehlenden blauen Ziffern 7 und 9. Die rote 4, die rote 7 und die rote 9 sind direkte Folge, womit das nackte Paar ebenfalls aufgedeckt ist, obgleich es nie hätte gesehen werden müssen. Die blaue 1 hat keine andere Position in der sechsten Spalte mehr, was aber auch ohne das versteckte Paar nicht anders mehr ginge.
[1] .6725...8.2..........61..5.3........2. 4..581....8..43..32..89..7.1.2...5....6.3.. [2] .672531.8125.8.763..361725.3.....5..2. 4.35816...8..43.6325.89.17.132.6.5....6.3.. [3] .672531.8125.8.763..361725.3..14.5..29 4735816...89.43.6325789417.132.6.5....613..Teil 1: Anfang
Teil 2: Einer
Teil 3: Paare
Teil 4: Raster
... link (3 Kommentare) ... comment
... older stories