Algoritmi e Strutture Dati

Sudoku

Data una griglia di sudoku, devi verificare se sia valida.

Una griglia sudoku valida deve avere:

  • Tutti i numeri da 1 a 9 in ciascuna riga.

  • Tutti i numeri da 1 a 9 in ciascuna colonna.

  • Tutti i numeri da 1 a 9 all’interno delle celle .

Di conseguenza, una griglia sudoku non valida potrebbe presentare:

  • Numeri ripetuti in alcune righe.

  • Numeri ripetuti in alcune colonne.

  • Numeri ripetuti all’interno di alcune celle .

Screen Shot 2022-11-01 at 12.03.36 PM.png

Input

L’input contiene una griglia di numeri. Tutti i numeri inseriti sono interi compresi tra 0 e 9. Le celle vuote sono rappresentate come 0.

Output

Il programma deve stampare Valid se la griglia è valida, altrimenti Not valid.

Esempi

Ingresso

Uscita

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

Valid

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

Not valid

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue