Sudoku resolver (bruteforece, récursion)

Soyez le premier à donner votre avis sur cette source.

Snippet vu 4 520 fois - Téléchargée 17 fois

Commenter

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).

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

Ajouter un commentaire

Commentaire

Signaler
amezghal
Messages postés
385
Date d'inscription
lundi 27 février 2006
Statut
Membre
Dernière intervention
21 août 2015
 1 -
Soon, Je vais ajouter une interface graphique pour générer et résoudre
S'inscrire maintenant

Vous 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.

Du même auteur (amezghal)