Valid Sudoku (LeetCode 36) vous donne une grille 9 par 9 partiellement remplie et vous demande si les cellules remplies enfreignent une règle du sudoku. Vous n'avez pas à résoudre le puzzle. Vous vérifiez seulement qu'aucun chiffre ne se répète dans une ligne, une colonne ou un carré 3 par 3. Une seule passe avec trois ensembles de chiffres déjà vus suffit en O(81), ce qui est constant.
Le problème
La grille est un tableau 9 par 9 de caractères, chacun étant un chiffre de 1 à 9 ou . pour une case vide. Retournez true si les cellules remplies respectent ces règles :
- Chaque ligne n'a aucun chiffre répété.
- Chaque colonne n'a aucun chiffre répété.
- Chaque carré 3 par 3 n'a aucun chiffre répété.
Une grille peut être valide même si elle n'a aucune solution. Seules les cellules remplies sont vérifiées.
Approche : trois ensembles par unité
Gardez un ensemble de chiffres déjà vus pour chaque ligne, chaque colonne et chaque carré. Pour chaque cellule remplie, vérifiez le chiffre dans les trois ensembles, et ajoutez-le s'il est nouveau.
La seule partie qui demande réflexion est l'indice du carré. Pour une cellule à la ligne r et à la colonne c, le numéro du carré est (r // 3) * 3 + c // 3. Il compte les carrés de gauche à droite, de haut en bas, de 0 à 8.
def is_valid_sudoku(board):
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
for r in range(9):
for c in range(9):
ch = board[r][c]
if ch == ".":
continue
b = (r // 3) * 3 + c // 3
if ch in rows[r] or ch in cols[c] or ch in boxes[b]:
return False
rows[r].add(ch)
cols[c].add(ch)
boxes[b].add(ch)
return True
Trace
Supposons que la ligne 0 ait un 5 à la colonne 0 et un autre 5 à la colonne 4. Le premier 5 est ajouté à rows[0], cols[0] et boxes[0]. À la colonne 4, le test ch in rows[0] est vrai, donc la fonction retourne false immédiatement. Les chiffres identiques dans le même carré ou la même colonne sont détectés de la même façon par les deux autres ensembles.
Complexité
La grille fait toujours 9 par 9, donc le temps est constant, 81 visites de cellules. Si vous généralisez à une grille n par n, c'est O(n au carré) en temps et O(n au carré) en espace. Mentionnez les deux, car les recruteurs demandent souvent comment cela passe à l'échelle.
Variantes que les recruteurs demandent
| Variante | Ce qui change |
|---|---|
| Utiliser moins de mémoire | Stocker chaque unité comme un entier de 9 bits et tester les bits avec 1 << digit |
| Vérifier un seul coup | Vérifier seulement la ligne, la colonne et le carré de la cellule modifiée |
| Résoudre le sudoku (LeetCode 37) | Les mêmes vérifications, plus un backtracking sur les cellules vides |
| Grilles plus grandes | La taille du carré devient la racine carrée de n, donc l'indice du carré l'utilise |
La version avec bitmask remplace chaque ensemble par un entier. mask & (1 << d) teste un chiffre et mask |= 1 << d l'enregistre. C'est plus rapide, mais la version avec ensembles est plus facile à écrire correctement sous pression, donc commencez par celle-là.
Erreurs courantes
- Vérifier les lignes et les colonnes mais oublier les carrés.
- Une mauvaise formule de carré, comme r // 3 + c // 3, qui donne le même indice à des carrés différents.
- Traiter . comme un chiffre, si bien que deux cellules vides comptent comme une répétition.
- Essayer de résoudre la grille alors que la question ne demande que sa validité.
Cas limites à tester
| Entrée | Attendu |
|---|---|
| Grille vide (que des .) | true |
| Grille entièrement remplie et valide | true |
| Répétition dans une ligne seulement | false |
| Répétition dans une colonne seulement | false |
| Répétition dans un carré seulement, lignes et colonnes différentes | false |
| Grille valide mais sans solution | true |
Comment l'expliquer en entretien
- Reformulez les règles et précisez que vous validez seulement, sans résoudre.
- Nommez les trois unités et dites que chacune a besoin d'un ensemble de chiffres vus.
- Donnez la formule de l'indice du carré et expliquez-la avec un exemple.
- Écrivez la passe unique et le retour anticipé.
- Énoncez la complexité et proposez la version avec bitmask si on vous la demande.
J'ai testé le code ci-dessus contre une vérification simple des lignes, colonnes et carrés sur 20 000 grilles aléatoires, certaines valides et d'autres volontairement erronées, avant de publier. Un contrôle aléatoire rapide comme celui-ci est une bonne habitude à prendre quand vous vous entraînez.
Entraînement associé
Consultez notre aide-mémoire Big O pour les termes de complexité, la liste LeetCode Blind 75 pour savoir quoi travailler ensuite, et le guide de l'assistant d'entretien de codage pour vous entraîner.
Déroulez votre approche à voix haute pendant que vous codez. Une transcription montre si vous avez énoncé l'observation clé avant d'écrire. Respectez les règles de l'employeur sur les outils d'IA lors de toute évaluation en direct.
Entraînez-vous aux entretiens de codage avec YesToTheOffer
Expliquez votre approche à voix haute, puis relisez votre transcription ensuite. 30 minutes gratuites, sans abonnement.
