BUG+1: Warum muss das Rätsel genau eine Lösung haben?

Reicht eine einzige Zelle mit drei Kandidaten?

BUG+1 nutzt einen besonderen Zustand eines eindeutig lösbaren Rätsels, in dem fast alle leeren Zellen zwei Kandidaten haben. Doch das Muster „eine Zelle mit drei Kandidaten, alle anderen mit zwei“ reicht nicht aus. Du musst auch zählen, wie oft jede Zahl in den einzelnen Zeilen, Spalten und Blöcken als Kandidat vorkommt. Vor allem brauchst du die Voraussetzung, dass es genau eine Lösung gibt.

Eindeutigkeit ist eine zusätzliche Eigenschaft neben der Regel, dass jede Zeile, Spalte und jeder Block die Zahlen 1 bis 9 genau einmal enthält. Es kann mehrere vollständig ausgefüllte Raster geben, die all diese Regeln einhalten. Prüfe die Eindeutigkeit zuerst, wenn du ein Raster selbst eingegeben oder Vorgaben entfernt hast.

Voraussetzungen — Eindeutigkeit, Kandidatenzahlen und Häufigkeiten

1. Das aktuelle Raster muss genau eine Lösung haben. Auch zuvor eingetragene Zahlen und gestrichene Kandidaten müssen korrekt sein.
2. Genau eine leere Zelle muss exakt drei Kandidaten haben, jede andere leere Zelle exakt zwei.
3. Wenn du gedanklich eine Zahl aus der Zelle mit drei Kandidaten streichst, muss jede verbleibende Kandidatenzahl in jeder Zeile, Spalte und jedem Block, in dem sie vorkommt, genau zweimal vorkommen. Bereits eingetragene Zahlen kommen im jeweiligen Bereich nullmal als Kandidaten vor.
4. Vor dem Streichen kommt diese Zahl daher in der Zeile, Spalte und im Block der besonderen Zelle jeweils dreimal vor. Es reicht nicht, sie nur in einer Zeile oder Spalte dreimal zu zählen.

Ein Zustand, in dem jede leere Zelle zwei Kandidaten hat und die Kandidaten in ihren Bereichen jeweils zweimal vorkommen, heißt BUG. Hat dieser Zustand eine Lösung, gibt es durch Umkehren der Auswahl auch eine andere; er kann also nicht genau eine Lösung haben. Er kann auch unlösbar sein. In einem eindeutig lösbaren Raster darf dieser Zustand nicht bestehen bleiben. Deshalb trägst du den einen zusätzlichen Kandidaten, der das BUG-Muster aufbricht, in die besondere Zelle ein.

Beispiel — welcher Kandidat ist in r7c6 zusätzlich?

c1c2c3c4c5c6c7c8c9

r1r2r3r4r5r6r7r8r9

68

7

36

89

5

1

39

4

2

9

1

5

2

4

3

7

8

6

28

4

23

7

6

89

39

5

1

4

2

8

69

3

69

5

1

7

5

6

9

4

1

7

2

3

8

1

3

7

58

2

58

4

6

9

3

8

26

56

7

256

1

9

4

7

9

1

3

8

4

6

2

5

26

5

4

1

9

26

8

7

3

★

★ r7c6 hat die Kandidaten 2, 5, 6. Alle anderen leeren Zellen haben nur zwei Kandidaten. Zähle die Positionen der Zahl 6.

• Zeile 7: drei Zellen, r7c3, r7c4, r7c6.
• Spalte 6: drei Zellen, r4c6, r7c6, r9c6.
• Block 8: drei Zellen, r7c4, r7c6, r9c6.

Ohne die 6 in r7c6 bleiben in diesen drei Bereichen jeweils zwei mögliche Positionen der 6. Auch alle anderen Kandidaten kommen in ihren Bereichen jeweils null- oder zweimal vor. Für dieses Raster wurde mit Rückwärtssuche geprüft, dass es genau eine Lösung hat. Daher gilt r7c6=6. Eine 2 oder 5 wäre mit der Voraussetzung einer eindeutigen Lösung unvereinbar. Nach dem Eintragen streichst du die Kandidaten 6 in derselben Zeile, Spalte und demselben Block und kehrst zu den grundlegenden Methoden zurück.

Wann die Methode nicht gilt und häufige Fehler

• Du weißt nicht, wie viele Lösungen es gibt. Verwende diese Voraussetzung nur, wenn der Generator Eindeutigkeit garantiert oder sie gesondert geprüft wurde. BUG+1 im logischen Löser zu aktivieren, ist selbst keine Eindeutigkeitsprüfung.
• Mehrere Zellen haben drei Kandidaten. Dann sind die BUG+1-Bedingungen dieses Artikels nicht erfüllt.
• Die Kandidatenzahlen stimmen, ihre Häufigkeiten in den Bereichen aber nicht. Das ist kein BUG; du kannst den zusätzlichen Kandidaten nicht sicher eintragen.
• Du hast Kandidaten ausgelassen. Ein BUG-Muster aus fehlerhaften Notizen ist keine Begründung.
• Du glaubst, ein BUG müsse genau zwei Lösungen haben. Entscheidend ist hier nur, dass er nicht genau eine Lösung haben kann. Gibt es unabhängig veränderliche Teile, können es mehr Lösungen sein.

