Sudoku en Javascript (Etape 1)

21 Avril 2017

par

Travis

Base :

Toujours dans l'idée de mettre en pratique mes connaissances basiques en Javascript, j'ai décidé de réaliser un Sudoku. Ceci est la première étape (certainement la plus simple), la génération d'une grille de Sudoku pleine. Les prochaines étant de vider certaines cases afin d'obtenir une grille (à solution unique) à remplir par le joueur, et de permettre le remplissage puis la vérification de la grille.

Pour la petite anecdote, l'idée m'est venue en jouant à Mass Effect Andromeda. Les puzzles que l'on rencontre au cours du jeu sont une simple variante du Sudoku. Les différences étant l'utilisation de symboles au lieu de chiffres, et le nombre de cases réduit (4x4 et 5x5 au lieu de 9x9). Il est donc fort probable que je crée quelque-chose de similaire lorsque mon algorithme de génération de Sudoku sera complet.

Je vais détailler ci-dessous ma démarche pour la génération de grilles complètes. A noter qu'il était important pour moi de créer quelque-chose de facilement modifiable et acceptant une base de 2 à 4. Tout étant au carré avec le Sudoku (en tout cas dans sa forme classique), cela donne des grilles de 4x4, 9x9 et 16x16. Gardez également à l'esprit qu'il s'agit ici encore de mes balbutiements en Javascript et que le résultat est par conséquent loin d'être vraiment optimisé.

Génération du tableau

Je commence par générer un tableau vide avec un nombre de cellules variant selon la base choisie avec un champ input de type number.

function sudokuTable() {
  var sudoku = document.getElementById('sudoku');
  var base = document.getElementById('base').value; // recupere la base choisie
  var baseP = Math.pow(base, 2); // base au carre
  sudoku.className = 'n' + base; // attribue une classe au sudoku pour varier
                                 // la mise en forme en fonction du nombre de
                                 // lignes/colonnes
  sudoku.innerHTML = ''; // Supprime le contenu du tableau (reset)
  for (var y = 0; y < baseP; y++) {
    var row = document.createElement('tr'); // cree une ligne
    for (var x = 0; x < baseP; x++) {
      var cell = document.createElement('td'); // cree une cellule
      row.appendChild(cell); // ajoute la cellule a la ligne
    }
    sudoku.appendChild(row); // ajoute la ligne au tableau
  }
}

La taille des cellules et la séparation entre les blocs (2x2, 3x3 ou 4x4) est gérée avec un peu de CSS.

#sudoku {
  margin: 0 auto;
  border-collapse: collapse; // Bordure commune entre cellules adjacentes
  border: 2px solid;
  font-size: 2.6rem;
  text-align: center;
}

#sudoku td {
  width: 4rem;
  height: 4rem;
  border: 1px solid;
}

#sudoku.n2 tr:nth-of-type(2n) td,
#sudoku.n3 tr:nth-of-type(3n) td,
#sudoku.n4 tr:nth-of-type(4n) td { // cellules positionnees toutes les
  border-bottom-width: 2px;        // 2,3 ou 4 lignes
}

#sudoku.n2 td:nth-of-type(2n),
#sudoku.n3 td:nth-of-type(3n),
#sudoku.n4 td:nth-of-type(4n) { // cellules positionnees toutes les
  border-right-width: 2px;      // 2,3 ou 4 colonnes
}

Remplissage de la grille

Ici, les choses se compliquent déjà car il y a pas mal de conditions à respecter. Premièrement, on veut générer une grille aléatoire, il faut donc s'assurer qu'elle sera quasiment toujours différente et que les grilles, même si différentes, ne suivent pas un pattern similaire. Ensuite il faut bien entendu respecter les règles du Sudoku, c'est à dire que chaque numéro ne peut apparaitre qu'une fois par ligne, par colonne et par bloc.

La méthode que j'ai employée consiste à remplir la grille de gauche à droite et de haut en bas avec un nombre aléatoire, tout en vérifiant qu'il n'est pas déjà présent dans la ligne, la colonne ou le bloc. Pour cela, je crée une boucle qui se répète pour chaque ligne, au sein de laquelle se trouve une autre boucle pour chaque cellule/colonne afin d'effectuer la même opération pour toutes les cases du Sudoku.

