Valid Sudoku

Q: Comment trouver dans quelle boîte 3 × 3 se trouve une cellule ?

Avec la division entière, r / 3 correspond à la bande de lignes (0, 1 ou 2) et c / 3 à la pile de colonnes. (r / 3) * 3 + c / 3 numérote les cases de 0 à 8, de gauche à droite et de haut en bas. La cellule (7, 1) se trouve dans la case 2 * 3 + 0 = 6 , celle en bas à gauche.

MoyenHachage

+10

On vous donne une grille de Sudoku de 9 × 9 sous forme de board, une liste de 9 chaînes de 9 caractères chacune, une chaîne par ligne. Chaque caractère est un chiffre de 1 à 9 ou . pour une case vide. Renvoyez true si aucun chiffre n’apparaît deux fois dans la même ligne, la même colonne ou le même carré de 3 × 3, et false sinon. Seules les cases remplies sont vérifiées : la grille n’a pas besoin d’être résoluble.

Fonction

isValidSudoku(board: string-array) → boolean

boardstring-array: 9 chaînes de 9 caractères, une par ligne, chiffres de 1 à 9 et . pour une case vide
Renvoieboolean: vrai si aucune ligne, colonne ou boîte 3 × 3 ne répète un chiffre, faux sinon

Contraintes

board.length == 9 et board[i].length == 9
board[i][j] est un chiffre de 1 à 9 ou .
Le plateau peut être impossible à compléter ; seules les répétitions parmi les cases remplies comptent.

Exemples

Entrée: board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]
Sortie: true
Explication: Chaque ligne, colonne et carré contient chaque chiffre au plus une fois. La ligne 4 (en comptant à partir de 0), .74..89.3, contient une seule fois chacun des chiffres 7, 4, 8, 9 et 3, et il en va de même pour les 26 autres groupes ; la réponse est donc true.

Entrée: board = ["3.64.....", "258..9..1", "...8.2...", "...9...43", ".6.1..28.", "....87.65", "8......24", "3.......6", "6....45.8"]
Sortie: false
Explication: La ligne 0 et la ligne 7 commencent toutes deux par un 3, donc la colonne 0 contient deux 3. Les deux cellules se trouvent dans des lignes et des blocs différents ; seule la vérification de la colonne permet de détecter ce problème.

Entrée: board = ["987..36.5", "2.6.8..13", ".1.64.75.", "8..261..4", "16.97.3.8", "..9.5..6.", "7.....49.", "..48.....", "5.1.....7"]
Sortie: false
Explication: Le 5 à la ligne 0, colonne 8 et le 5 à la ligne 2, colonne 7 se trouvent sur des lignes et des colonnes différentes, mais tous deux sont dans le carré supérieur droit, donc la réponse est false.

+16 tests cachés à la soumission

Pour aller plus loin

Généralisez la vérification à une grille de 16 × 16 avec des blocs de 4 × 4 et les symboles de 1 à 9 et de A à G. Quels nombres de votre code dépendent de la taille de la grille, et que devient la formule des blocs ?

Indices

Ouvrez-les un par un. Chacun en dévoile un peu plus.

0 sur 3 ouverts

Solution

Chaque chiffre appartient simultanément à trois groupes : sa ligne, sa colonne et son carré de 3 × 3. Les lignes et les colonnes sont faciles à indexer ; c’est dans les carrés que se trouvent la plupart des bogues. Numérote les carrés de 0 à 8 avec (r / 3) * 3 + c / 3 et un seul parcours des 81 cellules permet de vérifier les 27 groupes à la fois.

Vérifiez séparément chaque ligne, colonne et bloc.

Intuition

Les règles définissent 27 groupes : 9 lignes, 9 colonnes et 9 blocs. Rassemble les neuf cellules de chaque groupe et vérifie si un chiffre s’y répète, en ignorant les points. Si aucun groupe ne contient de répétition, la grille est valide.

La ligne i est board[i][0..8] et la colonne i est board[0..8][i]. Le bloc i commence à la ligne 3 * (i / 3) et à la colonne 3 * (i % 3), en utilisant la division entière, donc le bloc 5 commence à la ligne 3, colonne 6. Sa cellule k se trouve k / 3 lignes plus bas et k % 3 colonnes à droite de ce coin.

Pour trouver une répétition parmi neuf cellules, garde un indicateur pour chaque chiffre et arrête-toi au premier chiffre qui est déjà marqué. Chacune des 81 cellules est lue trois fois, une fois pour chaque groupe auquel elle appartient : 243 lectures, une quantité de travail fixe. Sur une grille n × n, la même méthode coûte O(n²).

Algorithme

Pour i de 0 à 8, récupérez la ligne i, la colonne i et la boîte i, neuf cellules chacune.
La boîte i commence à top = 3 * (i / 3) et left = 3 * (i % 3) ; sa cellule k se trouve à la ligne top + k / 3, colonne left + k % 3.
Pour chaque groupe, parcourez ses cellules avec des indicateurs « déjà vus » réinitialisés, en ignorant les points.
Si un chiffre est déjà signalé, renvoyez false.
Après les 27 groupes, renvoyez true.

def has_repeat(cells):
    seen = set()
    for ch in cells:
        if ch == '.':
            continue
        if ch in seen:
            return True
        seen.add(ch)
    return False


def isValidSudoku(board):
    for r in range(9):
        if has_repeat(board[r][c] for c in range(9)):
            return False
    for c in range(9):
        if has_repeat(board[r][c] for r in range(9)):
            return False
    for top in (0, 3, 6):
        for left in (0, 3, 6):
            box = (board[top + i][left + j] for i in range(3) for j in range(3))
            if has_repeat(box):
                return False
    return True

Un seul passage avec une table des éléments déjà vus pour chaque ligne, colonne et bloc

