Approche par marquage avec ensembles de bits

Une solution élégante consiste à utiliser trois tableaux de masques de bits pour suivre les présences respectivement dans les lignes, les colonnes et les sous-grilles. Cette technique évite les réinitialisations répétées et offre une complexité temporelle en O(1) avec un espace constant.

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& grille) {
        int ligne[9] = {0};
        int colonne[9] = {0};
        int bloc[9] = {0};
        
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                if (grille[i][j] == '.') continue;
                
                int chiffre = grille[i][j] - '1';
                int masque = 1 << chiffre;
                int idxBloc = (i / 3) * 3 + (j / 3);
                
                if ((ligne[i] & masque) || 
                    (colonne[j] & masque) || 
                    (bloc[idxBloc] & masque)) {
                    return false;
                }
                
                ligne[i] |= masque;
                colonne[j] |= masque;
                bloc[idxBloc] |= masque;
            }
        }
        return true;
    }
};

Alternative avec table de hachage

Pour une approche plus explicite, on peut utiliser des ensembles pour chaque ligne, colonne et bloc :

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& grille) {
        unordered_set<int> vueLigne[9];
        unordered_set<int> vueColonne[9];
        unordered_set<int> vueRegion[9];
        
        for (int rang = 0; rang < 9; ++rang) {
            for (int colonne = 0; colonne < 9; ++colonne) {
                char symbole = grille[rang][colonne];
                if (symbole == '.') continue;
                
                int valeur = symbole - '0';
                int idRegion = (rang / 3) * 3 + colonne / 3;
                
                if (!vueLigne[rang].insert(valeur).second) return false;
                if (!vueColonne[colonne].insert(valeur).second) return false;
                if (!vueRegion[idRegion].insert(valeur).second) return false;
            }
        }
        return true;
    }
};

Version Python condensée

En Python, la vérification peut s'écrire de manière très compacte :

class Solution:
    def isValidSudoku(self, grille: list[list[str]]) -> bool:
        rangees = [set() for _ in range(9)]
        colonnes = [set() for _ in range(9)]
        carres = [set() for _ in range(9)]
        
        for i in range(9):
            for j in range(9):
                case = grille[i][j]
                if case == '.':
                    continue
                    
                if case in rangees[i]:
                    return False
                rangees[i].add(case)
                
                if case in colonnes[j]:
                    return False
                colonnes[j].add(case)
                
                id_carre = (i // 3) * 3 + j // 3
                if case in carres[id_carre]:
                    return False
                carres[id_carre].add(case)
                
        return True

La clé pour identifier le bloc 3×3 d'une cellule située aux coordonnées (i, j) réside dans la formule (i // 3) * 3 + j // 3, qui projette les indices sur une grille 3×3 de régions.