Programmation d'un Générateur Sudoku JavaScript

Créer un générateur de Sudoku en JavaScript combine algorithmes mathématiques, techniques de programmation avancées et optimisations de performance. Ce guide complet vous accompagne dans le développement d'un générateur professionnel capable de créer des puzzles de qualité.

🎯 Ce que vous allez apprendre

• Algorithmes de génération de grilles Sudoku
• Techniques de backtracking et optimisation
• Validation et assurance de solution unique
• Gestion de la difficulté et des patterns
• Interface utilisateur interactive

🏗️ Architecture du Générateur

Structure Modulaire Recommandée

Organisez votre code en modules spécialisés pour maintenir la clarté et permettre la réutilisation :

// Structure de projet recommandée
sudoku-generator/
├── src/
│   ├── core/
│   │   ├── SudokuGrid.js      // Classe grille principale
│   │   ├── Generator.js       // Algorithmes de génération
│   │   ├── Solver.js         // Résolveur et validation
│   │   └── Validator.js      // Vérification contraintes
│   ├── utils/
│   │   ├── arrayUtils.js     // Utilitaires tableaux
│   │   ├── mathUtils.js      // Fonctions mathématiques
│   │   └── patterns.js       // Patterns et symétries
│   └── ui/
│       ├── GridRenderer.js   // Affichage interface
│       ├── Controls.js       // Contrôles utilisateur
│       └── Export.js         // Export/sauvegarde
└── tests/
    └── generator.test.js     // Tests unitaires

💻 Implémentation de Base

Classe SudokuGrid Principale

Commençons par implémenter la classe fondamentale qui représente la grille Sudoku :

class SudokuGrid {
  constructor() {
    this.grid = Array(9).fill().map(() => Array(9).fill(0));
    this.size = 9;
    this.boxSize = 3;
  }

  // Vérifie si un nombre peut être placé à une position
  isValid(row, col, num) {
    return this.isValidRow(row, num) && 
           this.isValidCol(col, num) && 
           this.isValidBox(row, col, num);
  }

  // Validation ligne
  isValidRow(row, num) {
    return !this.grid[row].includes(num);
  }

  // Validation colonne  
  isValidCol(col, num) {
    for (let row = 0; row < this.size; row++) {
      if (this.grid[row][col] === num) return false;
    }
    return true;
  }

  // Validation région 3x3
  isValidBox(row, col, num) {
    const startRow = Math.floor(row / this.boxSize) * this.boxSize;
    const startCol = Math.floor(col / this.boxSize) * this.boxSize;
    
    for (let r = 0; r < this.boxSize; r++) {
      for (let c = 0; c < this.boxSize; c++) {
        if (this.grid[startRow + r][startCol + c] === num) {
          return false;
        }
      }
    }
    return true;
  }

  // Place un nombre dans la grille
  setCell(row, col, value) {
    if (this.isValid(row, col, value)) {
      this.grid[row][col] = value;
      return true;
    }
    return false;
  }

  // Copie profonde de la grille
  clone() {
    const newGrid = new SudokuGrid();
    newGrid.grid = this.grid.map(row => [...row]);
    return newGrid;
  }
}

Algorithme de Génération (Backtracking)

L'algorithme de backtracking est la méthode standard pour générer des solutions Sudoku complètes :

class SudokuGenerator {
  constructor() {
    this.grid = new SudokuGrid();
  }

  // Génère une solution complète
  generateSolution() {
    this.grid = new SudokuGrid();
    this.fillGrid(0, 0);
    return this.grid.clone();
  }