Pour cette opération, je crée un array nbArray contenant les nombres de 1 à n² (avec n = base) que je mélange ensuite. Je crée également un array nbFilled auquel j'ajoute tous les nombres déjà présents dans la ligne, la colonne et le bloc. Il ne me reste plus qu'à comparer les deux arrays pour déterminer les nombres compatibles avec la cellule actuelle.

Plutôt que de soustraire le contenu de nbFilled à nbArray, j'extrais simplement la première valeur de nbArray et vérifie sa présence dans nbFilled, si elle n'est pas présente j'affecte simplement cette valeur à la cellule actuelle. Si elle est présente dans nbFilled (autrement dit si le nombre figure déjà dans la ligne, la colonne ou le bloc) j'extrais la prochaine valeur de nbArray et réitère le processus.

function sudokuFill() {
  var sudoku = document.getElementById('sudoku');
  var rows = sudoku.getElementsByTagName('tr');
  var base = Number(document.getElementById('base').value);
  var baseP = Math.pow(base, 2);

  for (var y = 0; y < baseP; y++) { // pour chaque ligne
    var row = rows[y];
    var rowCells = row.getElementsByTagName('td');

    for (var x = 0; x < baseP; x++) { // pour chaque cellule/colonne
      var cell = rowCells[x];

      var nbArray = []; // Array 1 a n^2
      for (var i = 1; i <= baseP; i++) { nbArray.push(i); }
      nbArray.sort(function(a, b){return 0.5 - Math.random()}); // melange

      var nbFilled = []; // Nombres deja dans ligne, colonne ou bloc

      for (var j = 0; j < baseP; j++) { // pour chaque cellule dans la ligne
        var sCellContent = Number(rowCells[j].innerHTML);
        if (sCellContent > 0) {
          nbFilled.push(sCellContent); // ajoute les nombres presents
        }
      }

      for (j = 0; j < baseP; j++) { // pour chaque cellule dans la colonne
        var searchCell = rows[j].getElementsByTagName('td')[x];
        sCellContent = Number(searchCell.innerHTML);
        if (sCellContent > 0) {
          nbFilled.push(sCellContent); // ajoute les nombres presents
        }
      }

      var block = sudokuBlock(x, y, base); // determine le bloc (voir plus bas)
      var xMin = base * block[0]; var xMax = xMin + base;
      var yMin = base * block[1]; var yMax = yMin + base;
      for (j = xMin; j < xMax; j++) { // pour chaque colonne du bloc
        if (j == x) { continue }
        for (var k = yMin; k < yMax; k++) { // pour chaque ligne du bloc
          if (k == y) { continue }
          searchCell = rows[k].getElementsByTagName('td')[j];
          sCellContent = Number(searchCell.innerHTML);
          if (sCellContent > 0) {
            nbFilled.push(sCellContent); // ajoute les nombres presents
          }
        }
      }

      do { var nb = nbArray.shift(); }    // Extrait la prochaine valeur
      while (nbFilled.indexOf(nb) != -1); // tant qu'elle existe dans nbFilled
      cell.innerHTML = nb;
    }

  }
}

function sudokuBlock(x, y, n) { // x et y sont les coordonnees de la cellule
  var xBlock = Math.floor(x / n); // n est la base (2,3 ou 4)
  var yBlock = Math.floor(y / n);
  var block = [xBlock, yBlock];
  return block; // renvoie un array contenant les coordonnees du bloc
}

Cette approche présente cependant un problème. Le fait de choisir des nombres aléatoires pour chaque case et à chaque ligne peut créer une ligne (voire une grille) partiellement remplie qui ne peut pas être complétée en rescpectant les règles du Sudoku.

1	4	3	2
3	2	4	1
4	3	2

Dans l'exemple ci-contre chaque case a été remplie avec un nombre aléatoire , jusqu'à présent sans avoir de nombres identiques dans la même ligne, colone ou bloc. Cependant on peut bien voir que la dernière case de la troisième ligne ne pourra pas satisfaire ces conditions.

Pour cet exemple on peut simplement choisir de recommencer l'arrangement des nombres de la troisième ligne jusqu'à en obtenir un qui convient (comme 2, 3, 1, 4 ou 4, 1, 2, 3). Mais avec des Sudoku de base supérieure cela n'est pas toujours possible, il faut alors réarranger plusieurs lignes.

