begin process at 2012 05 27 20:28:23
  Trouver un code source :
 
dans
 
[ Dernières recherches ]
Accueil > 

Code

 > 

Jeux

 > SUDOKU RESOLVER (BRUTEFORECE, RÉCURSION)

SUDOKU RESOLVER (BRUTEFORECE, RÉCURSION)


 Information sur la source

Note :
Aucune note
Catégorie :Jeux Classé sous :sudoku, resursion, solution sudoku Niveau :Débutant Date de création :10/10/2011 Vu :1 542
Auteur : amezghal

Ecrire un message privé
Commentaire sur cette source (1)
Ajouter un commentaire et/ou une note

 Description

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

  • <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>
<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>



 Sources de la même categorie

Source avec Zip Source avec une capture AVVDA : A VERY VERY DARK AFFAIRES DEMO par Cyreb
Source avec Zip Source avec une capture 3D AVEC WEBGL + MESH par Hakumbaya
Source avec Zip MACHINE À SOUS par loicseg
Source avec Zip DOODLE JUMP EN JAVASCRIPT par Toshy62
Source avec Zip DICOFOU DICTIONNAIRE FANTAISISTE EN JAVASCRIPT par lecurieux41
Toutes les sources de la catégorie Jeux

 Sources en rapport avec celle ci

Source avec Zip GÉNÉRATEUR DE GRILLES DE SUDOKU par kiadimoundi
Source avec Zip CRÉATION DE SUDOKU EN JAVASCRIPT par pabbati
Source avec Zip Source avec une capture SUDOKY - SUDOKU EN JAVASCRIPT par amrounix
Source avec Zip SUDOKUS PAREIL MAIS EN MIEUX par Laffrey
Source avec Zip Source avec une capture SUDOKU SOLVER par debutant VB

Commentaires et avis

Commentaire de amezghal le 11/10/2011 00:17:30

Soon, Je vais ajouter une interface graphique pour générer et résoudre

 Ajouter un commentaire

Nos sponsors


Sondage...

Comparez les prix


Archos Tablette PC ARNOVA ARNOVA 10 4GB
Entre 200€ et 210€

Visiter le guide achat

CalendriCode

Mai 2012
LMMJVSD
 123456
78910111213
14151617181920
21222324252627
28293031   

Consulter la suite du CalendriCode

A découvrir
 
Développement réalisé par Nicolas SOREL (Nix) avec l'aide de : Cyril DURAND et Emmanuel (EBArtSoft), Merci à Vincent pour ses précieux conseils.
CodeS-SourceS.com© Toute reproduction même partielle est interdite sauf accord écrit du Webmaster
CodeS-SourceS.com© est une marque déposée tous droits réservés

Google Coop CodeS-SourceS Google Coop CodeS-SourceS
Temps d'éxécution de la page : 0,452 sec (3)

Nous contacter | Annoncer sur CodeS-SourceS | Mentions légales
Outils Convertisseur VB/C# Snippets et scripts Outils en ligne La ToolBox
Communauté Programmation Photographie Technologie Newsgroups Emploi Forum Blogs
Guide d'achat Téléphonie mobile Image et son Informatique Bureautique Jeux vidéo
Logiciels Internet & Réseau Développement Market Android Jeux & Loisirs Graphisme Multimédia Sécurité Pilotes
Loisirs Cartes virtuelles Vidéos droles Jeux en ligne Géoguide AndroLib (Android Market)