Enciklopedija sudokua · Matematika i računarstvo

Matematika sudokua

Ažurirano 2026-10-05

Latinski kvadrat s kvadratima 3×3

U latinskom kvadratu svaki se simbol pojavljuje jednom u svakom retku i svakom stupcu. Riješeni sudoku latinski je kvadrat veličine 9 s jednim dodatnim uvjetom: i svaki od devet kvadrata 3×3 sadrži svaku znamenku jednom.

Izvori: Wikipedia: Latin square

Koliko mreža postoji

Bertram Felgenhauer i Frazer Jarvis prebrojili su 2005. popunjene mreže 9×9: ima ih 6.670.903.752.021.072.936.960, oko 6,67 × 10²¹. Mnoge od njih zapravo su ista mreža u drugačijem ruhu. Ako se dvije mreže računaju kao jedna kad se jedna može pretvoriti u drugu preimenovanjem znamenki, rotacijom ili zrcaljenjem, ili preslagivanjem redaka i stupaca na načine koji mrežu ostavljaju ispravnom, preostaje 5.472.730.538 bitno različitih mreža, a taj su broj izračunali Ed Russell i Frazer Jarvis.

Izvori: Felgenhauer and Jarvis, Enumerating possible Sudoku grids (2005), OEIS A107739: number of Sudoku grids, Wikipedia: Mathematics of Sudoku

Minimum od 17 zadanih brojeva

Nijedan standardni sudoku 9×9 sa 16 ili manje zadanih brojeva nema točno jedno rješenje. Gary McGuire, Bastian Tugemann i Gilles Civario pokazali su to iscrpnom računalnom pretragom i objavili rezultat u siječnju 2012. Sedamnaest je minimum, a ne jamstvo: mnoge mreže sa 17 zadanih brojeva i dalje imaju više od jednog rješenja.

Izvori: McGuire, Tugemann and Civario, There is no 16-Clue Sudoku (arXiv 1201.0749)

Sudoku kao bojenje grafa

Nacrtajte po jednu točku za svaku od 81 ćelije i spojite dvije točke kad god njihove ćelije dijele redak, stupac ili kvadrat. Taj sudoku graf ima 810 veza, a svaka točka ima točno 20 susjeda. Riješiti zagonetku znači proširiti boje koje su odredili zadani brojevi tako da spojene točke nikad nemaju istu boju. Potrebno je najmanje devet boja jer je svaki redak, stupac i kvadrat skupina od devet točaka koje su sve međusobno spojene, a svaka popunjena mreža pokazuje da je devet dovoljno.

Izvori: Wikipedia: Sudoku graph

Općenito teško, za 9×9 brzo

Za mreže sudokua koje mogu rasti bez ograničenja (n²×n² s kvadratima n×n), odlučivanje o tome može li se djelomično popunjena mreža dovršiti NP-potpun je problem, a taj su rezultat 2003. objavili Takayuki Yato i Takahiro Seta. Učinkoviti računalni programi obične zagonetke 9×9 obično riješe u djeliću sekunde, iako vrijeme ovisi o programu, računalu i zagonetki.

Izvori: Wikipedia: Mathematics of Sudoku, Wikipedia: Sudoku solving algorithms, Peter Norvig: Solving Every Sudoku Puzzle

Vidi također

Izvori

Svi članci →