Dans un soucis de simplicité pour l'instant, j'ai choisi de recommencer la grille depuis la première ligne si un nombre de réarrangements consécutifs est dépassé.

function sudokuFill() {
  var base = Number(document.getElementById('base').value);
  var baseP = Math.pow(base, 2);
  var sudoku = document.getElementById('sudoku');
  var rows = sudoku.getElementsByTagName('tr');
  var retries = 0;
  var maxRetries = 3 * Math.pow(base, 3); //

  for (var y = 0; y < baseP; y++) { // pour chaque ligne

    do { // execute le remplissage de la ligne une fois avant la boucle
      var row = rows[y];
      var rowCells = row.getElementsByTagName('td');

      for (var x = 0; x < baseP; x++) {

      // morceau de code vu precedemment

      }

      var errors =  0; // compte le nb d'erreurs dans ligne
      for (j = 0; j < baseP; j++) {
        searchCell = rowCells[j];
        sCellContent = searchCell.innerHTML;
        if (sCellContent == 'undefined') { errors++; }
      }

      if (errors > 0) { // reset la ligne si erreur
        for (j = 0; j < baseP; j++) {
          cell = rowCells[j];
          cell.innerHTML = '';
        }
        retries++;
      }

      if (retries >= maxRetries) { // reset si trop d'erreurs d'affilee
        for (j = 0; j < baseP; j++) {
          for (k = 0; k < baseP; k++) {
            var resetCell = rows[k].getElementsByTagName('td')[j];
            resetCell.innerHTML = '';
          }
        }
        retries = 0; x = 0; y = 0;
      }

    } while (errors > 0); // repete le remplissage de la ligne si erreur
  }
}

Un meilleur réarrangement aléatoire

Avec ce code il est possible de générer une grille de sudoku pleine en un temps satisfaisant (pour un novice). Cependant j'ai rapidement remarqué que la première méthode que j'ai utilisé pour réarranger aléatoirement mon array est loin de donner des résultats acceptables. En effet array.sort(function(a, b){return 0.5 - Math.random()}); n'est pas si random, la grande partie du temps les nombres 7, 8 et 9 sont les trois derniers de la première ligne sur un Sudoku en base 3. J'ai donc effectué quelques recherches pour trouver une méthode donnant des résultats convenables sans avoir trop d'impact sur le temps de réarrangement.

La même méthode était mentionné sur toutes les pages que j'ai consulté : il s'agit du Fisher-Yates Shuffle, et plus particulièrement la version moderne implémentée par Durstenfeld. J'ai mis le lien de la page Wikipédia en anglais car la page en français est très limitée.

Voici mon implémentation en JavaScript :

function randomNumber(n) { // nombre aleatoire entre 0 et (n-1)
  return Math.floor(Math.random() * n);
}

function shuffle(array) { // Fisher-Yates-Durstenfeld Shuffle
  var shufArray = array;
  var lcv = array.length - 1; // Valeur de controle de la boucle
  var n, nElem, lastElem;
  for (; lcv >= 0; lcv--) {
    n = randomNumber(lcv + 1); // nb aleatoire entre 0 et lcv inclu
    nElem = shufArray[n]; // element a la position n
    lastElem = shufArray[lcv]; // Dernier element inchange
    shufArray.splice(n, 1, lastElem); // nElem --> lastElem
    shufArray.splice(lcv, 1, nElem); // lastElem --> nElem
  }
  return shufArray; // renvoie l'array melange
}

Le Fisher-Yates-Durstenfeld Shuffle a grandement amélioré le côté aléatoire de la génération de mes grilles de Sudoku, ce qui a par conséquent également réduit le temps moyen nécessaire pour réarranger correctement les nombres d'une ligne lorsque le premier mène a une impasse.

Légère optimisation (MàJ 21/05/17)

J'ai essayé d'optimiser un peu mon code pour limiter le nombre d'opérations et surtout éviter de toucher au DOM (Document Object Model) inutilement. En effet interagir (accès, création, suppression, modification) avec les éléments de la page est relativement lent, il est donc préférable de ne le faire que lorsque cela est vraiment nécessaire.

