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.