Generaliseret Sudoku er et talpuslespil , der er en naturlig generalisering af Sudoku- puslespillet , når det drejer sig om et bord af vilkårlig størrelse.
Spillefeltet består af et kvadrat med størrelsen N ² × N ², opdelt i mindre firkanter med en side af N celler. Således har det samlede spillefelt N 4 celler. I nogle af dem er der i begyndelsen af spillet tal fra 1 til N² .
Opgaven er at fylde de frie celler med tal fra 1 til N², så i hver række, i hver kolonne og i hver lille firkant N × N hvert tal optræder nøjagtigt én gang.
Det generaliserede Sudoku -problem er NP-komplet . Problemet med at fylde den latinske firkant er reduceret til det .
| NP-komplette problemer | |
|---|---|
| Maksimeringsproblem ved stabling (pakning) |
|
| grafteori mængdeteori | |
| Algoritmiske problemer | |
| Logiske spil og puslespil | |