Le jeux de Sodoku est un jeu très connu qu'on trouve souvent dans les dernières pages des journaux . Le mot Sodoku en lui même signifie chiffre unique en langue japonaise d'ou l'origine de ce jeu .
Dans cette première partie on s’intéressera a la résolution d'une grille de Sodoku classique voir une grille de 9x9 en utilisant un algorithme très simple en javascript.
Pour présenter la grille dans une page Web d'une manière interactive et sans grand effort je dirais ,on utilisera AngularJS .
Cette librairie va structurer l'application séparer les infrastructures , la présentation , la gestion des données et plus encore ,sans oublier le data binding Pour ce qui sont dans le brouillard a propos de AngularJS vous pouvez visiter le site ici
A fin d’améliorer la maintenabilité, la productivité et lisibilité simplement de l'application on adoptera le pattern MVVM pour ce qui veulent savoir plus sur ce pattern icipour commencer . MVVM dans AngularJS est très implicite et dont le présent exemple sera une illustration enfin j’espère !
Sodoku classique - Algorithme
Rappel
le jeux consiste en une grille carrée de 9x9 qui contient tous les chiffres de 1 à 9 qu'on appellera solution puis en cachant 20,30...cases selon la complicité qu'on
veux donner, on obtient une grille de jeu .
Sodoku s'énonce avec les règles suivantes :
- - Tous les chiffre de 1 à 9 sont présent une fois sur chaque ligne
- - Tous les chiffre de 1 à 9 sont présent une fois sur chaque colonne
- - Tous les chiffre de 1 à 9 sont présent une fois dans chaque sous grille de 3x3
Algorithme
L'algorithme qu'on va appliquer ici est un algorithme connu de résolution de grille de Sodoku avancer de deux pas et reculer d'un on avance quand même
la solution consiste en une grille (une matrice, un tableau)
de 9x9 cellule .
Chaque cellule est un objet composé de d'une valeur qui est un chiffre de 1 à 9 et d'un tableau de valeur possibles qui est un tableau de tous les chiffre de 1 à 9 .
le déroulement :
Pour chaque cellule :
tant que il y a des possibilités pour cette cellule :
prendre un nombre aléatoirement un chiffre dans le tableau des possibilités et le supprimer dans celui ci :
vérifier que :
si ce nombre est assigne a la valeur de la cellule :
- sur la ligne de cette cellule ce nombre n existe pas déjà
- de même sur la colonne
- dans la sous grille de 3x3 ce nombre n existe pas déjà
si le cas on a trouvé une valeur alors l assigner a la cellule et arrêter le tant que
sinon boucler le tant que
si après le tant que on a pas trouvé alors
réinitialiser les possibilités de la cellule
reculer d'une case
fin
Et voilà : on génère une solution pour une grille classique de 9x9 a chaque lancement
puis nous reste qu'a cacher certaines cellules pour faire un jeu bien sur .
Implémentation
Maintenant nous allons implémenter cet algorithme en JavaScript .
On imagine bien sur un objet Javascript composé d'un tableau a deux dimensions dont chaque élément est une cellule composée a son tours d'une valeur et un tableau de chiffre de 1 à 9
Une méthode public qui consiste a générer la solution et d'autres méthodes utilitaires
pour l'initialisation , la validation la génération de nombre aléatoirement ...
voici le code jusqu' a cette étape :
///<summary>
///Objet qui decrit une grille de Sodoku
///<summary>
var sodokuGrid= {
///<summary>
///Represente la grille en elle meme comme une matrice
///<summary>
matrix:null,
///<summary>
/// Un compteur qui servira dans les tests
///<summary>
counter:0,
size:9,
///<summary>
/// Un chrono pour les tests et les perfs
///<summary>
stopWatch:0,
///<summary>
/// generer une solution valide
///<summary>
///<param name="arg"></param>
///<return name="matrix">renvoie une matrice solution</return>
resolve:function(arg){
this.init(arg);
var allcells=this.size*this.size;
for(var i=0;i<allcells;i++){
var row = parseInt(i / 9);
var col = i - (row * 9);
this.counter++
var num = this.getNext(row,col);
if( num){
this.matrix[row][col].value =num ;
}else{
i-=2;
}
}
this.stopWatch=new Date()-this.stopWatch;
return this.matrix
},
///<summary>
///obtenir un nombre valid pour la cellule actuelle
///<summary>
///<param name="i">la ligne actuelle</param>
///<param name="j">la colonne actuelle</param>
///<return name="number">renvoie un nombre de 1 a 9 ou undefined </return>
getNext:function(i,j){
var len=this.matrix[i][j].poss.length
if(!len){
this.matrix[i][j].poss = this.getPossibilities();
return
}
var num = this.matrix[i][j].poss.splice(this.randomize(0,len), 1)[0]
if(this.isValid(i,j,num)){
return num
} else{
return this.getNext(i,j);
}
},
///<summary>
///verifie qu un nombre est valable pour la cellule
///<summary>
///<param name="i">la ligne actuelle</param>
///<param name="j">la colonne actuelle</param>
///<param name="num">le nombre a verifier</param>
///<return name="number">renvoie un nombre de 1 a 9 ou undefined</return>
isValid:function(i,j,num){
for(var k=0;k<j;k++){
if(this.matrix[i][k].value ==num)return false ;
};
for(var k=0;k<i;k++){
if(this.matrix[k][j].value==num)return false ;
};
var minJ=parseInt(j/3)*3,minI=parseInt(i/3)*3;
var maxJ=minJ+3,maxI=minI+3;
for(var l=minI;l<i;l++){
for(var m=minJ;m<maxJ;m++){
if(this.matrix[l][m].value==num)return false ;
}
}
return true;
},
///<summary>
///initialise la grille
///<summary>
init:function(){
this.matrix=new Array(this.size);
this.counter=0;
this.stopWatch=new Date();
var that=this;
this.matrix=new Array(this.size);
for(var j=0;j<this.size;j++){
this.matrix[j]=new Array(this.size);
for(var i=0;i<this.size;i++){
this.matrix[j][i]={
value:"",
poss:that.getPossibilities()
}
}
}
},
/// <summary>
///genere un tableau de possibiles de 1 a 9
/// <return name="Array" > renvoie un tableau </return>
getPossibilities: function(){
return [1,2,3,4,5,6,7,8,9] ;
},
/// <summary>
///genere un nombre aleatoire entre deux chiffres
/// <summary>
/// <param name="min" >la valeur basse</param>
/// <param name="max">la valeur haute</param>
/// <return name="Number" >renvoie entre le min et le mx </return>
randomize: function(min, max){
return parseInt(Math.random()*max)+min ;
}
}
Presentation d'une grille et tests
Nous allons maintenant créer une page HTML pour tester l'algorithme et visualiser une grille solution.
La page HTML sera une introduction a l'application AngularJS
Une application AngularJS se compose de modules , de contrôleurs ,de directives et de services .Chaque contrôleur possède un scope qui nous servira plus tard de ViewModel et sans oublier les Templates et pages HTML
Pour l instant notre page sera une simple page avec un contrôleur.
Venons au faites et voici a quoi ressemble la page
<html ng-app>
<!-- ng-app indique que l 'application utilise Angular-->
<head>
<title>SODOKU</title>
</head>
<body>
<div id="sodoku" style="width:400px; height:400px;" ng-controller="sodokuCtrl">
<!-- ng-controller indique le controlleur de cette partie est sodokuCtrl -->
<table width="100%" border="1">
<tr ng-repeat="row in matrix">
<td ng-repeat="col in row">{{col.value}}</td>
</tr>
</table>
<br/>
Nombre de boucles: <input ng-model="counter"/>
<br/>
Temps de génération en ms :<input ng-model="stopWatch"/>
</div>
<script type="text/javascript" src="http://ajax.googleapis.com/ajax/libs/angularjs/1.0.4/angular.min.js">
</script>
<script type="text/javascript" src="SodokuAlgo.js">
</script>
<script>
//c'est le controleur de la page
//qui est déclare sur le premier div
// le paramétré $scope est injecté par Angular et représente
// le scope de ce contrôleur
function sodokuCtrl($scope){
//Ici on compose le ViewModel
//la vue(page) a besoin d'une matrice(grille)
//d'un conteur de boucle qu'a parcouru l’algorithme pour générer la grille
//et d'un chrono pour afficher le temps mis
$scope.matrix=sodokuGrid.resolve();
$scope.counter=sodokuGrid.counter;
$scope.stopWatch=sodokuGrid.stopWatch;
}
</script>
</body>
</html>
Et voila la page qui permet de générer des solutions de grilles Sodoku et d'afficher
le nombre de boucles de tentatives qu'a mis l'algorithme pour résoudre et enfin le temps mis a chaque fois en millisecondes
Conclusion
c'est une brève introduction à AngularJS et un algorithme de résolution de sodoku assez optimal sur 1000000 de tests effectué la moyenne de boucles de génération
est de 185 qui veut dire qu on retrouve 81 cases en 185 tentatives et sur un processeur de 2.3GHz et avc Google Chrome comme navigateur le temps moyen pour générer
une grille est moins de 3 ms
A la prochaine partie
