[IA] Creer un sudoku (algorithme pour le moment)

Bonjour tout le monde.

J'ai donc un projet a faire et on a refléchit avec des amis mais on arrive vraiment a rien.

Le but est de creer un sodoku (pas tres sympa pour des premieres année). Pour le moment on ne connait a peu pret rien en gtk( afficher les fenetre etc...) on s'est donc concentré sur l'algorithme.

On a pensé faire cela:
Creer un tableau a deux dimension 9*9. Mettre des chiffre compris entre 0 et 9 dans chaque cellule et vérifier ensuite si c'est bien un sudoku puis effacer certain nombre et voila.

Mais le probleme c'est que en generant des nombre aleatoirement il faudrai peut etre qq heures au pc avant de trouver un sudoku. Donc on s'est dit que c'est mort pour cette technique.

Donc j'aimerais collecter vos idées generer un sudoku.

Merci infiniement

cherche sur le net des algos il doit bien yen avoir sur le net pour générer des sudokus :)


perso moi je sais pas sorry mais c'est sur qu'avec tes aléatoires :)

Nan, ne cherche pas sur le net, CHERCHE sut developpez, y a eu un topic avec 175532325 réponses....

... on cherche d'abord, on pose une question ensuite!!!

Je suis déolé. J'avais cherché mais pas sur le bon forum.

Merci je vais lire tous les sujets et reviendrai apres.

Citation:

---

Envoyé par Nemerle

Nan, ne cherche pas sur le net, CHERCHE sut developpez, y a eu un topic avec 175532325 réponses....

... on cherche d'abord, on pose une question ensuite!!!

---

Si tu pouvais nous donner le lien de ce topic ce serai sympa parce que j'ai cherché partout sur Developpez.net et je ne trouve aucun topic qui résout ce problème sur lequel je bute également :(

[HS]
A mon avis, avant de résoudre le sudoku, il faudra apprendre à savoir utiliser la fonction recherche :aie:
[/HS]

http://www.developpez.net/forums/showthread.php?t=54373

Je ne cherche pas un solutionneur de grille de sudoku mais un algorithme de génération d'une grille de sudoku.

En fait, générer une grille, c'est résoudre un sudoku issu d'une grille vide.

Finalement, j'ai utilisé cette méthode pour générer une grille de sudoku aléatoirement :
http://sudoku.nerdzblog.com/index.php?idb=104

Voici le programme java que j'ai réalisé, un jeu de Sudoku :
http://dl.toofiles.com/kp8k4c/documents/sudoku.zip

berk les permutations !

le backtracking avec la simple heuristique de choisir la case qui a le moins de possibles fonctionne bien

sinon le plus efficace je pense est d'utiliser un SAT solver pour trouver les solutions d'une grille

il suffit de traduire en booléen:
au moins un chiffre par case, au max un chiffre par case, chaque chiffre apparait au moins une fois par colonne ligne bloc, au max une fois par colonne ligne bloc

on a 9 variables booléennes par case ce qui fait 9*81 variables booléennes en tout

attention: le SAT solver est par excellence l'outil qui ne permettra pas facilement de générer aléatoirement des grilles, pour ça il vaut mieux utiliser en plus le backtracking :)

Renaud