Sprawdzanie Sudoku

Cel

Sudoku to gra matematyczna, która nie pozwala, aby w obrębie obszaru, wiersza czy kolumny nie pozwala, aby powtórzyła się ta sama cyfra. Istnieje kilka podejść do sprawdzenia czy tak łamigłówka została rozwiązana. W tym artykule zostanie podany przykładowy sposób sprawdzania.

Analiza zadania

Sprawdzanie czy sudoku zostało prawidłowo rozwiązanie może polegać na odczytaniu wartości z wybranego obszaru, a następnie sprawdzeniu czy któraś wartość się nie powtarza. Dodatkowo należałoby sprawdzić czy każda z wartości została wpisana dokładnie tylko jeden raz i czy jest z odpowiedniego zakresu. Weźmy przykładowo poniższy widok planszy sudoku:

W celu sprawdzenia pierwszego rzędu należałoby wybrać wszystkie wartości {2, 7, 6, 4, 5, 3, 8, 9, 1}. Najprostszym sposobem byłoby teraz te wartości posortować. Wtedy od razu możnaby odczytać czy minimum to 1, a maksimum to 9 oraz czy każda kolejna wartość jest o jeden większa. Jeśli podane warunki zostaną spełnione to można sprawdzić następny obszar (tj. wiersz, kolumnę czy kwadrat).

Implementacja

Sortowanie zajmuje jednak trochę czasu, więc lepiej przyjąć inną strategię. Jeśli sudoku zostanie rozwiązane poprawnie to każdy obszar składa się z liczb od 1 do 9, a więc sumuje się do 45. Dodatkowo przyjmując, że każda wartość jest poprawna (można to zrobić podczas jej pobierania) to nie trzeba wtedy sprawdzać zakresu liczb dla każdego obszaru oddzielnie. Innymi słowy wystarczy zsumować wartości danego obszaru i porównać do poprawnego wyniku.

Dodatkowo zauważmy, że każda z wartości należy do trzech obszarów, które są znane z góry. Nie trzeba zatem odczytywać tej wartości trzy razy, a jedynie raz i zaktualizować wszystkie trzy liczniki równocześnie. Poniżej został przedstawiony przykładowy algorytm, który dla każdego obszaru deklaruje licznik, a następnie przechodzi po całej tablicy.

1. bool SprawdzPoprawnosc(int** tablica) {
2.   int* liczniki = new int[27]{ 0 };
3.   for (int x = 0; x < N; x++) {
4.     for (int y = 0; y < N; y++) {
5.       int wartosc = tablica[x][y];
6.       if (wartosc < 1 || wartosc > 9) {
7.         return false;
8.       }
9.       liczniki[x] += wartosc;
10.       liczniki[y + 9] += wartosc;
11.       liczniki[(x / 3 + (y / 3) * 3) + 18] += wartosc;
12.     }
13.   }
14.   for (int i = 0; i < 27; i++) {
15.     if (liczniki[i] != 45) {
16.       return false;
17.     }
18.   }
19.   return true;
20. }

Zaletą takiego rozwiązanie jest usunięcie sortowania liczb oraz zminimalizowanie ile razy dana wartość musi zostać odczytana. Dzięki temu algorytm ma bardzo niską złożoność. W podanym przykładzie dla każdej wartości aktualizujemy trzy liczniki: dla wiersza, kolumny oraz obszaru. Ze względu na to, że liczniki są zapisane na jednowymiarowej tablicy to liczniki wiersza mają przesunięcie 0, kolumny 9, a obszarów 18. W tych ostatnich mylące może być mylące przeliczanie licznika. Otóż w tym przypadku musimy zamienić pozycję (x, y) na numer kwadratu. Pozycję kwadratu otrzymujemy dzieląc współrzędne przez 3, więc będzie to (x//3, y//3), gdzie // - dzielenie całkowitoliczbowe. Tą wartość z kolei zamieniamy na numer licznika czyli i = x//3 + y//3 * 3. Jednak y//3*3 to nie jest y, ponieważ jest to dzielnie całkowitoliczbowe!

Testowanie funkcji

Podany wyżej algorytm można sprawdzić przy pomocy poniższego fragmentu kodu:

1. int main() {
2.   cout << "Podaj wartosci tablicy:\n";
3.   int** tablica = new int*[N];
4.   for (int i = 0; i < N; i++) {
5.     tablica[i] = new int[N];
6.     for (int j = 0; j < N; j++) {
7.       cin >> tablica[i][j];
8.     }
9.   }
10.   bool wynik = SprawdzPoprawnosc(tablica);
11.   cout << "Sudoku " << (wynik ? "" : "nie") << "poprawnie rozwiazane";
12.   system("pause");
13.   return 0;
14. }

• Kod źródłowy Implementacja