Création de grilles de sudoku fini

Version imprimable

Je m'explique. Pour créer des grilles jouables de différents niveaux j'ai décidé de partir d'une grille fini, de retirer une case aléatoirement et d'appeler un solveur.

Jusque là ça me parait jouable, mais par contre j'arrive pas à créer une grille dans un temps raisonnable. Mon algo ( implémenté en C) met 5-10 pour me faire un grille, c'est beaucoup trop long.

Alors voici mon algo
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 faireLigne(i) { int compt; for(comp=0;compt<9;compt++) faireCaseAléa(i,compt); si erreurSurLigne compt--; } faireGrille() { int compt; for (compt=0;compt<9;compt++) { faireLigne(compt); si (erreurSurColonne OU erreurSurBloc) compt--; } }
Donc bon le backtrack c'est bien mais c'est pas très optimisé. J'ai pas trop d'idée sur comment faire autrement.

J'ai pensé à une méthode de permutation de grille, mais il faut une grille de base et ça me plais pas trop. C'est pas trop propre je trouve, pis j'ai pas envie d'oublier des grilles.

13/03/2008, 10h28
ToTo13

Bonjour,

ton idée pour générer des grille jouable est la bonne, en tout cas la seule utilisée :). On part d'une solution et on retire aléatoirement une valeur, puis on demande au solveur de résoudre.

Quand tu dis 5-10, tu parles en minutes ? en heures ? en jours ? en années :D ?

Je sais qu'il existe des algorithmes pour remplir automatiquement une grille de sudoku juste. Fais une recherche sur :google: et sur le forum, il me semble que l'on en a déjà parlé.
13/03/2008, 20h03
mooglwy

Euh non non seconde seconde. Après j'ai cherché longtemps des algo pour généré la grille mais j'ai pas trouvé encore les bon mots clefs la je tombe que sur des algos pour le solveur.

Après ici j'ai trouvé un gros topic assez vieux mais ça parle pas de création de grille.
Si t'as un lien ou un mot clef je suis preneur.
14/03/2008, 09h53
ToTo13

Bonjour,

en lisant rapidement la page de Wikipédia, on apprend que l'ancètre du Sudoku est le "le carré latin magique" 9x9, donc je pense qu'il faut chercher des algos qui génèrent ce genre de grille.
14/03/2008, 12h02
pseudocode

Citation:

Envoyé par ToTo13

Bonjour,

en lisant rapidement la page de Wikipédia, on apprend que l'ancètre du Sudoku est le "le carré latin magique" 9x9, donc je pense qu'il faut chercher des algos qui génèrent ce genre de grille.

Sur le meme wikipedia, on apprend qu'on peut générer des grilles par permutations. (pas toutes les grilles possibles, mais un bon paquet quand meme)
14/03/2008, 19h28
mooglwy

Citation:

Envoyé par mooglwy

Pour créer des grilles jouables de
J'ai pensé à une méthode de permutation de grille, mais il faut une grille de base et ça me plais pas trop. C'est pas trop propre je trouve, pis j'ai pas envie d'oublier des grilles.

Hé hé déjà proposé. :) mais comme je l'ai déjà dit je trouve pas ça super propre. Je le prendrais mais pâs avec joie. :cry:

J'avais pas pensé à chercher du coté des carrés latin. Y de quoi chercher mais j'ai peur de trouver que des trucs sur la résolution.:roll:
16/03/2008, 14h27
acx01b

salut pour faire une grille voila comment j'ai fait (ça marche bien):

un backtrack simple sur une grille vide permet de la remplir
maintenant au lieu que le backtrack essaye successivement 1,2,3...9 pour chaque case tu essayes les 9 chiffres dans un ordre aléatoire

--> tu obtiens une grille complétement différente à chaque fois, et tu peux obtenir toutes les grilles

mais c'est très lent !

il faut rajouter une heuristique: tu ne remplis par la grille ligne par ligne, à chaque appel de la fontion backtrack tu choisis comme case à remplir celle qui a le moins de possibilité

note: s'il y a 0 possibilité dans une case alors tu es dans un cul de sac il faut backtracker
16/03/2008, 14h55
mooglwy

C'est une proposition intéressante, mais le simple fait de choisir ne case ne prend-t-il pas, pas mal de temps ?
Si tu ne construis plus ta grille ligne pas ligne ça veut dire que tu choisis aléatoirement ta case parmi celles ayant le moins de possibilité sur toute la grille.
ça me parait encore flou, tu pourrais détailler un peu. :)
17/03/2008, 18h52
acx01b