Intuition

Au lieu de constituer des groupes, parcourez chaque cellule une seule fois et posez les trois questions en même temps. Gardez trois tableaux de drapeaux de 9 × 9 : seenRow[r][d] indique que le chiffre d+1 est déjà présent dans la ligne r, et seenCol et seenBox fonctionnent de la même manière pour les colonnes et les blocs.

La cellule (r, c) appartient au bloc (r / 3) * 3 + c / 3. La première partie sélectionne la bande de trois blocs (les lignes 0 à 2 correspondent à la bande 0, les lignes 3 à 5 à la bande 1, et les lignes 6 à 8 à la bande 2), et c / 3 sélectionne le bloc à l'intérieur de la bande. La cellule (4, 7) se trouve dans le bloc 1 * 3 + 2 = 5, le bloc du milieu à droite.

Pour chaque cellule remplie, si l'un de ses trois drapeaux est déjà activé, le chiffre se répète dans ce groupe et vous renvoyez immédiatement false. Sinon, vous activez les trois. Chaque cellule est lue une seule fois et les tableaux contiennent 243 drapeaux ; le temps et la mémoire sont donc constants pour une grille de 9 × 9, et de O(n²) pour une grille de n × n.

Algorithme

Crée seenRow, seenCol et seenBox, chacun de 9 × 9 et rempli de valeurs false.
Parcours chaque cellule (r, c) ; ignore-la si elle contient un point.
Soit d le chiffre moins 1 et b = (r / 3) * 3 + c / 3.
Si seenRow[r][d], seenCol[c][d] ou seenBox[b][d] vaut true, retourne false.
Sinon, définis les trois à true. Après la dernière cellule, retourne true.

def isValidSudoku(board):
    # seen_row[r][d] is True once digit d + 1 appears in row r; same for columns and boxes.
    seen_row = [[False] * 9 for _ in range(9)]
    seen_col = [[False] * 9 for _ in range(9)]
    seen_box = [[False] * 9 for _ in range(9)]
    for r in range(9):
        for c in range(9):
            ch = board[r][c]
            if ch == '.':
                continue
            d = int(ch) - 1
            b = (r // 3) * 3 + c // 3
            if seen_row[r][d] or seen_col[c][d] or seen_box[b][d]:
                return False
            seen_row[r][d] = seen_col[c][d] = seen_box[b][d] = True
    return True

Pièges et cas limites

Les vérifications des lignes et des colonnes échouent rarement. Les erreurs se trouvent dans l’index des cases et dans ce qui est considéré comme une répétition.

Calculer la case avec r / 3 + c / 3. Cela ne donne que des valeurs de 0 à 4 : les cellules (0, 3) et (3, 0) ont donc le même numéro alors qu’elles se trouvent dans des cases différentes, et deux 7 à ces emplacements sont signalés comme une répétition. Utilisez (r / 3) * 3 + c / 3.
Faire une division avec / en JavaScript, Python 3 ou Lua, où 4 / 3 vaut 1.33, et non un numéro de case. Utilisez Math.floor, // ou math.floor.
Traiter . comme une valeur. Un plateau vide comporte neuf points dans chaque ligne, et il est valide.
Essayer de résoudre le puzzle. Avec 12345678. comme ligne 0 et un 9 plus bas dans la colonne 8, la dernière cellule de la ligne 0 ne peut jamais être remplie, mais aucun groupe ne répète de chiffre : la réponse est donc true.
Vérifier les lignes et les colonnes, mais pas les cases. Une grille complète où chaque ligne est la précédente décalée d’une place vers la gauche ne contient aucune répétition dans les lignes ni dans les colonnes, alors que chaque case contient des répétitions.

Questions fréquentes4

Quelle est la complexité temporelle de Valid Sudoku ?

La grille comporte toujours 81 cellules, donc les deux approches s’exécutent en temps O(1) et utilisent une mémoire O(1). Pour un Sudoku général de n × n, la vérification en un seul passage lit chacune des n² cellules une fois et conserve 3n² indicateurs ; elle est donc en O(n²) en temps et en mémoire.

Un plateau de Sudoku valide doit-il nécessairement être résoluble ?

Non. Valide signifie ici uniquement qu’aucun chiffre ne se répète dans une ligne, une colonne ou un carré de 3 × 3 parmi les cases déjà remplies. Une grille peut réussir cette vérification et n’avoir pourtant aucune solution. Déterminer si elle est soluble nécessite une recherche, par exemple avec un retour sur trace, ce qui constitue un problème différent.

Comment trouver dans quelle boîte 3 × 3 se trouve une cellule ?

Avec la division entière, r / 3 correspond à la bande de lignes (0, 1 ou 2) et c / 3 à la pile de colonnes. (r / 3) * 3 + c / 3 numérote les cases de 0 à 8, de gauche à droite et de haut en bas. La cellule (7, 1) se trouve dans la case 2 * 3 + 0 = 6, celle en bas à gauche.

Peut-on résoudre Valid Sudoku avec des masques de bits ?

Oui. Attribue un entier à chaque ligne, colonne et bloc, et considère que le bit d signifie que le chiffre d+1 a été vu. Pour une case remplie, calcule 1 << d ; si son ET binaire avec l’un des trois masques est non nul, le chiffre est répété ; sinon, applique un OU binaire aux trois masques. Cela fait 27 entiers au lieu de 243 indicateurs, avec la même logique en un seul passage.

Python

def isValidSudoku(board):
    # Écrivez le code ici

Cas de test

Cas 1

Cas 2

Cas 3

Entrée

board = [".19......", "..89...3.", ".3.8.....", ".5..6....", ".74..89.3", "....7....", ".2.5..19.", "1....3...", ".8......7"]

Attendu

true