email: darw32@poczta.onet.pl

Sudoku - Techniki Rozwiązywania

Proste Kolorowanie (Simple Coloring)

Proste Kolorowanie (ang. Simple Koloring) zwana także Pojedyńczymi Łańcuchami (ang. Singles Chains) rozpatrywane jest dla jednej wartości. Polega ona kolejno na wykonywanych krokach:

  • Wybieramy pewien sektor (wiersz/kolumna/blok 3x3), w którym wartość "x" kandyduje dokładnie w dwóch pozycjach. Sektor ten nazywamy Sektorem Bazowym.
  • Ustalamy, że pierwsza kandydująca pozycja dla wartości "x" w sektorze bazowym przyjmuje wartość "x". Pozycję tą symbolicznie oznaczymy jako "ON" (włączona do łańcucha).
  • następnie wszystkie pozycje z sektorów zawierających pozycje "ON", które kandydują dla wartości "x" oznaczamy jako "OFF" (wyłączona z łańcucha) - oczywiście bez pozycji "ON".
  • teraz szukamy takiego sektora, w którym dokładnie jedna pozycja kandydująca dla wartości "x" nie została oznaczona jako "OFF" i oznaczamy ją jako "ON".
  • kroki 3 i 4 powtarzamy dotąd, aż:
    • wszystkie sektory zostaną wypełnione wartością "x" (łańcuch pełny)
    • nie uda się wypełnić kolejnej pozycji wartością "x" - krok 4-ty zakończył się niepowodzeniem (łańcuch niepełny)
    • wystąpiła sprzeczność - wszystkie kandydujące pozycje dla wartości "x" w pewnym sektorze są oznaczone jako "OFF" (łańcuch sprzeczny)
  • przy czym łańcuchem nazywamy wszystkie pozycje, które koleno przyjmują wartość "ON".
  • ściągamy znacznik "ON" i "OFF" z wszystkich pozycji, które zostały oznaczone tymi znacznikami.
  • teraz przyjmujemy, że druga kandydująca pozycja dla wartości "x" z sektora bazowego przyjmuje wartość "x" i oznaczamy ją jako "ON" i od tego momentu wykonujemy kroki 3, 4 i 5 tworząc w ten sposób drugi łańcuch.
  • Mając obydwa wypełnione łańcuchy usuwanie kandydata "x" odbywa się różnie, w przypadku gdy:
    • obydwa łańcuchy są pełne - usuwamy wartość "x" z pozycji, które nie wystąpiły ani w pierszym, ani w drugim łańcuchu
    • conajmniej jeden z dwóch łańcuchów jest niepełny - usuwamy wartość "x" z pozycji, które nie wystąpiły ani w jednym, ani w drugim łańcuchu oraz:
      • pozycja ta leży w sektorze (wiersz/kolumna/blok), w którym są pozycje z obudwu łańcuchów
      • pozycja ta leży na przecięciu sektorów (wiersz/kolumna/blok) dowolnych dwóch pozycji (jednej pozycji z pierwszego łańcucha, a drugiej z drugiego łańcucha)
    • jeden z łańcuchów jest sprzeczny - wartość "x" usuwamy z pierwszej pozycji, która należy do sprzecznego łańcucha

Opis algorytmu prostego kolorowania jest trochę skomplikowany (cóż zrobić starałem się być w miarę precyzyjny), więc bez przykładów, które przedstawiam poniżej, się nie obędzie.

Obydwa pełne łańcuchy

Na diagramie obok mamy przykład pełnych łańcuchów:
Niech wiersz "1" jest sektorem bazowym, kolorowanie wykonujemy dla wartości "4", zakładając, że pozycjia [1,2] przyjmuje wartość "4" (ustawiona na ON) wówczas pozycja [8,2] będzie ustawiona na OFF zatem pozycja [7,3] będzie na ON, z kolei pozycja [7,9] przyjmie wartość OFF, więc pozycja [8,2] przyjmie wartość ON postępując dalej analogicznie otrzymamy następujący łańcuch:
Łańcuch 1: [1,2]→ [7,3]→ [8,7]→ [6,8]→ [3,9]→ [2,4]
analogicznie zakładając, że pozycja [1,8] przyjmuje wartość "4" tworzymy drugi łańcuch:
Łańcuch 2: [1,8]→ [2,3]→ [3,4]→ [6,7]→ [7,9]→ [8,2]
Ponieważ wystąpiły pełne łańcuchy tzn. wszystkie dostępne sektory (wiersze/kolumny/bloki) zostały wypełnione dla kandydata "4" w obydwu łańcuchach, tak więc można usunąć wartość "4" z pozycji, które nie wystąpiły ani w pierszym ani w drugim łańcuchu, w naszym przypadku z pozycji: [2,8], [3,7].

