Il gioco si svolge in matrici, che chiamiamo matrici Sudoku di aspetto 9×9 (le griglie) le cui caselle possono contenere un elemento di un insieme di 9 oggetti distinguibili, oppure un ulteriore oggetto diverso dai precedenti. Per fissare i discorsi conveniamo che le righe e le colonne delle matrici siano individuate dagli interi da 1 a 9, che i nove oggetti siano gli interi dell'insieme '9' := {1, 2, 3, 4, 5, 6, 7, 8, 9}, che l'oggetto ulteriore sia denotato con la lettera b e che una casella contenente b sia detta casella bianca o vuota. Una matrice Sudoku M viene considerata suddivisa in 9 blocchi di aspetto 3×3 che denotiamo Bh,k con h,k = 1, 2, 3; il blocco Bh,k riguarda le righe relative agli indici 3h-2, 3h-1 e 3h e le colonne relative agli indici 3k-2, 3k-1 e 3k. In ogni riga, colonna e regione di una matrice Sudoku i valori interi non possono essere ripetuti.

Una istanza di Sudoku, detta anche griglia proposta o matrice incompleta, è una matrice Sudoku che presenta alcune celle bianche. Scopo del gioco è la trasformazione della griglia proposta in una matrice completa, cioè in una matrice priva di celle bianche e quindi tale che in ogni sua riga, colonna e regione compaiano tutti gli elementi di '9' (ciascuno una sola volta). Si osserva che una matrice Sudoku completa è un quadrato latino di ordine 9 avente per blocchi matrici 3×3 con i nove numeri da 1 a 9.

Affinché una matrice incompleta sia considerata valida, ai fini del gioco, è necessario che la soluzione sia univoca, ovvero non devono sussistere due o più soluzioni differenti.

È da notare che mentre una matrice "semplice" (con 35 numeri già inseriti) possiede una sola soluzione, una matrice "difficile", (con 20 numeri) può possedere più soluzioni: d'altra parte, una "matrice vuota", con soli spazi, ha ben 6.670.903.752.021.072.936.960 soluzioni.

Le soluzioni di una qualsiasi altra matrice incompleta sono un sottoinsieme delle soluzioni della matrice vuota. Un sistema relativamente semplice, anche se prettamente teorico, per risolvere il Sudoku è quello di generare tutte le soluzioni con la matrice vuota (con un programma per computer) e poi sovrapporre una matrice incompleta per vedere quali tra queste coincidono.

Storicamente questo gioco è un caso ben più facile da risolvere di un antico e famoso gioco di logica-matematica a cui si è dedicato anche Eulero; si tratta dei "quadrati greco-latini". In questo caso, a differenza del Sudoku, non vi sono griglie interne e l'unica condizione da rispettare è che in ogni riga ed in ogni colonna compaiano tutti i numeri da 1 ad n*n una volta ed una volta sola, dove n è la dimensione del quadrato (nel caso del Sudoku n=9). Inoltre occorre sovrapporre n soluzioni di questo tipo (dette quadrati latini) in modo che ciascuna casella abbia una n-upla distinta.

Al contrario di quanto spesso si afferma, il sudoku è un gioco di logica e non di matematica, né ha a che fare con i numeri. Le proprietà dei numeri non vengono mai utilizzate e neppure viene mai utilizzato il fatto che siano dei numeri. Per rendersi conto della cosa basta pensare che il gioco sarebbe esattamente identico se anziché i primi nove numeri si usassero le prime nove lettere dell'alfabeto oppure nove simboli diversi tra loro (non c'è nemmeno bisogno che tra i simboli sussista un ordine).