Auparavant chaque cellule de la grille de Sudoku était remplie une à une, en allant vérifier les nombres déjà présents dans les autres cellules. Cette méthode était pratique lors de ma première écriture du code car elle me permettait voir la grille se remplir étape par étape et donc de débugger plus facilement. Cependant cela augmentait grandement le nombre de lectures et de modifications du DOM et donc l'exécution du code dans son ensemble.

J'ai réécrit la fonction sudokuFill(), que j'ai séparée en deux étapes. Premièrement l'arrangement des nombres (uniquement dans des arrays cette fois-ci, et donc sans toucher au DOM), puis le remplissage du tableau sur la page. La méthode de génération en elle-même n'a pas changé.

function sudokuGenerate(base) {
  var baseP = Math.pow(base, 2);
  var sudokuArray = [];
  var retries = 0;
  var maxRetries = Math.pow(baseP, 2);

  for (var y = 0; y < baseP; y++) { // pour chaque ligne
    sudokuArray.push([]);

    for (var x = 0; x < baseP; x++) { // pour chaque cellule de la ligne

      var nbArray = []; // array 1 a n^2
      for (var i = 1; i <= baseP; i++) { nbArray.push(i); }
      nbArray = shuffle(nbArray);

      var nbFilled = [];
      var row = sudokuArray[y];
      var rowLength = row.length;

      for (i = 0; i < rowLength; i++) { // ajoute chaque nombre de la ligne
        nbFilled.push(row[i]);
      }

      for (i = 0; i < y; i++) {  // ajoute chaque nombre de la colonne
        row = sudokuArray[i];
        nbFilled.push(row[x]);
      }

      var block = sudokuBlock(x, y, base);
      var xMin = base * block[0]; var xMax = xMin + base;
      var yMin = base * block[1]; var yMax = yMin + base;

      for (var j = yMin; j < yMax; j++) { // ajoute chaque nombre du bloc
        if (j == y) {continue;}
        row = sudokuArray[j];
        if (row === undefined) {break;}
        for (i = xMin; i < xMax; i++) {
          if (i == x) {continue;}
          nbFilled.push(row[i]);
        }
      }

      do {
        var nb = nbArray.shift(); // nombre suivant si un double existe
      } while (nbFilled.indexOf(nb) != -1)

      row = sudokuArray[y];

      if (nb != undefined) {
        row.push(nb); // ajoute nb a la ligne actuelle
      } else {
        if (retries < maxRetries) {
          sudokuArray[y] = [];
          x = -1;
          retries++;
        } else {
          sudokuArray = [];
          sudokuArray.push([]);
          y = 0;
          x = -1;
          retries = 0;
        }
      }
    }
  }

  return sudokuArray;
}

function sudokuFill(base) {
  var sudokuGrid = sudokuGenerate(base);
  var baseP = Math.pow(base, 2);
  var tableRows = sudoku.getElementsByTagName('tr');

  for (var y = 0; y < baseP; y++) {
    var row = sudokuGrid[y];
    var tableRow = tableRows[y];
    var tableCells = tableRow.getElementsByTagName('td');

    for (var x = 0; x < baseP; x++) {
      cell = tableCells[x];
      cell.innerHTML = row[x];
    }
  }
}

Validation de la base (MàJ 21/05/17)

Afin d'éviter les problèmes liés à une base non appropriée (nombre non entier ou trop élevé par exemple) il était nécessaire de la valider avant l'exécution du code. Le nombre d'entrées acceptées étant faible, j'ai choisi d'utiliser un switch.

Je commence par récupérer la valeur du champ avec l'ID base, puis je la convertie en nombre pour être sûr qu'elle ne soit pas considérée comme une chaîne de caractères. J'utilise alors mon switch avec la valeur obtenue, s'il s'agit d'une des valeurs attendues j'appelle ma fonction reset(), dans le cas contraire j'alerte l'utilisateur que la valeur est incorrecte.

function sudokuBase() {
  var base = document.getElementById('base').value;
  base = Number(base);
  switch (base) {
    case 2:
    case 3:
    case 4:
      reset(base);
      break;
    default:
      window.alert('La base doit etre 2, 3 ou 4.');
  }
}

Code Final

Voici mon code final pour cette première étape. Gardez encore une fois à l'esprit qu'il ne s'agit ici que d'un de mes tous premiers exercices de JavaScript (et de code de manière générale) et que le résultat est par conséquent loin d'être parfait. Evidemment conseils et remarques sont bienvenus.