  // Remplissage récursif avec backtracking
  fillGrid(row, col) {
    // Fin de grille atteinte
    if (row === 9) return true;
    
    // Passage à la ligne suivante
    if (col === 9) return this.fillGrid(row + 1, 0);
    
    // Cellule déjà remplie
    if (this.grid.grid[row][col] !== 0) {
      return this.fillGrid(row, col + 1);
    }

    // Essai de chaque nombre dans un ordre aléatoire
    const numbers = this.getShuffledNumbers();
    
    for (const num of numbers) {
      if (this.grid.isValid(row, col, num)) {
        this.grid.grid[row][col] = num;
        
        if (this.fillGrid(row, col + 1)) {
          return true;
        }
        
        // Backtrack
        this.grid.grid[row][col] = 0;
      }
    }
    
    return false;
  }

  // Mélange les nombres pour la randomisation
  getShuffledNumbers() {
    const numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9];
    return this.shuffle(numbers);
  }

  // Algorithme de mélange Fisher-Yates
  shuffle(array) {
    const result = [...array];
    for (let i = result.length - 1; i > 0; i--) {
      const j = Math.floor(Math.random() * (i + 1));
      [result[i], result[j]] = [result[j], result[i]];
    }
    return result;
  }
}

🔧 Création de Puzzles Jouables

Retrait Stratégique de Chiffres

Transformer une solution complète en puzzle jouable nécessite de retirer des chiffres tout en maintenant une solution unique :

// Extension de la classe SudokuGenerator
generatePuzzle(difficulty = 'medium') {
  // Générer solution complète
  const solution = this.generateSolution();
  const puzzle = solution.clone();
  
  // Configuration difficulté
  const difficultySettings = {
    easy: { minClues: 45, maxClues: 50 },
    medium: { minClues: 35, maxClues: 44 }, 
    hard: { minClues: 25, maxClues: 34 },
    expert: { minClues: 17, maxClues: 24 }
  };
  
  const settings = difficultySettings[difficulty];
  const targetClues = Math.floor(Math.random() * 
    (settings.maxClues - settings.minClues + 1)) + settings.minClues;
  
  // Créer liste de positions à tenter
  const positions = this.generateRandomPositions();
  let cluesRemaining = 81;
  
  for (const pos of positions) {
    if (cluesRemaining <= targetClues) break;
    
    const [row, col] = pos;
    if (puzzle.grid[row][col] === 0) continue;
    
    // Sauvegarder valeur originale
    const originalValue = puzzle.grid[row][col];
    puzzle.grid[row][col] = 0;
    
    // Vérifier solution unique
    if (this.hasUniqueSolution(puzzle)) {
      cluesRemaining--;
    } else {
      // Restaurer si multiples solutions
      puzzle.grid[row][col] = originalValue;
    }
  }
  
  return {
    puzzle: puzzle,
    solution: solution,
    difficulty: difficulty,
    clues: cluesRemaining
  };
}

// Génère positions aléatoires avec préférence symétrique
generateRandomPositions() {
  const positions = [];
  
  // Ajouter toutes les positions
  for (let row = 0; row < 9; row++) {
    for (let col = 0; col < 9; col++) {
      positions.push([row, col]);
    }
  }
  
  return this.shuffle(positions);
}

✅ Validation et Résolution

Résolveur avec Comptage de Solutions

Pour garantir l'unicité de la solution, implémentez un résolveur qui compte le nombre de solutions possibles :

class SudokuSolver {
  constructor(grid) {
    this.grid = grid.clone();
  }

  // Compte le nombre de solutions possibles
  countSolutions(maxSolutions = 2) {
    return this.countSolutionsRecursive(0, 0, maxSolutions);
  }

  countSolutionsRecursive(row, col, maxSolutions) {
    if (row === 9) return 1; // Solution trouvée
    if (col === 9) return this.countSolutionsRecursive(row + 1, 0, maxSolutions);
    
    if (this.grid.grid[row][col] !== 0) {
      return this.countSolutionsRecursive(row, col + 1, maxSolutions);
    }

    let solutionCount = 0;
    
    for (let num = 1; num <= 9; num++) {
      if (this.grid.isValid(row, col, num)) {
        this.grid.grid[row][col] = num;
        
        solutionCount += this.countSolutionsRecursive(row, col + 1, maxSolutions);
        
        // Optimisation : arrêt précoce si trop de solutions
        if (solutionCount >= maxSolutions) {
          this.grid.grid[row][col] = 0;
          return solutionCount;
        }
        
        this.grid.grid[row][col] = 0;
      }
    }
    
    return solutionCount;
  }

