... newer stories
Sudoku: Paare
wuerg, 16.09.2006 19:53
In den letzten Tagen begegneten mir Sudoku, in denen ich mit der Suche nach Einern nicht zum Ziel kam, die ich nur durch weitergehende Überlegungen lösen konnte. Und damit meine ich nicht so einfache Kombinationen wie in diesem Diagramm:
Im rechten Block kann die 3 weder in der ersten noch der dritten Zeile stehen, muß also in der mittleren Platz finden, wodurch die dritte 3 des 3×9‑Streifens nicht nur im linken Block, sondern auch in der ersten Zeile stehen muß, wo aber nur noch das mit einem Punkt bezeichnete Feld bleibt.
Warum ist diese Überlegung nach meinen Erläuterungen über Einer zwar neu, aber nicht erforderlich? Weil es sich bei der gefundenen 3 einfach um einen versteckten Einer in der ersten Zeile handelt, denn in dreien der vier freien Felder ist die 3 nicht mehr möglich, weil sie im mittleren Block bereits vergeben ist. Trotzdem ist die neue Überlegung nicht überflüssig, weil sie oftmals schneller ins Auge springt, nebenbei abfällt oder einfacher ist.
Natürlich findet der Computer gerne von mir übersehene Einer, vor allem nackte. Und so tröstet es mich, daß in diesem Sudoku [1]
Hätte ich nicht zum Zwecke der Analyse an dieser Stelle den Computer bemüht, würde ich eher ein verstecktes Paar gesucht haben. Das sind zwei Ziffern, die in einer Zeile, Spalte oder in einem Block genau zweimal vorkommen, und zwar in den gleichen beiden Feldern. Da darin neben diesen zwei Ziffern in der Regel noch weitere möglich sind (sonst wäre es zugleich ein nacktes Paar), werden sie über die Buchhaltermethode nur schwer gesehen. Deshalb empfielt es sich, vorzugsweise in stark besetzten Zeilen, Spalten oder Blöcken nach fehlenden Ziffern in der Hoffnung Ausschau zu halten, daß sie bis auf zwei in allen Feldern ausscheiden. Das liefert kein Paar, aber einen Zweier, also einzelne Ziffern in nur zwei Feldern. Auch wenn man sich nur solche innerhalb eines Blockes merkt, so geschieht es doch häufig, daß ein weiterer Zweier für die gleichen Felder entdeckt wird und so ein Paar entsteht.
Langer Rede kurzer Sinn: Mir hätte auffallen können, daß 2 und 6 in Spalte 4 des Blockes 2 und auch in der Spalte 5 des Blockes 8 stehen, weshalb ihnen im Block 5 nur die 6. Spalte bleibt. Eines dieser drei Felder ist besetzt, weshalb das versteckte Paar 2/6 in den beiden verbleibenden stehen muß.
Bleibt nur noch eine Frage zu klären: Wie finde ich das 2/6‑Paar, zumal ich doch nicht ohne weiteres sehe, daß 2 und 6 in den Spalten 4 und 5 bereits im oberen und im unteren Block vorkommen? Die Antwort ist einfach: Es wird eine Ziffer n nach der anderen betrachtet, und es werden (im Geiste) alle Zeilen, Spalten und Blöcke geschwärzt, in denen diese Ziffer steht, zusätzlich auch alle bereits belegten Felder. Bleibt ein einzelnes weißes Feld in einer Zeile, Spalte oder Block, ist an dieser Stelle ein Einer n entdeckt. Dort wird die ausgewählte Ziffer notiert und sodann weiter geschwärzt. Dieser Prozeß ist zu wiederholen, bis keine Einer n mehr gefunden werden. Sodann werden Zweier gesucht, also Felder, die in einer Zeile, einer Spalte oder einem Block genau zweimal n als noch möglichen Kandidaten aufweisen. Auch wenn sie direkt nichts nützen, sollten sie zumindest dann notiert werden, wenn sie sich in einem gemeinsamen Block befinden [3], besonders wenn sie darin waagerecht oder senkrecht liegen und in ihre Zeile bzw. Spalte ausstrahlen (pointing pair), daß darin alle weiteren n gestrichen werden können. Im Glücksfalle wurde bereits ein Zweier zu einer anderen Zahl m an der gleichen Stelle gefunden. Dann steht dort ein m/n‑Paar mit allen seinen Konsequenzen. Möglicherweise können nun weitere Einer zu finden sein.
Normalerweise gehe ich zu Beginn stur alle Ziffern von 1 bis 9 durch, beginne auch teilweise wieder von vorne, wenn es erfolgversprechend aussieht. Das hier betrachtete Sudoku sieht nach Abarbeitung der Ziffern 1 bis 6 wie folgt aus:
[1] .6725...8.2..........61..5.3........2.4..581....8..43..32..89..7.1.2...5....6.3..
[2] Andrew Stuart: Sudoku Solver.
[3] Wenn die beiden Felder eines Zweiers sich berühren, schreibe ich die Ziffer auf die gemeinsame Kante bzw. Ecke. Ansonsten zeichne ich eine Verbindungslinie und beschrifte sie mit der Ziffer des Zweiers. Am Computer werden solche Zweier (oder auch Dreier) gerne in eine Ecke der Felder geschrieben, weshalb sie zur eindeutigen Interpretation alle in einem Block liegen sollten. Auch ich verzichte fast immer auf blockübergreifende Verbindungen, da sie normalerweise auch nicht viel bringen.
Anfang | Einer | Raster | Stufen
┏━━━┯━━━┯━━━┳━━━┯━━━┯━━━┳━━━┯━━━┯━━━┓ ┃ 1 │ 2 │ ⋅ ┃ │ │ ┃ 4 │ 5 │ 6 ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ │ │ ┃ │ │ ┃ │ │ ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ │ │ ┃ │ │ 3 ┃ │ │ ┃ ┗━━━┷━━━┷━━━┻━━━┷━━━┷━━━┻━━━┷━━━┷━━━┛[Da hier Tabllen nicht mehr dargestellt werden, habe ich Diagramme mit Unicode-Rahmenzeichen erstellt, die immer noch nicht von allen Browsern korrekt angezeigt werden. Die Arbeit mit Bildern erspare ich mir, egal ob scharf und verlinkt oder verwaschen und direkt hier eingefügt.]
Im rechten Block kann die 3 weder in der ersten noch der dritten Zeile stehen, muß also in der mittleren Platz finden, wodurch die dritte 3 des 3×9‑Streifens nicht nur im linken Block, sondern auch in der ersten Zeile stehen muß, wo aber nur noch das mit einem Punkt bezeichnete Feld bleibt.
Warum ist diese Überlegung nach meinen Erläuterungen über Einer zwar neu, aber nicht erforderlich? Weil es sich bei der gefundenen 3 einfach um einen versteckten Einer in der ersten Zeile handelt, denn in dreien der vier freien Felder ist die 3 nicht mehr möglich, weil sie im mittleren Block bereits vergeben ist. Trotzdem ist die neue Überlegung nicht überflüssig, weil sie oftmals schneller ins Auge springt, nebenbei abfällt oder einfacher ist.
Natürlich findet der Computer gerne von mir übersehene Einer, vor allem nackte. Und so tröstet es mich, daß in diesem Sudoku [1]
┏━━━┯━━━┯━━━┳━━━┯━━━┯━━━┳━━━┯━━━┯━━━┓ ┃ │ 6 │ 7 ┃ 2 │ 5 │ ┃ │ │ 8 ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ │ 2 │ ┃ │ │ ┃ │ │ ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ │ │ ┃ 6 │ 1 │ ┃ │ 5 │ ┃ ┣━━━┿━━━┿━━━╋━━━┿━━━┿━━━╋━━━┿━━━┿━━━┫ ┃ 3 │ │ ┃ │ │ ┃ │ │ ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ 2 │ │ 4 ┃ │ │ 5 ┃ 8 │ 1 │ ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ │ │ ┃ 8 │ │ ┃ 4 │ 3 │ ┃ ┣━━━┿━━━┿━━━╋━━━┿━━━┿━━━╋━━━┿━━━┿━━━┫ ┃ │ 3 │ 2 ┃ │ │ 8 ┃ 9 │ │ ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ 7 │ │ 1 ┃ │ 2 │ ┃ │ │ 5 ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ │ │ ┃ │ 6 │ ┃ 3 │ │ ┃ ┗━━━┷━━━┷━━━┻━━━┷━━━┷━━━┻━━━┷━━━┷━━━┛ein fast menschlich vorgehendes Programm [2], das ebenfalls zunächst nach Einern sucht, 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 ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ │ │ ┃ 8 │ │ ┃ 4 │ 3 │ ┃ ┣━━━┿━━━┿━━━╋━━━┿━━━┿━━━╋━━━┿━━━┿━━━┫ ┃ 6 │ 3 │ 2 ┃ 5 │ │ 8 ┃ 9 │ │ ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ 7 │ │ 1 ┃ 3 │ 2 │ ┃ 6 │ │ 5 ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ │ │ ┃ │ 6 │ ┃ 3 │ │ ┃ ┗━━━┷━━━┷━━━┻━━━┷━━━┷━━━┻━━━┷━━━┷━━━┛Irgendwann hätte ich eine Fortsetzung gefunden, und sei es durch Fallunterscheidung, habe aber aufgegeben, weil ich unbedingt wissen wollte, ob der Computer an dieser Stelle weitere Einer findet. Das war nicht der Fall, weshalb er zu Paaren überging. Das sind zwei Felder einer Zeile, einer Spalte oder eines Blockes, in denen nur zwei Ziffern möglich sind, und zwar in beiden Feldern die gleichen. Von diesen Paaren (rot) fand er zwei. Zum einen 4/9 in den Zeilen 2 und 8 der Spalte 6 mit der roten nackten 1 als Konsequenz. Zum anderen 7/9 (rot )an den Positionen 4 und 8 des mittleren Blockes, woraus sich darin eine rote nackte 4 ergibt. Direkte Folge ist die versteckte blaue 1 in diesem Block und ein ebenfalls blaues 2/6‑Paar, das sich auch ergäbe, fielen einem 2 und 6 in den Spalten 4 und 5 auf. Damit ist das Sudoku so gut wie gelöst:
┏━━━┯━━━┯━━━┳━━━┯━━━┯━━━┳━━━┯━━━┯━━━┓ ┃ │ 6 │ 7 ┃ 2 │ 5 │ 3 ┃ 1 │ │ 8 ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ 1 │ 2 │ 5 ┃ │ 8 │4/9┃ 7 │ 6 │ 3 ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ │ │ 3 ┃ 6 │ 1 │ 7 ┃ 2 │ 5 │ ┃ ┣━━━┿━━━┿━━━╋━━━┿━━━┿━━━╋━━━┿━━━┿━━━┫ ┃ 3 │ │ ┃ 1 │ 4 │2/6┃ 5 │ │ ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ 2 │ │ 4 ┃7/9│ 3 │ 5 ┃ 8 │ 1 │ 6 ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ │ │ ┃ 8 │7/9│2/6┃ 4 │ 3 │ ┃ ┣━━━┿━━━┿━━━╋━━━┿━━━┿━━━╋━━━┿━━━┿━━━┫ ┃ 6 │ 3 │ 2 ┃ 5 │ │ 8 ┃ 9 │ │ ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ 7 │ │ 1 ┃ 3 │ 2 │4/9┃ 6 │ │ 5 ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ │ │ ┃ │ 6 │ 1 ┃ 3 │ │ ┃ ┗━━━┷━━━┷━━━┻━━━┷━━━┷━━━┻━━━┷━━━┷━━━┛Nackte Paare wie 7/9 und 4/9 sind für Menschen mitunter schwer zu sehen, wenn man nicht buchhalterisch und leider auch zeitraubend vorgeht, in den leeren Feldern alle noch möglichen Ziffern notiert und sich sodann anschaut, in welchen nur noch zwei stehen. Ist es das gleiche Paar innerhalb einer Zeile, Spalte oder einem Block, so hat man dieses nackte Paar gefunden, woraufhin in dieser Zeile, Spalte oder diesem Block an anderen Stellen diese beiden Ziffern gestrichen werden können.
Hätte ich nicht zum Zwecke der Analyse an dieser Stelle den Computer bemüht, würde ich eher ein verstecktes Paar gesucht haben. Das sind zwei Ziffern, die in einer Zeile, Spalte oder in einem Block genau zweimal vorkommen, und zwar in den gleichen beiden Feldern. Da darin neben diesen zwei Ziffern in der Regel noch weitere möglich sind (sonst wäre es zugleich ein nacktes Paar), werden sie über die Buchhaltermethode nur schwer gesehen. Deshalb empfielt es sich, vorzugsweise in stark besetzten Zeilen, Spalten oder Blöcken nach fehlenden Ziffern in der Hoffnung Ausschau zu halten, daß sie bis auf zwei in allen Feldern ausscheiden. Das liefert kein Paar, aber einen Zweier, also einzelne Ziffern in nur zwei Feldern. Auch wenn man sich nur solche innerhalb eines Blockes merkt, so geschieht es doch häufig, daß ein weiterer Zweier für die gleichen Felder entdeckt wird und so ein Paar entsteht.
Langer Rede kurzer Sinn: Mir hätte auffallen können, daß 2 und 6 in Spalte 4 des Blockes 2 und auch in der Spalte 5 des Blockes 8 stehen, weshalb ihnen im Block 5 nur die 6. Spalte bleibt. Eines dieser drei Felder ist besetzt, weshalb das versteckte Paar 2/6 in den beiden verbleibenden stehen muß.
┏━━━┯━━━┯━━━┳━━━┯━━━┯━━━┳━━━┯━━━┯━━━┓ ┃ │ 6 │ 7 ┃ 2 │ 5 │ 3 ┃ 1 │ │ 8 ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ 1 │ 2 │ 5 ┃ │ 8 │ ┃ 7 │ 6 │ 3 ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ │ │ 3 ┃ 6 │ 1 │ 7 ┃ 2 │ 5 │ ┃ ┣━━━┿━━━┿━━━╋━━━┿━━━┿━━━╋━━━┿━━━┿━━━┫ ┃ 3 │ │ ┃ 1 │ 4 │2/6┃ 5 │ │ ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ 2 │ 9 │ 4 ┃ 7 │ 3 │ 5 ┃ 8 │ 1 │ 6 ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ │ │ ┃ 8 │ 9 │2/6┃ 4 │ 3 │ ┃ ┣━━━┿━━━┿━━━╋━━━┿━━━┿━━━╋━━━┿━━━┿━━━┫ ┃ 6 │ 3 │ 2 ┃ 5 │ 7 │ 8 ┃ 9 │ 4 │ 1 ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ 7 │ │ 1 ┃ 3 │ 2 │ ┃ 6 │ │ 5 ┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼───┨ ┃ │ │ ┃ │ 6 │ ┃ 3 │ │ ┃ ┗━━━┷━━━┷━━━┻━━━┷━━━┷━━━┻━━━┷━━━┷━━━┛Sofort ergibt sich erst die versteckte 1, danach die versteckte 4 im mittleren Block, gefolgt von der versteckten 9 in Spalte 5. Im Anschluß purzeln die roten Siebener. Damit ist das 7/9‑Paar im mittleren Block aufgelöst, ohne es vorher als nacktes Paar bemerkt zu haben. Und wegen 1 und 4 in Zeile 7 fallen alle Vieren und Neunen des gesamten Diagramms. Die zahlreichen 4/9‑Paare sind also ebenfalls aufgelöst, ohne sie zuvor gesehen haben zu müssen.
Bleibt nur noch eine Frage zu klären: Wie finde ich das 2/6‑Paar, zumal ich doch nicht ohne weiteres sehe, daß 2 und 6 in den Spalten 4 und 5 bereits im oberen und im unteren Block vorkommen? Die Antwort ist einfach: Es wird eine Ziffer n nach der anderen betrachtet, und es werden (im Geiste) alle Zeilen, Spalten und Blöcke geschwärzt, in denen diese Ziffer steht, zusätzlich auch alle bereits belegten Felder. Bleibt ein einzelnes weißes Feld in einer Zeile, Spalte oder Block, ist an dieser Stelle ein Einer n entdeckt. Dort wird die ausgewählte Ziffer notiert und sodann weiter geschwärzt. Dieser Prozeß ist zu wiederholen, bis keine Einer n mehr gefunden werden. Sodann werden Zweier gesucht, also Felder, die in einer Zeile, einer Spalte oder einem Block genau zweimal n als noch möglichen Kandidaten aufweisen. Auch wenn sie direkt nichts nützen, sollten sie zumindest dann notiert werden, wenn sie sich in einem gemeinsamen Block befinden [3], besonders wenn sie darin waagerecht oder senkrecht liegen und in ihre Zeile bzw. Spalte ausstrahlen (pointing pair), daß darin alle weiteren n gestrichen werden können. Im Glücksfalle wurde bereits ein Zweier zu einer anderen Zahl m an der gleichen Stelle gefunden. Dann steht dort ein m/n‑Paar mit allen seinen Konsequenzen. Möglicherweise können nun weitere Einer zu finden sein.
Normalerweise gehe ich zu Beginn stur alle Ziffern von 1 bis 9 durch, beginne auch teilweise wieder von vorne, wenn es erfolgversprechend aussieht. Das hier betrachtete Sudoku sieht nach Abarbeitung der Ziffern 1 bis 6 wie folgt aus:
┏━━━┯━━━┯━━━┳━━━┯━━━┯━━━┳━━━┯━━━┯━━━┓ ┃ │ 6 │ 7 ┃ 2 │ 5 │ 3 ┃ │ │ 8 ┃ ┠─1─┼───┼───╂───┼───┼───╂─1─┼───┼───┨ ┃ 5┼─2─┼5 ┃ │ │ ┃ 6 │ ┃ ┠───┼───┼─3─╂───┼───┼───╂───┼───┼─3─┨ ┃ │ │ ┃ 6 │ 1 │ ┃ 2┼─5─┼2 ┃ ┣━━━┿━━━┿━━━╋━━━┿━━━┿━━━╋━━━┿━━━┿━━━┫ ┃ 3 │ 1│ 6┃ │ │2 6┃ 5 │ │ ┃ ┠───┼──┼┼──┼╂───┼───┼┼─┼╂───┼───┼───┨ ┃ 2 │ ││ 4│┃ │ 3 ││5│┃ 8 │ 1 │ 6 ┃ ┠───┼──┼┼──┼╂───┼───┼┼─┼╂───┼───┼───┨ ┃ │ 1│ 6┃ 8 │ │2 6┃ 4 │ 3 │ ┃ ┣━━━┿━━━┿━━━╋━━━┿━━━┿━━━╋━━━┿━━━┿━━━┫ ┃ 6 │ 3 │ 2 ┃ 5 │ │ 8 ┃ 9 │ │ 1┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼──┼┨ ┃ 7 │ │ 1 ┃ 3 │ 2 │ ┃ 6 │ 5│┃ ┠───┼───┼───╂───┼───┼───╂───┼───┼──┼┨ ┃ │ │ ┃ │ 6 │ ┃ 3 │ 2 1┃ ┗━━━┷━━━┷━━━┻━━━┷━━━┷━━━┻━━━┷━━━┷━━━┛Normalerweise würde ich auch die verbleibenden Ziffern 7 bis 9 auf Einer und Zweier überprüfen. Dadurch aber würde mein Bild überladen, und es ist auch nicht erforderlich, denn nunmehr ist im mittleren Block ein Paar gefunden, das der 1 und der 4 ihren Platz darin zuweist. Die restlichen beiden bilden ein 7/9‑Paar, das aber gar nicht beachtet werden muß, denn nun kommt man wie zuvor dargelegt mit Einern ans Ziel.
[1] .6725...8.2..........61..5.3........2.4..581....8..43..32..89..7.1.2...5....6.3..
[2] Andrew Stuart: Sudoku Solver.
[3] Wenn die beiden Felder eines Zweiers sich berühren, schreibe ich die Ziffer auf die gemeinsame Kante bzw. Ecke. Ansonsten zeichne ich eine Verbindungslinie und beschrifte sie mit der Ziffer des Zweiers. Am Computer werden solche Zweier (oder auch Dreier) gerne in eine Ecke der Felder geschrieben, weshalb sie zur eindeutigen Interpretation alle in einem Block liegen sollten. Auch ich verzichte fast immer auf blockübergreifende Verbindungen, da sie normalerweise auch nicht viel bringen.
Anfang | Einer | Raster | Stufen
... link (4 Kommentare) ... comment
... older stories
