Sudoku resolver (bruteforece, récursion)
Soyez le premier à donner votre avis sur cette source.
Snippet vu 4 985 fois - Téléchargée 18 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
- Sudoku resolver
- Resolver sudoku 9x9 - Meilleures réponses
- Resolver sudokus - Meilleures réponses
- Javascript : Sudoku resolver in javascript - CodeS SourceS - Guide
- Sudoku python tkinter - Guide
- Sudoku c++ - Guide
- Python sudoku - Guide
- Javascript sudoku - Guide
- Messages postés
-
385
- Date d'inscription
- lundi 27 février 2006
- Statut
- Membre
- Dernière intervention
- 21 août 2015
5Vous 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.