[Projet Sudoku] Retour à l'algo
Bonsoir tout le monde !!
Voici l'algo d'affichage en console d'une grille de sudoku générée aléatoirement :
Tout d'abord, les 9 carrés de ma grille de sudoku sont numérotés de 0 à 8 de gauche à droite (ce qui explique la formule du 2) au deuxième "-").
Voici l'algorithme auquel j'ai pensé :
1) je crée une grille de sudoku 9*9
les étapes qui suivent sont réalisées en boucle :
2) à chaque ligne, colonne et sous-tableaux est associé un tableau d'entiers de 1 à 9...
ainsi dès que je place un élément (disons 8) à la case (i,j), commun aux trois tableaux :
- l'élément ligne[i][indice de 8] est mis à -1...
- de même pour colonne[j][indice de 8] et carre[3*(i/3)+j/3][indice de 8]
3) je trie les trois tableaux ds l'ordre décroissant (afin que le nouveau -1 soit le dernier élément de chaque tableau) //étape non indispensable
4) enfin, j'affiche la grille à grands coups de printf
De cette manière, je suis sûr que la grille de sudoku est remplie conformément aux régles, puisque l'élément d'une même ligne/colonne/carre ne peut être placé deux fois... .
Seulement, j'ai vérifié expérimentalement que la grille de sudoku ainsi générée ne pouvait pas se remplir complètement, comme on me l'avait dit.
Du coup, j'en viens à me demander s'il ne faut pas boucler les étapes 2 à 4 TANT QUE la grille n'est pas correctement remplie. Cette solution est cependant EXTREMEMENT COUTEUSE en temps processeur, je me demande même si ça n'équivaut pas à une boucle infinie.
Vous pourrez trouver le fichier en question en pièce jointe (ne pas compiler, c'est juste pour la lecture)
Toutes les fonctions non définies le sont dans d'autres fichiers, qui ont été compilés et testés sans problèmes... .
Si vous avez des suggestions d'améliorations de cet algo (je veux rester malgré tout sur la même base), je suis preneur.
Merci d'avance.
P.S. : je l'avais déjà expliqué dans un autre post récent, mais le sujet de cet ancien post a été réglé...
c'est pourquoi je lance un nouveau sujet lié au même projet...
Répondre avec citation
Partager