Conajmniej jeden z łańcuchów niepełny

Na diagramie obok mamy dwa łańcuchy prostego kolorowania dla wartości "4" oraz wiersza "8" jako sektora startowego:
Łańcuch 1: [8,1]→ [5,6]→ [9,5]
Łańcuch 2: [8,6]→ [9,2]
W tym przypadku wystąpiły niepełne łańcuchy, tak więc można usunąć tą wartość z pozycji, które nie wystąpiły ani w jednym, ani w drugim łańcuchu oraz:
- pozycja ta leży w sektorze (wiersz/kolumna/blok), w którym są pozycje z obudwu łańcuchów
- pozycja ta leży na przecięciu sektorów (wiersz/kolumna/blok 3x3) dowolnych dwóch pozycji (jednej pozycji z pierwszego łańcucha, a drugiej z drugiego łańcucha).
W naszym przypadku usuwamy kandydata "4" z pozycji na przecięciu wiersza przechodzącego przez pozycję [5,6] (pozycja z pierwszego łańcucha) oraz kolumny przechodzącej przez punkt [9,2] (pozycja z drugiego łańcucha) czyli z punktu [5,2].

Jeden z łańcuchów sprzeczny

Na diagramie obok algorytm prostego kolorowania stosujemy dla wartości "5", a sektorem bazowym jest 4-ty wiersz, otrzymujemy łańcuchy:
Łańcuch 1: [4,3]→ [6,4]→ [2,5]→ [1,1]→ [7,7]→ [5,9]→ [8,6]→ [9,2]
Łańcuch 2: [4,6]→ [1,4]→ [2,1]→ [5,3]→ [6,7]→ sprzeczność (wartość "5" nie może wystąpić w 7-mym wierszu)
Ponieważ w drugim łańcuchu wystąpiła sprzeczność, więc usuwamy wartość "5" z pierwszej pozycji tego tego łańcucha, w naszym przypadku z pozycji: [4,6].

Porada : Stosując proste kolorowanie powinieneś:

  • nie wykorzystywać głównego diagramu sudoku (kolorując/przekreślając/wymazując znaczniki kandydujących wartości narobiłbyś sobie sporo bałaganu na tym diagramie, który nie zawsze dałoby się doprowadzić do orginalnego wyglądu
  • najlepiej jest wykorzystać do tego kartkę w kratkę i narysować na niej dwa diagramy [9x9] z wyszczególnieniem bloków [3x3]
  • zaczynając kolorowanie dla jakiejś wartości "x" zaznaczamy na obudwu diagramach, wszystkie pozycje zawierające kandydata "x" (można wykorzystać dowolny znak np. kropkę), zaznaczać powinniśmy ołówkiem, gdyż łatwo jest wymazać takie znaki gumką
  • na pierwszym diagramie tworzymy pierwszy łańcuch, a na drugim drugi łańcuch przy czym pozycje ustawione na ON można przykładowo brać w kółko, a pozycje ustawione na OFF przekreślać krzyżykiem.
  • gdy mamy, już utworzone obydwa łańcuchy, na pierwszym diagram zaznaczamy w inny sposób pozycje z drugiego łańcucha, które przyjeły wartość ON przykładowo rysując na tej pozycji trójkąt.
  • mając na jednym diagramie pozycje na ON z obydwu łańcuchów można łatwo zgadnąć z jakich pozycji można usunąć wartość "x"
  • wymazując wszystkie znaki z jednego i drugiego diagramu, można je następnie przygotować do rozpatrywania algorytmu prostego kolorowania dla innej kandydującej wartości