Valid Sudoku

Description

[EN]

You are given a a 9 x 9 Sudoku board board. A Sudoku board is valid if the following rules are followed:

1. Each row must contain the digits 1-9 without duplicates.

2. Each column must contain the digits 1-9 without duplicates.

3. Each of the nine 3 x 3 sub-boxes of the grid must contain the digits 1-9 without duplicates.

Return true if the Sudoku board is valid, otherwise return false

Note: A board does not need to be full or be solvable to be valid.

Constraints:

• board.length == 9

• board[i].length == 9

• board[i][j] is a digit 1-9 or '.'.

[FR]

On vous donne un tableau Sudoku board de taille 9 x 9. Un tableau Sudoku est considéré comme valide si les règles suivantes sont respectées :

1. Chaque ligne doit contenir les chiffres de 1-9 sans répétitions.

2. Chaque colonne doit contenir les chiffres de 1-9 sans répétitions.

3. Chacune des neuf sous-grilles de 3 x 3 de la grille doit contenir les chiffres de 1-9 sans répétitions.

Retournez true si le tableau Sudoku est valide, sinon retournez false.

Remarque :
Un tableau n'a pas besoin d'être complètement rempli ou d'être résoluble pour être considéré comme valide.

Contraintes :

• board.length == 9 : Le tableau contient exactement 9 lignes.

• board[i].length == 9 : Chaque ligne contient exactement 9 colonnes.

• board[i][j] est soit un chiffre de 1-9, soit le caractère '.' (qui représente une case vide).

Approche 1: Brute Force

• Complexité temporelle: O(n³) 

• Complexité spatiale: O(1)

Une première solution consiste à comparer une à une les cases du tableaux en lignes, colonnes, sous-grilles en utilisant des boucles imbriquées

Approche 2: Utilisation de HashMap

• Complexité temporelle: O(n²) car parcours du tableau complet

• Complexité spatiale: O(n) car utilisation d'une HashMap

Une solution optimisée consiste à utiliser une HashMap pour la résolution: