3.1. Rozwiązania możliwe

Rozwiązania możliwe są to zbiory cyfr, które mogą wystąpić w pustych polach planszy SUDOKU. Są powszechnie wykorzystywane, ale zwykle nie konsekwentnie dla całego zadania. Niektóre zależności zachodzące między zbiorami rozwiązań możliwych są wykorzystywane przy rozwiązywaniu zadań techniką „kartka_pisak”. Wyznaczanie rozwiązań możliwych powinno być podstawową umiejętnością rozwiazującego SUDOKU. Można te rozwiązania uzyskać w sposób pokazany poniżej.

Będziemy dalej rozważać sytuację widoczną na rys. 3.1. Na planszy mamy pokazane dane startowe (cyfry wytłuszczone) oraz rozwiązania możliwe (małe cyfry), które wyznaczył komputer. Stanowić one będą elementy kontrolne przedstawianych dalej rozważań, które prowadzimy jak gdyby ich nie było.

Puste pola należą do wiersza (W), kolumny (K) oraz sekcji (S). Jeżeli oznaczymy zbiory cyfr występujących w tych obiektach odpowiednio AW, BK i CS, to rozwiązania możliwe uzyskać można na podstawie zależności

R[W,K] = Z – AW – BK – CS , (*)

gdzie Z = {1,2,3,4,5,6,7,8,9}.

Przykład 1 (pole [1,3]) (rys. 3.1): A1 = {3,5,7}, B3 = {8}, C1 = {3,5,6,8,9}.

Jako wynik na podstawie (*) otrzymujemy R[1,3] = {1,2,4}.

UWAGA – w operacjach na zbiorach nie ma elementów ujemnych.

Przykład 2 (pole [5,5]) (rys. 3.1): A5 = {1,3,4,8}, B5 = {1,2,6,7,8,9}, C5 = {2,3,6,8}.

Jako wynik otrzymujemy R[5,5] = {5}.

Przykład 3 (pole [7,9])(rys. 3.1): A7 = {2,6,8}, B9 = {1,3,5,6,9}, C9 = {2,5,7,8,9}.

Otrzymujemy w tym przypadku R[7,9] = {4}.

Dwa ostatnie wyniki są poszukiwanymi rozwiązaniami. Mamy tu do czynienia z rozwiązaniami typu SINGIEL. Możemy napisać: P[5,5] = 5, P[7,9] = 4.

Program komputerowy wyznacza zbiory rozwiązań możliwych korzystając z tablic pomocniczych X. Przykłady takich tablic pokazano na rys. 3.2. Tablice te budowane są w sposób przedstawiany poniżej.

Dla wybranego pustego pola planszy SUDOKU budujemy tablicę, która ma 4 wiersze oraz 9 kolumn. Kolumny odpowiadają poszczegolnym cyfrom zbioru Z. Pierwszy wiersz tablicy X związany jest z wierszem W, drugi z kolumną K natomiast trzeci z sekcją S. W tablicy kodujemy przy pomocy znaków „X” fakt niewystępowania danej cyfry w zbiorach dotyczących poszczególnych obiektów (wierszy, kolumn, sekcji). W czwartym wierszu tablicy X znak „X” pojawia się wtedy, gdy w kolumnie tej tablicy mamy trzy znaki „X”. Posługując się tak wyznaczonymi kodami możemy określić zbiór rozwiązań możliwych dla rozważanego pola planszy.

3.2. Rozwiązania zadania

Jeden typ rozwiązań zadania, tzw. SINGLE już poznaliśmy. Są te rozwiązania widoczne od razu po wyznaczeniu rozwiązań możliwych dla wszystkich pustych pól planszy SUDOKU. Są też rozwiązania innego typu. Rozważmy wiersz nr 6. Mamy w tym przypadku:

R[6,2] = {1,5}, R[6,3] = {1,3,5,9}, R[6,4] = {5,9},

R[6,6] = {1,4}, R[6,7] = {4,5,8,9}, R[6,8] = {4,5,9}.

Można zauważyć, że dla rozważanego obiektu (W6) w zestawieniu wszystkich rozwiązań możliwych cyfry „3” oraz „8” występują tylko raz. Są to kolejne rozwiazania zadania. Mamy więc: P[6,3] = 3, P[6,7] = 8.

Rozważmy kolumnę nr 5. W tym przypadku mamy: R[3,5] = {3,4}, R[5,5] = {5}, R[7,5] = {3,5}. Można zauważyć, że cyfra „4” występuje tylko raz. Jest to kolejne rozwiazanie zadania. Mamy więc P[3,5] = 4.

Rozważmy następnie sekcję nr 9. W tym przypadku mamy: R(9,3) = {4}, R(9,4) = {3,6}, R(9,5) = {3}, R(9,7) = {1,3,4,6}. Cyfra „1” w podanych zestawieniach występuje tylko raz. Mamy więc P(9,7) = P[9,7] = 1.

Proponowany algorytm sprowadza się do konsekwentnego wyszukiwania rozwiązań jednokrotnych w analizowanych obiektach (wierszach, kolumnach lub sekcjach). Są to rozwiązania typu JEDYNA.

Na podstawie analizy planszy pokazanej na rys. 3.1 można otrzymać kolejne rozwiązania tego typu:

wiersz nr 3/ P[3,7] = 5, wiersz nr 5/ P[5,3] = 6 oraz P[5,7] = 7,

wiersz nr 8/ P[8,2] = 8 oraz P[8,7] = 6,

kolumna nr 1/ P[7,1] = 9, kolumna nr 6/ P[1,6] = 8, kolumna nr 8/ P[1,8] = 1.

Mamy też rozwiązania typu SINGIEL: P[7,6] =7, P[8,8] = 3.

UWAGA – w poszukiwaniu kolejnych rozwiązań nie uwzględniano wpływu rozwiązań już zidentyfikowanych, na postać zbiorów rozwiązań możliwych.

Algorytm rozwiązywania SUDOKU polegający na identyfikacji rozwiazań typu SINGIEL oraz JEDYNA nazywać będziemy algorytmem standardowym. Zadania, które można rozwiązać przy pomocy tego algorytmu nazywać będziemy zadaniami standardowymi. Takimi zadaniami są zwykle zadania zamieszczane w popularnych wydawnictwach.

Na zakończenie przedstawianych rozważań pokażemy tablice pomocnicze T, kreowane w trakcie rozwiązywania przez program komputerowy, który omówimy w innym miejscu. Tablice T budowane są dla każdego obiektu. Liczba tablic 3*9 = 27. W tablicach tych kodujemy znakami „X” fakt występowania cyfry zbioru rozwiązań możliwych. Wiersz zerowy tych tablic odpowiada polu planszy SUDOKU ze znaną cyfrą. Poszukujemy pojedynczych znaków „X” w wierszach lub kolumnach, które oznaczają odpowiednio rozwiązania typu SINGIEL lub JEDYNA. Wybrane tablice T pokazano na rys. 3.3 i 3.4.