Ne postoji Sudoku sa 16 početnih brojeva!

Što je Sudoku?

Sudoku je matematička zagonetka koja se razvila u Japanu. Igra se sastoji od jednog velikog kvadratnog polja s ukupno 81 manjih polja, tj. devet manjih 3×3 kvadrata koje je potrebno ispuniti brojevima od jedan do devet tako da se svaki broj ispuni samo jednom u nizu i jednom u kvadratu. Sama igra temelji se na logici, a može se koristiti i za testiranje inteligencije. Svaka zagonetka započinje s određenim brojem početnih brojeva te se na temelju eliminacije polja ili brojeva popunjavaju ostala polja.

Ne postoji Sudoku sa 16 početnih brojeva!

Znanstvenici Gary McGuire, Bastian Tugemann i Gilles Civario (University College Dublin u Irskoj) pokazali su kako ne postoji Sudoku sa 16 početnih brojeva, tj. tragova. Minimalan broj tragova kako bi igra bila rješiva je 17. Irski matematičari koristili su složen algoritam te su potrošili milijune sata na superračunalu kako bi riješili otvorenu zagonetku u matematici ove igre. Dokazano je kako Sudoku s manje od 17 početnih brojeva nema jedinstveno rješenje. Većina Sudoku igara u časopisima započinje s oko 25 početnih brojeva te se težina zagonetke povećava sa smanjenjem početnih brojeva. Na konferenciji u Bostonu objavljeno je kako je dokaz vjerojatno ispravan te predstavlja važan iskorak u polju Sudoku matematike.

Početna ideja ovih znanstvenika dobivena je proučavanjem raznih članaka vezanih za analizu sekvenciranih gena i staničnih mreža. Stoga, moguće je da se ovaj algoritam može upotrijebiti baš u tu svrhu. Dizajnirali su tzv. “hitting-set algoritam” s idejom pronalaska neizbježnih setova, tj. setova brojeva u riješenoj zagonetci koja se mogu međusobno izmjenjivati, te stoga dati i različite rezultate. Kako bi izbjegli višestruke rezultate, svi tragovi se moraju preklapati s neizbježnim setovima. Nakon što se pronađu neizbježni setovi, ovaj zadatak postaje puno lakši, ali i dalje netrivijalan računalni zadatak preko kojega je moguće pokazati kako se igra sa 16 početnih brojeva ne može preklapati sa svim setovima.