en C tu arrives à faire quelque chose de bien performant, en utilisant une liste triée par nombre de possible des cases vides

tu modifies une petite partie de cette liste quand tu mets ou que tu enlèves un chiffre dans une case

tu gardes la liste triée avec un tri à bulle par exemple ou tu peux faire encore plus optimisé

pas besoin de choisir aléatoirement la case qui a le moins de possible, suffit de prendre la première !
car tu fais déja de l'aléatoire sur l'ordre des chiffres que tu essayes dedans
17/03/2008, 18h55
acx01b

après si tu veux aller super loin, le meilleur solver que j'ai vu jusqu'à maintenant utilie un SAT solver: mais attention pas possible de générer des grilles aléatoires comme ça

1) tu crées une grille aléatoire avec un backtrack
2) tu enlèves des cases aléatoirement, et à chaque fois tu testes s'il y a qu'une seule solution en utilisant un SAT solver (voir "coder un sudoku en langage booléen")
17/03/2008, 19h59
mooglwy

Coté liste trié faut que je vois ça mais si c'est bien optimisée ça peut être pratique. Merci pour l'idée.

Après le SAT solver je me suis un peu renseigné dessus mais je comprends pas grand chose pour le moment va falloir que je m'y penche plus sérieusement.
Disons que coté solveur c'est pas trop mon problème pour le moment vu que je suis en cours de rédaction de mes algos.

Bon ben merci pour toutes c'est idée et voix vers les qu'elle m'orienter. Si tu as d'autre précisions n'hésite pas.

content de trouver quelqu'un que ça intéresse les histoires de sat solver :)

le sudoku en booléen: 81 cases, 9 possibilité par case
on a 729 variables booléennes
la variable booléenne VAR(i,j,k) indique si le chiffre k est dans la case i,j ou pas
par exemple la variable VAR(1,1,8) vraie signifie que dans la case 1,1 il y a le chiffre 8

- pour toute case i,j, VAR(i,j,1) ou VAR(i,j,2) ou ... VAR(i,j,9)
un chiffre au moins dans chaque case
- pour toute case i,j, pour tout k,l k différent de l, non(VAR(i,j,k)) ou non(VAR(i,j,l))
il ne peut pas y avoir 2 chiffres différents dans une même case
- pour toute ligne i, tout chiffre k, VAR(i,1,k) ou VAR(i,2,k) ... ou VAR(i,9,k)
chaque chiffre apparait dans chaque ligne
- pour toute ligne i, tout chiffre k, pour tout l,m, l différent de m, non(VAR(i,l,k)) ou non(VAR(i,m,l))
pas 2 fois le même chiffre sur une même ligne
... etc pareil pour les colonnes et les régions

finalement on a 3 règles symétriques (c'est un carré latin avec ces 3 règles):
Code:

1 2 3 4 5 6 7 pour tout i,j on a: un et un seul vrai parmis VAR(i,j,1), VAR(i,j,2) ... VAR(i,j,9) --> un chiffre par case un et un seul vrai parmis VAR(i,1,j), VAR(i,2,j) ... VAR(i,9,j) --> tous les chiffres dans une ligne un et un seul vrai parmis VAR(1,i,j), VAR(2,i,j) ... VAR(9,i,j) --> tous les chiffres dans une colonne
reste à mettre les règles sur les régions selon le même principe

si tu n'as rien compris c'est normal, relis plusieurs fois c'est pas compliqué
Renaud

18/03/2008, 09h51
mooglwy

En fait j'ai fait ma structure comme ça, j'ai juste rajouté un bit ( comme bit faible) me disant si la case a été résolue ou pas. Et je peut tous stocker dans un int, genre le 3 est dans la case si la 4ème(3+0) bit est vrai.
Je trouvais ça beaucoup plus pratique pour gérer l'ensemble des possibles d'une case.
Après ce qui me gênait c'est je lis ma variable, je vois qu'elle est résolue, et bah boucle for pour trouver la valeur. Y a surement plus simple. Et surtout plus rapide.
19/03/2008, 18h41
Veovis

Pour la réalisation des grilles unique de sudolu cherche sur google : "sudoku ILP modeling". Tu tomberas sur des liens intéressants notemment :

http://www.aps.anl.gov/News/Meetings...0VG-sudoku.ppt
19/03/2008, 22h29
mooglwy

faillais vraiment connaître pour le trouver le mot clef. Mais merci bien pour le renseignement. :)