Coloring (Färben)

Inhaltsverzeichnis

Simple Colors (Einfaches Färben) (Color Wrap/Color Trap)
Multi Colors (Mehrfaches Färben)

Färben ist eine Einzelziffer-Strategie, die eine ganze Reihe von Varianten in verschiedensten Schwierigkeitsgraden hervorgebracht hat. Zwei einfache Varianten werden hier erklärt. Das Prinzip ist immer das gleiche: Man sucht nach Häusern, in denen die zu färbende Ziffer nur noch in zwei Zellen gesetzt werden kann (das Haus enthält einen strong link für diese Ziffer). Im Coloring-Jargon bezeichnet man einen solchen strong link als "Conjugate Pair". Den zwei Kandidaten des Conjugate Pairs werden zwei verschiedene Farben zugewiesen (siehe Coloring im Benutzerhandbuch). Wenn das Färben abgeschlossen wurde, wird das Gitter nach Widersprüchen durchsucht, die zu Eliminierungen führen können.

Wenn zwei verschiedene Farben in ein Gitter eingetragen wurden (nennen wir sie Farbe 1 und Farbe 2), müssen entweder alle Zellen mit Farbe 1 gesetzt und alle Zellen mit Farbe 2 nicht gesetzt sein oder umgekehrt. Es ist schlicht unmöglich, dass zwei Zellen mit verschiedenen Farben zur selben Zeit gesetzt sind. Wenn mehr als zwei Farben verwendet werden, gilt das oben gesagte für jedes Farbpaar extra.

Alle Färben-Varianten sind einfache Methoden zum Auffinden von Chains. Färben ist normalerweise einfacher als das Gitter nach Chains zu durchsuchen.

Simple Colors (Einfaches Färben)

Einfaches Färben verwendet nur zwei verschiedene Farben. Man beginnt mit einer Zelle eines Conjugate Pairs und weist Farben zu, bis keine gefärbte Zelle mehr zu einem noch nicht komplett gefärbten Conjugate Pair gehört. Danach wird das Gitter nach zwei möglichen Widersprüchen durchsucht:

Eine ungefärbte Zelle, die Zellen mit unterschiedlichen Farben sieht (Color Trap): Da alle Zellen mit derselben Farbe gesetzt oder nicht gesetzt sein müssen, muss eine der zwei verschieden gefärbten Zellen gesetzt sein, und die ungefärbte Zelle kann unmöglich die zu färbende Ziffer enthalten.
Zwei Zellen mit der selben Farbe sehen einander (Color Wrap): Alle Zellen mit dieser Farbe sind entweder gesetzt oder nicht gesetzt. Alle gesetzt ist unmöglich (da würde die selbe Ziffer zwei Mal im selben Haus vorkommen), also müssen alle falsch sein.

Sudoku Lösungstechnik: Beispiel für Simple+Colors

Das linke Beispiel zeigt einen Color Trap: Zelle r1c9 sieht r1c4 und r8c9 und diese beiden Zellen haben unterschiedliche Farben. Kandidat 3 kann von r1c9 gelöscht werden. Das selbe Argument gilt für r3c9 und r8c1.

Das rechte Beispiel zeigt einen Color Wrap: Filter wurden eingeschaltet, daher werden alle Zellen, die einen Kandidaten 8 enthalten, grün gezeichnet (zwei dieser Zellen sind immer noch grün; sie gehören zu keinem Conjugate Pair und sind daher auch nicht gefärbt). Das Färben startete bei r1c6 und wurde fortgesetzt, bis kein weiterer strong link mehr gefunden werden konnte. Jetzt betrachten wir Spalte 4: r2c4 und r4c4 haben beide dieselbe Farbe und sind im selben Haus. 8 kann von allen Zellen mit dieser Farbe eliminiert werden, was das Sudoku löst (Bedeutung: es bleiben nur noch Singles).

Multi Colors (Mehrfaches Färben)

Multi Colors verwendet mehr als ein Farbenpaar zum Färben von nicht zusammenhängenden von Conjugate Pairs gebildeten Regionen. Wenn das Färben abgeschlossen wurde, gibt es wieder zwei Situationen, die zu Eliminierungen führen können.

Zwei gefärbte Zellen von verschiedenen Farbpaaren sind im selben Haus (sie bilden einen weak link). Da sie sich ein Haus teilen, kann nur einer von ihnen gesetzt sein (und das gilt auch für alle anderen Zellen mit diesen Farben). Es bedeutet aber auch, dass entweder die entgegengesetzte Farbe des einen oder die des anderen Farbpaares gesetzt werden muss. Der Färbe-Kandidat kann aus allen Zellen gelöscht werden, die mindestens zwei Zellen mit diesen Farben sehen können.
Zwei Zellen mit derselben Farbe (nennen wir sie Farbe 1) sehen Zellen mit entgegengesetzten Farben eines anderen Farbpaares. Eine der Zellen des anderen Farbpaares muss gesetzt sein (siehe Simple Colors), was bedeutet, dass eine der Zellen mit Farbe 1 falsch sein muss. Da aber alle Zellen mit derselben Farbe den selben Zustand annehmen müssen, kann keine der Zellen mit Farbe 1 den Färbe-Kandidaten enthalten.

Multi Colors sind gleich mächtig wie X-Chains. HoDoKu unterstützt derzeit nur zwei Farbpaare in seiner Multi Colors Implementation, es kann daher nicht für alle X-Chains der äquivalente Multi Color-Spielzug gefunden werden.

Sudoku Lösungstechnik: Beispiel für Multi+Colors

Das linke Beispiel zeigt Typ 1 für Kandidat 1: Es werden zwei Farbpaare verwendet. r1c5 hat Farbe 1a, r1c7 hat Farbe 1b. r2c9 hat Farbe 2a und r5c9 hat Farbe 2b. r1c7 und r2c9 gehören zu verschiedenen Farbpaaren, teilen sich aber dasselbe Haus (Block 3). Da nur einer dieser Kandidaten gesetzt werden kann (es können auch beide nicht gesetzt werden!), müssen entweder alle Zellen mit Farbe 1a oder alle Zellen mit Farbe 2b gesetzt sein (oder auch beides zugleich). Die Zellen r5c23 sehen diese beiden Farben und können daher den Färbe-Kandidaten nicht enthalten.

Das rechte Beispiel zeigt Typ 2 für Kandidat 3 (wir verwenden die selben Farbnamen wir oben): Zelle r6c2 (Farbe 1b) sieht Zelle r6c9 (Farbe 2b) und Zelle r8c6 (auch Farbe 1b) sieht Zelle r2c6 (Farbe 2a). Da entweder alle Zellen mit Farbe 2a oder alle Zellen mit Farbe 2b wahr sein müssen, muss entweder r6c2 oder r8c6 falsch sein. Da diese beiden Zellen aber dieselbe Farbe haben, kann keine der Zellen mit dieser Farbe eine 3 enthalten.