email: darw32@poczta.onet.pl

Sudoku - Techniki Rozwiązywania

Forsowne Łańcuchy (Forcing Chains)

Ta metoda (na szczęście!) jest całkiem łatwa do zrozumienia, ale może zabrać całkiem sporo czasu. Jeśli używasz tej metody to posiadanie oddzielnej kopii sudoku albo notatnik naprawdę pomaga, ponieważ wymaga ona mnóstwa notatek!

Prosty forsowny łańcuch (ang. Forcing Chain) występuje wtedy, gdy masz mnóstwo komórek z 2-ma kandydatami - i którąkolwiek wartość wybrałbyś w jednej komórce, wymusza to (forsuje) aby inna komórka przyjeła jedną z jego dwóch wartości. Wyjaśnimy to poniżej na przykładzie!

Pierwszy Wybór

Spójrz na ten diagram, który pokazuje przykład forsownego łańcucha.

Nie ma znaczenia czy komórce [1,3] będzie wartość "1" czy też "2", wymusi to, aby w komórce [4,1] była wartość "5".

Zanim zaczniemy warto nadmienić, że niektóre z tych łańcuchów mogą być krótkie, a niektóre całkiem długie. Tutaj jest przykład krótkiego łańcucha.

Po pierwsze, wyobraźmy sobie, że komórka [1,3] przyjmuje wartość "1". To z kolei wymusiłoby aby komórka [4,3] przyjeła wartość "4" a to z kolei forsuje wartość "7" w komórce [4,6]. Ma koniec wymusiłoby to aby komórka [4,1] przyjeła wartość "5".

Tak więc wystąpienie w komórce [3,1] wartości "1" forsuje (wymusza) wartość "5" w komórce [4,1]:

Drugi Wybór

Teraz z kolei przyjmujemy, że komórka [1,3] ma wartość "2" zamiast "1". Ponownie wykreślając wartości, które wykluczamy - zobaczysz całkiem długi łańcuch!

Tutaj widzisz jak to wygląda za pomocą strzałek.

Dwa łańcuchy zaczynające się od dwóch różnych wartości z komórki [1,3] mają inne drogi, ale obydwie prowadzą do tego, że w komórce [4,1] będzie wartość "5".

Gdy tylko znajdziesz taką sytuację, że niezależnie od kandydującej wartości podanej w komórce początkowej, komórka końcowa przyjmie zawsze tą samą wartość. Więc możesz wpisać tą wartość do komórki końcowej!

Czy to jest to samo co zgadywanie?

Nie całkiem - w tym przypadku niezależnie od dokonanego wyboru w początkowej komórce, w komórce końcowej otrzymamy tą samą wartość. Nie jest więc to zgadywanie gdyż wartość, którą wpiszemy w komórkę końcową jest pewna i wynika z przeprowadzonej przez nas dedukcji. Przy zgadywaniu wpisujemy jakąś wartość w komórkę początkową i mimo iż w naszej komórce końcowej otrzymalibyśmy poprawną wartość, lecz w zależności od tego czy zgadliśmy poprawnie wartość w komórce początkowej czy też nie możemy zrobić całą masę błędów po drodze.

Jak bardzo to jest trudne?

To co sprawia, że metoda ta jest trudna to to, że musisz tworzyć jak najdłuższe łańcuchy (do momentu aż nie będzie możliwe wymuszenie kolejnej wartości w łańcuchu), więc dużo testów przed tobą. Dłuższe łańcuchy nie są trudniejsze niż krótsze, ale znacznie łatwiej popełnić w nich błąd.

Można oczywiście tworzyć łańcuchy tylko z komórek zawierających dwóch kandydatów sprawia to, że tworzenie łańcuchów staje się prostsze. Oczywiście, przy tworzeniu łańcuchów można brać pod uwagę komórki z trzema lub więcej kandydatami.

Porada : Oto metoda z użyciem nakładek (kalki kreślarskiej albo nakładki przezroczystej komputerowej), przy pomocy której szukanie łańcuchów jest trochę łatwiejsze.
-> Wybierz komórkę startową i zrób mały znaczek (np. kółeczko) pod pierwszym znacznikiem komórki startowej. Następnie, gdy znajdziemy kolejną wartość, którą wymusza (forsuje) nasz poprzedni wybór to nie wykreślamy innych znaczników z komórki, w której znaleźliśmy kolejną wartość (bo doprowadzi to do bałaganu), lecz stawiamy taki sam znaczek przy wymuszonej wartości. Ignoruj pozostałe znaczniki z komórki, w której wstawiliśmy znaczek przy wymuszonej wartości (one mogą być potrzebne później)!
-> Kontynuuj to dotąd, dopóki nie możesz już "forsować" kolejnych wartości.
-> Teraz wybierz drugą wartość z komórki startowej i wstaw nad nią inny znaczek (np. kwadracik). Tak jak wcześniej, kontynuuj wymuszanie wartości w komórkach do czasu, dopóki nie możesz już "forsować" kolejnych wartości (pamiętaj, że przy "wymuszonych" wartościach wstawiasz znacznik z drugiego wyboru).
-> Na koniec szukamy w "forsownym łańcuchu" komórki, w której przy jednym znaczniku są obydwa znaczki (np. kóleczko i kwadracik). Gdy coś takiego zauważysz, jest to pewny znak, że niezależnie od kandydata, którego wybrałeś w pierwszej komórce, w komórce końcowej zawsze będzie ta sama wartość (ta przy której znaczniku są obydwa znaczki). Wstaw tą wartość do komórki końcowej. Na tym kończymy przeszukiwanie forsownego łańcucha.
Niektórzy ludzie używają kolorów, by uczynić łatwiejszym oznaczanie forsownych łańcuchów, ale nie jest to konieczne.