Gegenbeispiel mit mehreren Lösungen — dieselben Bedingungen legen die 8 nicht fest

c1c2c3c4c5c6c7c8c9

r1r2r3r4r5r6r7r8r9

8

7

6

9

5

1

3

4

2

9

1

5

2

4

3

78

78

6

2

4

3

7

6

8

9

5

1

4

2

8

6

3

9

5

1

7

5

6

9

4

1

7

2

38

38

1

3

7

8

2

5

4

6

9

3

8

2

5

7

6

1

9

4

7

9

1

3

8

4

6

2

5

6

5

4

1

9

2

78

378

38

★

Dieses Gegenbeispiel entstand, indem aus einem vollständig ausgefüllten Raster des Generators Vorgaben entfernt und anschließend logische Lösungsschritte angewandt wurden. r9c8 ist die einzige Zelle mit drei Kandidaten; die scheinbar zusätzliche Zahl ist 8. Sie kommt in Zeile 9 bei r9c7·r9c8·r9c9, in Spalte 8 bei r2c8·r5c8·r9c8 und in Block 9 bei r9c7·r9c8·r9c9 jeweils dreimal vor. Alle anderen Kandidaten kommen null- oder zweimal vor. Damit sind alle Kandidatenbedingungen für BUG+1 erfüllt, nur die Eindeutigkeit fehlt.

Die Prüfung der Lösungsanzahl ergibt jedoch mindestens 2; die Prüfung stoppt, sobald zwei gefunden sind. Aktivierst du BUG+1 ohne Eindeutigkeitsprüfung, schlägt der Löser r9c8=8 vor. Doch auch die folgenden beiden Vervollständigungen halten alle Zeilen-, Spalten- und Blockregeln ein. Die 8 ist also nicht zwingend. Außer den folgenden sieben Zellen bleiben alle Zahlen des Diagramms unverändert.

Leere Zelle	Vervollständigung A	Vervollständigung B
r2c7	7	8
r2c8	8	7
r5c8	3	8
r5c9	8	3
r9c7	8	7
r9c8	7	3
r9c9	3	8

r9c8 enthält in A die 7 und in B die 3. Der Schluss „r9c8 muss 8 sein“ ist also falsch. Es gibt auch eine Lösung mit 8, aber eine mögliche Lösung auszuwählen ist etwas anderes, als eine in allen Lösungen zwingende Zahl festzustellen. Dieses Gegenbeispiel scheitert tatsächlich an mehreren Lösungen; es ist kein durch fehlende Kandidaten vorgetäuschtes Muster.

Übung

c1c2c3c4c5c6c7c8c9

r1r2r3r4r5r6r7r8r9

8

24

39

49

7

6

23

5

1

1

24

39

5

49

8

7

6

23

5

6

7

3

1

2

4

9

8

6

9

5

2

3

1

8

4

7

7

3

1

8

6

4

9

2

5

2

8

4

7

5

9

1

3

6

39

7

2

49

8

5

6

1

34

39

5

6

1

49

7

23

8

234

4

1

8

6

2

3

5

7

9

★

★ r8c9 hat die Kandidaten 2, 3, 4. Auch dieses Raster hat genau eine Lösung. Welchen Kandidaten musst du eintragen? Notiere die Koordinaten in den drei Bereichen, in denen er jeweils dreimal vorkommt.

Lösung anzeigen

Es gilt r8c9=3. In Zeile 8 liegt die 3 bei r8c1, r8c7, r8c9, in Spalte 9 bei r2c9, r7c9, r8c9 und in Block 9 bei r7c9, r8c7, r8c9. Ohne die 3 in r8c9 kommt jeder Kandidat, auch in den anderen leeren Zellen, in jedem betroffenen Bereich zweimal vor. Die Voraussetzung einer eindeutigen Lösung schließt diesen BUG-Zustand aus, also trägst du den zusätzlichen Kandidaten 3 ein.

Weiterlesen

Die Vorkenntnisse findest du in Kandidaten im Sudoku richtig notieren und Musst du beim Sudoku raten?. Lies anschließend AIC-Einstieg: Was kannst du mit abwechselnden starken und schwachen Bindungen streichen?.

Die eigenen Beispielrätsel wurden mit dem Generator und dem logischen Löser von sudoku-core gefunden. Seed, Schwierigkeit und Schrittnummer stehen in den Metadaten. Referenz für die Definition: HoDoKu Uniqueness.