09.01.2012 17:41
Selgus sudoku vähim võimalik algseis
Iiri matemaatikul õnnestus tõestada, et sudokus peab
ühese lahenduse jaoks olema ette antud vähemalt 17 numbrit.
Jaapanis ülipopulaarseks muutunud ja sealt üle maailma
levinud sudoku on loogikal põhinev numbrimäng. Mängu üldlevinud variant koosneb
9×9 ruudustikust, mis on jaotatud omakorda üheksaks 3×3 piirkonnaks. Ruudustik
tuleb täita numbritega 1-9 nii, et üheski reas, veerus ega piirkonnas ükski
number ei kordu.
Dublini ülikooli kolledži matemaatik Gary McGuire kasutas
sudoku seni vastuseta olulise matemaatilise probleemi lahendamiseks keerulist
algoritmi ja superarvuteid, kirjutas Nature News.
Tal õnnestus tõestada, et selle numbrimängu lahendamiseks
vajalik minimaalne etteantud numbrite arv on 17, sest 16 või vähema algselt
täidetud ruudu korral ei ole sudokul ühest lahendust. Enamike ajalehtedes ja
ajakirjades leiduvate sudokude puhul on ära trükitud kuni 25 numbrit. Mida
rohkem on numbreid algselt teada, seda lihtsam on tühje ruute õigete numbritega
täita.
Keegi pole suutnud koostada üheselt lahendatavat 9x9
sudokut, kus oleks algselt märgitud vähem kui 17 numbrit, mistõttu oletati, et
16 etteantud numbriga ei saagi eksisteerida ühest lahendust.
Üks võimalik viis selle tõestamiseks oleks kontrollida
kõigi erinevate 16 algnumbri kombinatsioonidega esineda võivaid
lahendusvariante, kuid need arvutused võtaks liiga kaua aega – 9x9 sudokul on
umbes 1021 võimalikku erinevat lahendust.
McGuire lihtsustas ülesannet, luues vältimatute
numbrikomplektidega arvestava algoritmi. Tema mõte oli otsida sudokus esinevaid
vältimatuid numbrikomplekte ehk numbrite asetusi lahendatud sudokus, mis on
asendatavad mõne teise numbrikomplektiga, võimaldades seetõttu erinevaid
lahendusi.
Mitme lahendusvariandi vältimiseks peab olema lahendajale
algselt teada mõni number kõigist vältimatutest numbrikomplektidest. Kõiki
selliseid numbrikomplekte teades on vaja teostada juba palju vähem arvutusi
näitamaks, et 16 etteantud numbriga ei ole võimalik hõlmata kõiki vältimatuid
numbrikomplekte ning seega võib sel juhul alati olla mitu erinevat lahendust.
Esmapilgul lihtsana tunduva tõdemuseni jõudmise keerukust
näitab, et kokku kulus McGuire rühmal oma algoritmi testimiseks kaks aastat ja
ligi 700 miljonit protsessori töötundi.