  // Vérifie si la grille a exactement une solution
  hasUniqueSolution() {
    return this.countSolutions(2) === 1;
  }

  // Résout complètement le puzzle
  solve() {
    return this.solveRecursive(0, 0);
  }

  solveRecursive(row, col) {
    if (row === 9) return true;
    if (col === 9) return this.solveRecursive(row + 1, 0);
    
    if (this.grid.grid[row][col] !== 0) {
      return this.solveRecursive(row, col + 1);
    }

    for (let num = 1; num <= 9; num++) {
      if (this.grid.isValid(row, col, num)) {
        this.grid.grid[row][col] = num;
        
        if (this.solveRecursive(row, col + 1)) {
          return true;
        }
        
        this.grid.grid[row][col] = 0;
      }
    }
    
    return false;
  }
}

🚀 Optimisations de Performance

Techniques d'Accélération

Pre-remplissage Intelligent

Commencez par placer des patterns de base pour réduire l'espace de recherche

Ordre de Remplissage

Priorisez les cellules avec le moins de possibilités (heuristique MRV)

Cache des Contraintes

Maintenez des structures de données pour éviter les recalculs

Web Workers

Déportez la génération en arrière-plan pour éviter le blocage UI

Implémentation avec Web Workers

// worker.js - Web Worker pour génération
self.onmessage = function(e) {
  const { difficulty, count } = e.data;
  const generator = new SudokuGenerator();
  const puzzles = [];
  
  for (let i = 0; i < count; i++) {
    const puzzle = generator.generatePuzzle(difficulty);
    puzzles.push(puzzle);
    
    // Progression
    self.postMessage({
      type: 'progress',
      completed: i + 1,
      total: count
    });
  }
  
  // Résultat final
  self.postMessage({
    type: 'complete',
    puzzles: puzzles
  });
};

// Utilisation côté principal
class AsyncSudokuGenerator {
  generatePuzzlesAsync(difficulty, count) {
    return new Promise((resolve, reject) => {
      const worker = new Worker('worker.js');
      
      worker.postMessage({ difficulty, count });
      
      worker.onmessage = function(e) {
        if (e.data.type === 'complete') {
          resolve(e.data.puzzles);
          worker.terminate();
        } else if (e.data.type === 'progress') {
          // Callback de progression
          this.onProgress?.(e.data.completed, e.data.total);
        }
      };
      
      worker.onerror = reject;
    });
  }
}

🎨 Interface Utilisateur Interactive

Rendu de Grille HTML/CSS

Créez une interface utilisateur moderne et responsive pour votre générateur :

class SudokuRenderer {
  constructor(containerSelector) {
    this.container = document.querySelector(containerSelector);
    this.grid = null;
    this.selectedCell = null;
  }

  renderGrid(sudokuGrid, isEditable = false) {
    this.grid = sudokuGrid;
    this.container.innerHTML = '';
    this.container.className = 'sudoku-grid';
    
    for (let row = 0; row < 9; row++) {
      for (let col = 0; col < 9; col++) {
        const cell = this.createCell(row, col, isEditable);
        this.container.appendChild(cell);
      }
    }
  }

  createCell(row, col, isEditable) {
    const cell = document.createElement('div');
    cell.className = this.getCellClasses(row, col);
    cell.dataset.row = row;
    cell.dataset.col = col;
    
    const value = this.grid.grid[row][col];
    cell.textContent = value === 0 ? '' : value;
    
    if (isEditable && value === 0) {
      cell.contentEditable = true;
      cell.addEventListener('input', this.handleCellInput.bind(this));
      cell.addEventListener('click', this.handleCellClick.bind(this));
    }
    
    return cell;
  }

