🧩 Regulile Sudoku
O grilă 9×9 împărțită în 9 boxuri 3×3. Trebuie completată cu cifrele 1–9 astfel încât:
📌 Fiecare rând conține cifrele 1–9 o singură dată
📌 Fiecare coloană conține cifrele 1–9 o singură dată
📌 Fiecare box 3×3 conține cifrele 1–9 o singură dată
🔁 Abordarea BKT
Căutăm prima celulă goală și încercăm cifrele 1–9. Dacă o cifră respectă toate regulile → o plasăm și continuăm recursiv.
Dacă nicio cifră nu e validă → backtrack: golim celula și revenim la cea anterioară.
Dacă nu mai avem celule goale → puzzle rezolvat!
💻 Cod C++ — Sudoku BKT
💻 Cod C++
#include <iostream>
using namespace std;
int x[10][10], sol = 0;
void CITIRE()
{
for(int i = 1; i <= 9; i++)
for(int j = 1; j <= 9; j++)
cin >> x[i][j];
}
int VALID(int r, int c, int v)
{
for(int i = 1; i <= 9; i++)
if(x[r][i] == v || x[i][c] == v) return 0;
int br = ((r-1)/3)*3+1, bc = ((c-1)/3)*3+1;
for(int i = br; i <= br+2; i++)
for(int j = bc; j <= bc+2; j++)
if(x[i][j] == v) return 0;
return 1;
}
void TIPAR()
{
sol++;
cout << "Solutia " << sol << ":" << endl;
for(int i = 1; i <= 9; i++) {
for(int j = 1; j <= 9; j++)
cout << x[i][j] << " ";
cout << endl;
}
}
void BCK(int r, int c)
{
if(r == 10) { TIPAR(); return; }
int nr = (c == 9) ? r+1 : r;
int nc = (c == 9) ? 1 : c+1;
if(x[r][c] != 0) { BCK(nr, nc); return; }
for(int v = 1; v <= 9; v++)
if(VALID(r, c, v)) {
x[r][c] = v;
BCK(nr, nc);
x[r][c] = 0;
}
}
int main()
{
CITIRE();
BCK(1, 1);
if(sol == 0) cout << "Nu exista solutie." << endl;
return 0;
}