Matematycy rozwiązują minimalny problem sudoku

Sudoku to łamigłówka liczbowa składająca się z siatki 9 x 9, w której niektóre komórki zawierają wskazówki w postaci cyfr od 1 do 9. Zadaniem rozwiązującego jest wypełnienie pozostałych komórek tak, aby każdy wiersz, kolumna i pole 3×3 były siatka zawiera wszystkie dziewięć cyfr.

Jest jeszcze jedna niepisana zasada: zagadka musi mieć tylko jedno rozwiązanie. Tak więc plansze nie mogą zawierać tylko kilku wskazówek na początek.

Łatwo zrozumieć, dlaczego. Siatka z 7 wskazówkami nie może mieć jednoznacznej odpowiedzi, ponieważ dwie brakujące cyfry zawsze można zamienić w dowolnym rozwiązaniu. Podobny argument wyjaśnia, dlaczego siatki z mniejszą liczbą wskazówek również muszą mieć wiele rozwiązań.

Ale nie jest tak łatwo zrozumieć, dlaczego siatka z 8 wskazówkami nie może mieć unikalnego rozwiązania, a nawet taka, która ma 9 lub więcej wskazówek.

To rodzi interesujące pytanie dla matematyków: jaka jest minimalna liczba wskazówek Sudoku, która daje unikalną odpowiedź?

To pytanie wisiało ciężko w społeczności Sudoku, nie tylko dlatego, że wydaje im się, że znają odpowiedź. Fanatycy Sudoku znaleźli wiele przykładów siatek z 17 wskazówkami, które mają unikalne rozwiązanie, ale nigdy nie znaleźli takiej z 16 wskazówkami.

Sugeruje to, że minimalna liczba wynosi 17, ale nikt nie był w stanie udowodnić, że gdzieś w przestrzeni łamigłówki nie kryje się 16-znakowe rozwiązanie.

Wprowadź Gary'ego McGuire'a i kumpli z University College Dublin. Ci faceci rozwiązali problem, stosując wypróbowaną i zaufaną matematyczną technikę czystej brutalnej siły.

W gruncie rzeczy ci faceci przeanalizowali każde potencjalne rozwiązanie 16-wskazówkowe dla każdej możliwej siatki Sudoku. Podczas naszych poszukiwań nie znaleziono porządnych łamigłówek z 16 wskazówkami, ale gdyby jedna istniała, to byśmy ją znaleźli, mówią.

To imponujący wyczyn. Istnieje dokładnie 6, 670, 903, 752, 021, 072, 936, 960 możliwych rozwiązań Sudoku (około 10^21) . To znacznie więcej, niż można sprawdzić w rozsądnym czasie.

Ale na szczęście nie trzeba ich wszystkich sprawdzać. Różne argumenty dotyczące symetrii dowodzą, że wiele z tych siatek jest równoważnych. Zmniejsza to liczbę, które należy sprawdzić, do zaledwie 5,472,730,538.

Tak więc McGuire i współpracownicy napisali program o nazwie Checker, który sprawdza każdą z tych siatek pod kątem rozwiązania 16-wskazówek.

Ale sam proces sprawdzania pojedynczej siatki jest skomplikowany. Jednym ze sposobów na to jest zbadanie każdego możliwego podzbioru 16 wskazówek, aby zobaczyć, czy któraś z nich prowadzi do unikalnego rozwiązania. Kłopot polega na tym, że dla każdej siatki jest jakieś 10^16 podzbiorów.

Po raz kolejny przyda się trochę matematyki. McGuire i współpracownicy zastosowali sprytne rozumowanie, aby pokazać, że pewne podzbiory są równoważne wielu innym, co drastycznie zmniejsza liczbę podzbiorów, które należy sprawdzić.

Niemniej jednak wynikowa kalkulacja wciąż jest potworem. Zespół z Dublina twierdzi, że na maszynie z 640 sześciordzeniowymi procesorami Intel Xeon zajęło to 7,1 miliona godzin rdzenia. Rozpoczęli w styczniu 2011 i zakończyli w grudniu.

Całe ćwiczenie może brzmieć jak trochę matematycznej zabawy, ale ten rodzaj rozwiązywania problemów ma wiele ważnych zastosowań. McGuire i wsp. twierdzą, że problem sprawdzania siatki Sudoku jest formalnie równoważny problemom związanym z analizą ekspresji genów oraz testowaniem sieci komputerowych i oprogramowania.

Tak więc metody zespołu z Dublina dotyczące przyspieszenia obliczeń będą miały bezpośredni wpływ również w tych obszarach.

Ale chociaż wynik jest wyraźnie imponujący, problem minimalnego sudoku nie został całkowicie odłożony.

Ten problem woła o elegancki dowód, który pozwoli nam zobaczyć, dlaczego minimalna liczba musi wynosić 17; raczej jak dowód na to, że nie ma unikalnych rozwiązań dla 7 lub mniej wskazówek.

Wielka prośba, wiem, ale z pewnością warto do niej dążyć.

Nr ref.: arxiv.org/abs/1201.0749 : Nie ma 16 wskazówek Sudoku: Rozwiązywanie problemu z minimalną liczbą wskazówek

Poprawka: ten post został zredagowany 6 stycznia, aby odzwierciedlić argument, że jeśli siatka n-wskazówek jest jednoznacznie rozwiązywalna, to dodanie cyfry, aby utworzyć siatkę n+1-wskazówek, również musi być jednoznacznie rozwiązywalne. Więc jeśli nie ma siatek 16-wskazówek dających się jednoznacznie rozwiązać, nie może być siatek z mniejszą liczbą wskazówek, które są rozwiązywalne w sposób jednoznaczny. Dzięki RealMurph i abooij.

ukryć