Algorithmes et Structures de Données

Sudoku

Étant donné une grille de sudoku, vous devez déterminer si elle est valide.

Une grille de sudoku valide doit posséder :

  • Tous les nombres de 1 à 9 sur chaque ligne.

  • Tous les nombres de 1 à 9 sur chaque colonne.

  • Tous les nombres de 1 à 9 dans chacune des cellules .

Par conséquent, une grille de sudoku invalide peut présenter :

  • Des chiffres qui se répètent sur certaines lignes

  • Des chiffres qui se répètent sur certaines colonnes

  • Des chiffres qui se répètent dans les cellules

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

Input

L’entrée contient une grille de nombres. Tous les nombres remplis sont des entiers compris entre 0 et 9. Les cellules vides sont représentées par 0.

Output

Le programme doit imprimer Valid si la grille est valide, et Not valid sinon.

Examples

Entrée

Sortie

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