SDA Tema 4

Cornel se chinuie de două săptămâni să rezolve un joc de Sudoku, dar de fiecare dată când ajunge la final, observă că a greșit ceva și trebuie să o ia de la capăt. Pentru că deja nu mai are răbdare, Cornel se hotărăște să scrie un program în C care să rezolve jocul. Dar pentru că n-a învățat nimic la PC și SDA, are nevoie de ajutorul vostru.

Cerință

Dându-se o listă de căsuțe ce conțin valori implicite, se cere să se rezolve un joc de Sudoku și să se afișeze rezultatul.

Informații suplimentare

Sudoku este un joc care presupune completarea unei matrici de 9x9 elemente cu cifrele de la 1 la 9, astfel încât o cifră să nu se repete pe linie, pe coloană, sau într-o sub-matrice de 3x3. Un joc pleacă de cele mai multe ori cu o parte din locații completate inițial.

Date de intrare

În fișierul text sudoku.in se găsește pe prima linie numărul N de căsuțe constrânse și apoi pe următoarele N linii câte un tuplu de 3 valori reprezentând linia, coloana și valoarea de la poziția respectivă.

Ex:

32
1 1 3
1 3 6
1 4 5
1 6 8
1 7 4
2 1 5
2 2 2
3 2 8
3 3 7
3 8 3
3 9 1
4 3 3
4 5 1
4 8 8
5 1 9
5 4 8
5 5 6
5 6 3
5 9 5
6 2 5
6 5 9
6 7 6
7 1 1
7 2 3
7 7 2
7 8 5
8 8 7
8 9 4
9 3 5
9 4 2
9 6 6
9 7 3

Date de ieșire

În fișierul text sudoku.out se va scrie matricea rezolvată:

 3 1 6 5 7 8 4 9 2
 5 2 9 1 3 4 7 6 8
 4 8 7 6 2 9 5 3 1
 2 6 3 4 1 5 9 8 7
 9 7 4 8 6 3 1 2 5
 8 5 1 7 9 2 6 4 3
 1 3 8 9 4 7 2 5 6
 6 9 2 3 5 1 8 7 4
 7 4 5 2 8 6 3 1 9

Livrabile

Tema submisă va conține: unul sau mai multe fișiere .cpp/.c/.h care să fie compilabile pe cel puțin o platformă (sistem de operare + compilator), și un document pdf care să conțină o analiză a complexității în timp și spațiu.

Modalitatea de submitere

Tema va fi submisă pe e-mail, la adresa homework@dcae.pub.ro. Subiectul va fi [SDA-4][NUME][GRUPA]. Fișierele vor fi atașate mesajului, NEARHIVATE.

Atenție: Singurul fișier binar va fi documentul pdf. Orice alt binar (executabil, dll, so, etc.) atașat mesajului va face ca acesta să fie respins de server-ul de e-mail și în consecintă să nu primiți nici un punct pe temă.

Atenție: Temele vor fi verificate anti-plagiat cu soft-uri specializate. Orice temă copiată va fi penalizată (atât sursa cât și copia) cu 100% din punctaj, fără posibilitate de refacere.