Sudoku resolver (bruteforece, récursion)
Soyez le premier à donner votre avis sur cette source.
Snippet vu 4 674 fois - Téléchargée 17 fois
Contenu du snippet
Un bout de code qui trouve la solution d'un sudoku en utilisant une fonction récursive (brute force en gros);
mini & clean code intéressant si vous voulez comprendre l’intérêt des fonctions récursives.
j'utilise console.log et console.time pour profiler
Donc la solution est dans la console (chrome & firefox avec firebug)
sur chrome il touve la solution dans un peu pres 240ms et firefox 520ms).
mini & clean code intéressant si vous voulez comprendre l’intérêt des fonctions récursives.
j'utilise console.log et console.time pour profiler
Donc la solution est dans la console (chrome & firefox avec firebug)
sur chrome il touve la solution dans un peu pres 240ms et firefox 520ms).
Source / Exemple :
<html>
<body>
Sudoku resolver (la solution est dans la console!);
<script type="text/javascript">
var grille = [[9,0,0,1,0,0,0,0,5],
[0,0,5,0,9,0,2,0,1],
[8,0,0,0,4,0,0,0,0],
[0,0,0,0,8,0,0,0,0],
[0,0,0,7,0,0,0,0,0],
[0,0,0,0,2,6,0,0,9],
[2,0,0,3,0,0,0,0,6],
[0,0,0,2,0,0,9,0,0],
[0,0,1,0,0,4,5,7,0]];
var stackCache = [];
stackCache.push(grille);
console.time('time to resolve sudoku');
resolve();
console.timeEnd('time to resolve sudoku');
function resolve(){
if(stackCache.length == 0){
console.warn("Error, stackCache is empty");
return false;
}
var stack = stackCache.pop();
for(var i=0; i<9; i++){
for(var j=0; j<9; j++){
if(stack[i][j] == 0){
var nums = getPossibleNumbers(i, j, stack);
if(nums.length == 1 && i == 8 && j == 8){
stack[8][8] = nums[0];
return stack;
}
if(nums.length > 0){
for(var index in nums){
var innerStack = clone(stack);
innerStack[i][j] = nums[index];
stackCache.push(innerStack);
};
}
return resolve();
}
}
}
}
function getPossibleNumbers(idx, idy, stack){
var ret = [];
for(var num=1; num<=9; num++){
if(isValid(idx, idy, stack, num)){
ret.push(num);
}
}
return ret;
}
//to clone stack not make reference;
function clone(stack){
var ret = [];
for(var idx in stack){
var val = stack[idx];
var tmp = [];
for(var j in val){
tmp.push(val[j]);
}
ret.push(tmp);
}
return ret;
}
function isValid(idx, idy, stack, val){
return !(getLineValues(idx, stack).indexOf(val) > -1 || getColValues(idy, stack).indexOf(val) > -1 || getBlockValues(idx, idy, stack).indexOf(val) > -1);
}
function getLineValues(idx, stack){
return stack[idx];
}
function getColValues(idy, stack){
var ret = [];
for(var x=0; x<9; x++){
ret.push(stack[x][idy]);
}
return ret;
}
function getBlockValues(idx, idy, stack){
var ret = [];
var startX = 3 * (Math.floor(idx/3));
var startY = 3 * (Math.floor(idy/3));
for(var x=startX; x<(startX+3); x++){
for(var y=startY; y<(startY+3); y++){
ret.push(stack[x][y]);
}
}
return ret;
}
</script>
</body>
</html>
A voir également
- Recursion javascript
- Sudoku resolver - Meilleures réponses
- Javascript : Sudoku resolver in javascript - CodeS SourceS - Guide
- Solution de tous les sudoku ,recursive, tres bien commenté - Codes sources - Visual Basic / VB.NET (Divers)
- C / C++ / C++.NET : Résolution sudoku (9x9) par backtracking récursif intelligent - C - Guide
- Pgcd recursif en c - Guide
- Algorithme fonction puissance recursive - Conseils pratiques - PHP
Commentaire
- Messages postés
-
385
- Date d'inscription
- lundi 27 février 2006
- Statut
- Membre
- Dernière intervention
- 21 août 2015
2Vous n'êtes pas encore membre ?
inscrivez-vous, c'est gratuit et ça prend moins d'une minute !
Les membres obtiennent plus de réponses que les utilisateurs anonymes.
Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.
Le fait d'être membre vous permet d'avoir des options supplémentaires.