Les commentaires sont en anglais sur le code final car cela permet de limiter le nombre de caractères et d'éviter les caractères spéciaux.

var sudoku = document.getElementById('sudoku');

sudokuBase();

function randomNumber(n) { // random number from 0 to (n-1)
  return Math.floor(Math.random() * n);
}

function shuffle(array) { // Fisher-Yates-Durstenfeld Shuffle
  var shufArray = array;
  var lcv = array.length - 1; // loop control value
  var n, nElem, lastElem; // lastElem == Last unchanged element
  for (; lcv >= 0; lcv--) {
    n = randomNumber(lcv + 1);
    nElem = shufArray[n];
    lastElem = shufArray[lcv];
    shufArray.splice(n, 1, lastElem);
    shufArray.splice(lcv, 1, nElem);
  }
  return shufArray;
}

function sudokuTable(n) {
  sudoku.className = 'sudoku n' + n;
  sudoku.innerHTML = '';
  var baseP = Math.pow(n, 2);
  for (var y = 0; y < baseP; y++) {
    var row = document.createElement('tr');
    for (var x = 0; x < baseP; x++) {
      var cell = document.createElement('td');
      row.appendChild(cell);
    }
    sudoku.appendChild(row);
  }
}

function sudokuGenerate(base) {
  var baseP = Math.pow(base, 2);
  var sudokuArray = [];
  var retries = 0;
  var maxRetries = Math.pow(baseP, 2);

  for (var y = 0; y < baseP; y++) { // for each row
    sudokuArray.push([]);

    for (var x = 0; x < baseP; x++) { // for each cell in the row

      var nbArray = []; // array 1 to n^2
      for (var i = 1; i <= baseP; i++) { nbArray.push(i); }
      nbArray = shuffle(nbArray);

      var nbFilled = [];
      var row = sudokuArray[y];
      var rowLength = row.length;

      for (i = 0; i < rowLength; i++) { // adds every number in the row
        nbFilled.push(row[i]);
      }

      for (i = 0; i < y; i++) {  // adds every number in the column
        row = sudokuArray[i];
        nbFilled.push(row[x]);
      }

      var block = sudokuBlock(x, y, base);
      var xMin = base * block[0]; var xMax = xMin + base;
      var yMin = base * block[1]; var yMax = yMin + base;

      for (var j = yMin; j < yMax; j++) { // adds every number in the block
        if (j == y) {continue;}
        row = sudokuArray[j];
        if (row === undefined) {break;}
        for (i = xMin; i < xMax; i++) {
          if (i == x) {continue;}
          nbFilled.push(row[i]);
        }
      }

      do {
        var nb = nbArray.shift(); // next number until no duplicates
      } while (nbFilled.indexOf(nb) != -1)

      row = sudokuArray[y];

      if (nb != undefined) {
        row.push(nb); // Adds nb to the current row
      } else {
        if (retries < maxRetries) {
          sudokuArray[y] = [];
          x = -1;
          retries++;
        } else {
          sudokuArray = [];
          sudokuArray.push([]);
          y = 0;
          x = -1;
          retries = 0;
        }
      }
    }
  }

  return sudokuArray;
}

function sudokuFill(base) {
  var sudokuGrid = sudokuGenerate(base);
  var baseP = Math.pow(base, 2);
  var tableRows = sudoku.getElementsByTagName('tr');

  for (var y = 0; y < baseP; y++) {
    var row = sudokuGrid[y];
    var tableRow = tableRows[y];
    var tableCells = tableRow.getElementsByTagName('td');

    for (var x = 0; x < baseP; x++) {
      cell = tableCells[x];
      cell.innerHTML = row[x];
    }
  }
}

function sudokuBlock(x, y, n) {
  var xBlock = Math.floor(x / n);
  var yBlock = Math.floor(y / n);
  var block = [xBlock, yBlock];
  return block;
}

function reset(base) {
  sudokuTable(base);
  sudokuFill(base);
}

function sudokuBase() {
  var base = document.getElementById('base').value;
  base = Number(base);
  switch (base) {
    case 2:
    case 3:
    case 4:
      reset(base);
      break;
    default:
      window.alert('La base doit etre 2, 3 ou 4.');
  }
}