  getCellClasses(row, col) {
    let classes = ['sudoku-cell'];
    
    // Bordures épaisses pour régions 3x3
    if (row % 3 === 0) classes.push('border-top');
    if (col % 3 === 0) classes.push('border-left');
    if (row === 8) classes.push('border-bottom');
    if (col === 8) classes.push('border-right');
    
    return classes.join(' ');
  }

  handleCellInput(event) {
    const cell = event.target;
    const row = parseInt(cell.dataset.row);
    const col = parseInt(cell.dataset.col);
    const value = parseInt(cell.textContent) || 0;
    
    if (value >= 1 && value <= 9) {
      if (this.grid.isValid(row, col, value)) {
        this.grid.grid[row][col] = value;
        cell.classList.remove('error');
      } else {
        cell.classList.add('error');
        setTimeout(() => {
          cell.textContent = '';
          cell.classList.remove('error');
        }, 1000);
      }
    }
  }
}

📱 Application Complète

Interface de Contrôle

class SudokuApp {
  constructor() {
    this.generator = new SudokuGenerator();
    this.renderer = new SudokuRenderer('#sudoku-container');
    this.currentPuzzle = null;
    this.currentSolution = null;
    
    this.initializeUI();
  }

  initializeUI() {
    // Boutons de génération
    document.getElementById('generate-easy').addEventListener('click', 
      () => this.generatePuzzle('easy'));
    document.getElementById('generate-medium').addEventListener('click', 
      () => this.generatePuzzle('medium'));
    document.getElementById('generate-hard').addEventListener('click', 
      () => this.generatePuzzle('hard'));
    
    // Boutons d'action
    document.getElementById('solve').addEventListener('click', 
      () => this.showSolution());
    document.getElementById('validate').addEventListener('click', 
      () => this.validateCurrentGrid());
    document.getElementById('export').addEventListener('click', 
      () => this.exportPuzzle());
  }

  async generatePuzzle(difficulty) {
    this.showLoading(true);
    
    try {
      const result = this.generator.generatePuzzle(difficulty);
      this.currentPuzzle = result.puzzle;
      this.currentSolution = result.solution;
      
      this.renderer.renderGrid(this.currentPuzzle, true);
      this.updateStats(result);
      
    } catch (error) {
      console.error('Erreur génération:', error);
    } finally {
      this.showLoading(false);
    }
  }

  showSolution() {
    if (this.currentSolution) {
      this.renderer.renderGrid(this.currentSolution, false);
    }
  }

  validateCurrentGrid() {
    const solver = new SudokuSolver(this.renderer.grid);
    const isComplete = this.isGridComplete();
    const isValid = this.isGridValid();
    
    this.showValidationResult(isComplete && isValid);
  }

  exportPuzzle() {
    if (this.currentPuzzle) {
      const data = {
        puzzle: this.currentPuzzle.grid,
        solution: this.currentSolution.grid,
        timestamp: new Date().toISOString()
      };
      
      this.downloadJSON(data, 'sudoku-puzzle.json');
    }
  }
}

⚡ Optimisations Importantes

• Utilisez des Web Workers pour éviter le blocage UI
• Implémentez un cache pour les grilles génération
• Optimisez la validation avec des bitmasks
• Utilisez requestAnimationFrame pour les animations

Code Source Complet

Téléchargez l'implémentation complète

Applications Avancées

Créez des applications mobiles et web

Fonctionnalités Avancées

Une fois les bases maîtrisées, explorez des fonctionnalités comme la génération de variantes (Killer Sudoku, X-Sudoku), l'analyse de difficulté sophistiquée, et l'intégration d'intelligence artificielle pour optimiser la qualité des puzzles.

Félicitations ! Vous avez maintenant toutes les connaissances pour créer un générateur Sudoku professionnel en JavaScript !

Générateur de Sudoku en JavaScript