Sudoku generalizat

Sudoku generalizat este un puzzle numeric care este o generalizare naturală a puzzle-ului Sudoku pentru cazul unei table de dimensiuni arbitrare.

Regulile jocului

Terenul de joc este format dintr-un pătrat de dimensiunea N² × N² , împărțit în pătrate mai mici cu o latură de N celule. Astfel, terenul de joc total are N 4 celule. În unele dintre ele, la începutul jocului, există numere de la 1 la N² .

Sarcina este să umpleți celulele libere cu numere de la 1 la N², astfel încât în fiecare rând, în fiecare coloană și în fiecare pătrat mic N × N fiecare număr să apară exact o dată.

Complexitatea computațională a problemei

Problema generalizată de Sudoku este NP-completă . Problema umplerii pătratului latin se reduce la ea .

Note

Link -uri

Dovada completității NP a problemei generalizate de Sudoku

Probleme NP-complete
Problema de maximizare a stivuirii (ambalării)	Ambalare in containere ambalare bidimensională ambalare liniară ambalare după greutate ambalare după valoare Problema rucsacului
teoria grafurilor teoria multimelor	Problemă de acoperire a vârfurilor Faceți clic pe problemă Problema unei multimi (multimi) independente Setați problema acoperirii Problema lui Steiner Problema vânzătorului ambulant Problemă generalizată a vânzătorului ambulant
Probleme algoritmice	Problemă de satisfacție pentru formulele booleene (în formă normală conjunctivă)
Jocuri de logică și puzzle-uri	Etichete generalizate (joc în N 2 -1) cea mai scurta solutie problema Probleme ale căror soluții sunt aplicate în Tetris Problemă generalizată de Sudoku Problemă de umplere a pătratului latin Sarcina lui Kakuro
Clasele de dificultate Cercetare operațională Optimizare Optimizare combinatorie Matematică aplicată Teoria algoritmilor Programare dinamică 21 Problemă Karp NP-completă