Valid Sudoku

+10

Tu reçois une grille de Sudoku de 9 × 9 sous la 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. Renvoie true si aucun chiffre n’apparaît deux fois dans une ligne, une colonne ou un 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 case 3 × 3 ne contient plusieurs fois le même chiffre, faux sinon

Contraintes

board.length == 9 et board[i].length == 9
board[i][j] est un chiffre compris entre 1 et 9, ou .
Il peut être impossible de compléter le plateau ; 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: La ligne 4, en comptant à partir de 0, .74..89.3, contient une fois chacun des chiffres 7, 4, 8, 9 et 3, et aucun des 26 autres groupes ne répète non plus un chiffre.

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. Elles ne partagent ni ligne ni bloc, donc seul le contrôle de la colonne le détecte.

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 ne partagent ni ligne ni colonne, mais se trouvent tous deux dans le carré en haut à droite, donc la réponse est false.

Pour aller plus loin

Comment vérifieriez-vous un plateau de 16 × 16 avec des blocs de 4 × 4 et les symboles de 1 à 9 et de A à G ? 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 à trois groupes : sa ligne, sa colonne et sa boîte de 3 × 3. Les lignes et les colonnes sont faciles à indexer ; c’est dans la boîte que se cachent les bugs. Numérotez les boîtes de 0 à 8 avec (r / 3) * 3 + c / 3, et un seul passage sur les 81 cellules vérifie les 27 groupes.

Vérifiez chaque ligne, chaque colonne et chaque carré séparément

Intuition

La règle nomme 27 groupes : 9 lignes, 9 colonnes et 9 blocs. Rassemble les neuf cellules de chaque groupe et cherche un chiffre répété, en ignorant les points. Le plateau est valide exactement lorsqu’aucun groupe n’en contient.

Un indicateur par chiffre permet de repérer une répétition parmi neuf cellules. Chacune des 81 cellules est lue une fois pour chacun de ses trois groupes : 243 lectures, une quantité de travail fixe. Sur un plateau n × n, la même méthode coûte O(n²).

Algorithme

Pour i de 0 à 8, collectez la ligne i, la colonne i et le bloc i.
Le bloc i a son coin en ligne 3 * (i / 3), colonne 3 * (i % 3) ; sa cellule k se trouve k / 3 lignes plus bas et k % 3 colonnes à droite.
Parcourez chaque groupe avec des indicateurs « déjà vu » réinitialisés, en ignorant les points. Si un chiffre est déjà marqué, 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

Parcourez chaque cellule une fois et posez les trois questions simultanément. Gardez trois tableaux de 9 × 9 indicateurs : 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.

La cellule (r, c) appartient à la boîte (r / 3) * 3 + c / 3. La première partie sélectionne la bande de trois boîtes, et c / 3 sélectionne la boîte à l’intérieur de la bande. La cellule (4, 7) se trouve dans la boîte 1 * 3 + 2 = 5, celle du milieu à droite.

Un indicateur déjà activé signifie que le chiffre se répète dans ce groupe. Chaque cellule est lue une fois et les tableaux contiennent 243 indicateurs : temps et mémoire fixes ici, O(n²) sur un plateau n × n.

Algorithme

Créez seenRow, seenCol et seenBox, chacun de 9 × 9 et entièrement initialisé à false.
Pour chaque cellule remplie (r, c), soit d son chiffre moins 1 et b = (r / 3) * 3 + c / 3.
Si seenRow[r][d], seenCol[c][d] ou seenBox[b][d] est défini, renvoyez false ; sinon, définissez les trois.
Après la dernière cellule, renvoyez 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

Calculer le bloc comme r / 3 + c / 3. Cela ne donne que des valeurs de 0 à 4, donc (0, 3) et (3, 0) partagent un nombre alors que leurs blocs sont différents, et deux 7 à ces endroits sont signalés comme un doublon.
Diviser avec / en JavaScript, Python 3 ou Lua, où 4 / 3 vaut 1.33. Arrondissez à l'entier inférieur.
Considérer . comme une valeur. Un plateau vide, avec neuf points par ligne, est valide.
Essayer de résoudre la grille. Une ligne 0 contenant 12345678. avec un 9 plus bas dans la colonne 8 ne pourra jamais être complétée, et pourtant rien ne se répète : true.
Ignorer les blocs. 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 une ligne ou une colonne, alors que chaque bloc contient des répétitions.

Questions fréquentes3

Quelle est la complexité temporelle de Sudoku valide ?

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

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 sur une ligne, une colonne ou dans un bloc de 3 × 3 parmi les cases remplies. Une grille peut réussir cette vérification et ne pourtant avoir aucune solution. Déterminer si elle est résoluble nécessite une recherche, par exemple avec du retour sur trace, ce qui constitue un problème différent.

Le Sudoku valide peut-il être résolu avec des masques de bits ?

Oui. Attribue un entier à chaque ligne, colonne et bloc, où le bit d signifie que le chiffre d+1 a été vu. Pour une case remplie, si 1 << d donne un résultat non nul avec l’un de ses trois masques par une opération AND, le chiffre est répété ; sinon, fais un OR avec les trois masques. Cela fait 27 entiers au lieu de 243 indicateurs.

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

Test #1

Test #2

Test #3

Argument

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

Résultat attendu

true