Matematikken
Hvis man generaliserer problemet med at løse Sudoku'er, hvor der er 9x9 felter og 3x3 kasser, til at løse problemet med en n²xn² plade med nxn kasser, så er det NP-komplet. Hvis spillepladen har en endelig størrelse, er der et endeligt antal mulige løsninger og problemet kan løses vha. en deterministisk endelig automat, som kender træet for hele spillet, som er en måde at udtrykke alle de mulige løsninger på. Antallet af mulige løsninger for n=3, en Sudoku-plade, er dog ret stort og træet er dermed også ret stort. Bertram Felgenhauer har beregnet, at der er 6,670,903,752,021,072,936,960 mulige løsninger for en Sudoku-plade. Tallet er lig 9! × 72^2 × 2^7 × 27,704,267,971 og man er kommet frem til det vha. logik og brute force udregninger, dvs. at man har prøvet alle muligheder igennem. Ed Russell har verificeret disse udregninger, som desuden er blevet simplificeret noget af Frazer Jarvis.Det at løse en Sudoku kan udtrykkes som det at lave en graf-farvning ("graph colouring problem").
Grafen, der skal udtrykke en Sudoku, har 81 knuder, en for hvert felt i Sudoku'en. Hver knude får tilknyttet et ordnet par (x,y), hvor x og y er heltal mellem 1 og 9.
To forskellige knuder, der har henholdvis (x,y) og (x′, y′) tilknyttet, har en kant mellem sig, hvis og kun hvis:
x=x′ eller
y=y′ eller
⌈x/3⌉=⌈x′/3⌉ og ⌈y/3⌉=⌈y′/3⌉
Man skal så, givet en partiel 9-farvning af en bestemt graf, lave en 9-farvning af hele grafen. I denne graf betyder det, at man får givet en graf på ovenstående form, hvor nogle af knuderne indeholder et heltal mellem 1 og 9. Man skal så give de resterende knuder et heltal mellem 1 og 9, så knuder, der har en kant mellem sig, ikke indeholder det samme heltal.
Det højeste antal på forhånd givne tal, man kan have i en Sudoku, så der kan være mere en een løsning, er 77. Det mindste antal på forhånd givne tal, der kan gøre løsningen i en Sudoku unik, har man endnu ikke fundet, men det laveste man har fundet indtil videre er 17, hvis tallene ikke står symmetrisk og 18, hvis de står symmetrisk. Eksperter definer en minimal Sudoku som en Sudoku, hvor det ikke er muligt at fjerne nogen af de givne tal uden at det resulterer i en Sudoku med multiple løsninger.
