Lui Vasilică îi plac jocurile și puzzle-urile, printre care și Sudoku. Prietenii lui știu asta, așa că i-au adus mai multe jocuri de Sudoku, să vadă dacă sunt completate corect. Prietenii lui i-au dat soluțiile într-un fișier text. Ajutați-l pe Vasilică să scrie un program care să verifice corectitudinea acestor soluții.
Cerință
Să se verifice dacă un joc de Sudoku este corect completat. Pot exista jocuri cu următoarele dimensiuni: 1×1, 4×4, 9×9, 16×16, 25×25, 36×36, 49×49, 64×64, 81×81 (pătrate perfecte).
Un joc de dimensiune n x n este corect, dacă respectă următoarele condiții:
- pe fiecare linie apar toate cele n caractere o singură dată
- pe fiecare coloana apar toate cele n caractere o singură dată
- în fiecare sub-pătrat de dimensiune sqrt(n) apar toate cele n o singură dată
- nu există mai mult de n caractere distincte într-o soluție
Caracterele folosite pentru completarea jocului sunt exclusiv din setul de caractere dat mai jos:
0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz$#?+~!@%^&*()[]+={}:;|
Se va ține cont de:
- pentru dimensiuni diferite de 16, se consideră caracterele începând de la 1, nu neapărat primele n caractere.
- pentru dimensiunea 16, se consideră caracterele începând de la 0 la F (în hexazecimal)
Formatul datelor de intrare și ieșire
Pe prima linie din fisierul de intrare se găsește numărul de jocuri, N. Pe următoarele linii, se găsesc N jocuri specificate prin:
- dimensiunea jocului ni
- soluția jocului (o matrice ni x ni )
Exemplu:
Intrare
3 1 1 4 1 2 3 4 4 3 2 1 3 1 2 4 2 1 4 3 9 1 2 3 4 5 6 7 8 9 4 5 6 7 8 9 1 2 3 7 8 9 1 2 3 4 5 6 2 3 4 5 6 7 8 9 1 5 6 7 8 9 1 2 3 4 8 9 1 2 3 4 5 6 7 3 4 5 6 7 8 9 1 2 6 7 8 9 1 2 3 4 5 9 1 2 3 4 5 6 7 8
Iesire
VALID INVALID VALID
Un exemplu de soluție invalidă este și acesta:
4 1 2 3 w 4 3 2 1 3 4 1 2 2 1 4 3
Autori: Florin Pop, Anca Bălănel
Data: 14.11.2009