Discussion :

[rota90]

bjr,
j'ai comme projet d'ecrire le code de résolution d'une grille sudoku,que dois je avoir comme acquis en c? et par où commencer?
merci d'avance

[Bousk]

Bonjour,

dans le cas de vérification d'une grille de sudoku, les seules choses qui me semblent utiles sont
- les règles du jeu..
- les tableaux (à tailles fixes - ça devrait suffire, sinon ajouter la dimension)
- écrire des for
- écrire des if
- écrire et appeler une fonction (pour simplifier le code)

Après, s'il te faut un programme qui soit capable de remplir une grille, les notions sont les mêmes. Seule leur utilisation va changer.

[Bktero]

J'ai eu en DS d'initiation à l'algorithmique de 1ère année, la validation d'une grille de sudoku. Ce n'est pas très compliqué et je ne vois rien à rajouter à ce qu'à dit Bousk.

En revanche, si ton programme doit remplir une grille initiée, tu as un plus gros travail d'algorithmique à faire (mais ça doit se trouver sur le net). Il te faut peut-être savoir faire une fonction récursive.

[Sve@r]

et par où commencer?

Salut

J'ai déjà programmé ça (en C++)
Mon algo qui fonctionne en 2 temps
1) boucle sur chaque case du jeu
- je regarde tous les chiffres qui peuvent aller sur la case
- s'il n'y a qu'un seul chiffre possible alors c'est bon
2) boucle sur chaque ensemble (chaque ligne, chaque colonne, chaque zone 3x3)
- je prends un chiffre de 1 à 9 et je regarde sur quelles cases de l'ensemble il peut aller
- s'il ne peut aller que sur une seule case de l'ensemble, alors c'est bon

Et tant que au-moins une case positionnée je recommence boucles 1 et 2

Il existe toutefois certaines grilles avancées où cet algo ne suffit pas. J'ai donc rajouté ensuite l'algo "brute force" qui fonctionne en récursif où je prends la première case de libre et je boucle sur tous les chiffres possibles de cette case. Je place donc le premier chiffre et je relance l'algo en récursif. S'il arrive à tout remplir alors c'est bon...
Donc une fois que l'algo 1+2 atteint ses limites (quand il n'arrive plus à rien placer) alors j'enchaine sur l'algo brute force...

J'ai aussi programmé le générateur de grilles
Je génère avec le brute force une grille complète.
Puis, pour chaque chiffre de la grille, je l'enlève et je regarde si on peut le retrouver avec l'algo 1+2.
Et je recommence tant que je peux enlever des chiffres...

[Bktero]

Javais pas mal réfléchi il y a quelques mois pour faire un jeu de sudoku pour m'initier à la programmation sous Android (finalement, j'ai fait un démineur en Qt sur PC, rien à voir). Je m'étais alors demandé : comment faire si (pour reprendre les termes du post précédent) les algos 1 et 2 ne suffisent pas. J'ai la confirmation qu'il faut bourriner

Ma question : dans une grille standard (comme je trouve tous les jours dans 20 Minutes ou Metro), est ce que tu as souvent besoin de bourriner ? (à noter que je sais à peine jouer à ce truc, je connais juste les règles...)

[Sve@r]

Javais pas mal réfléchi il y a quelques mois pour faire un jeu de sudoku pour m'initier à la programmation sous Android (finalement, j'ai fait un démineur en Qt sur PC, rien à voir). Je m'étais alors demandé : comment faire si (pour reprendre les termes du post précédent) les algos 1 et 2 ne suffisent pas. J'ai la confirmation qu'il faut bourriner

Ma question : dans une grille standard (comme je trouve tous les jours dans 20 Minutes ou Metro), est ce que tu as souvent besoin de bourriner ? (à noter que je sais à peine jouer à ce truc, je connais juste les règles...)

Non. Les grilles standard se résolvent par la méthode standard.
Le brute force ne se justifie que dans les grilles des petits bouquins spécifiques et uniquement pour les niveaux hard.

Ca m'intéresse ton démineur en Qt (pas pour le démineur mais pour me perfectionner en Qt). De mon coté je peux te filer un sudoku en Qt (pas fait par moi mais par un gars qui m'a abandonné le truc) et un "compte est bon" en PyQt...

[Bktero]

Ca m'intéresse ton démineur en Qt (pas pour le démineur mais pour me perfectionner en Qt). De mon coté je peux te filer un sudoku en Qt (pas fait par moi mais par un gars qui m'a abandonné le truc) et un "compte est bon" en PyQt...

Salut !

Si tu es intéressé par mon démineur en Qt, tu pourras trouver les sources sur ma page GitHub : https://github.com/bktero/ . J'ai aussi fait une application (ma 1ère en Qt) où j'interagis avec une base de données SQLite pour gérer ma collection de disques. Les sources sont aussi sur mon GitHub.

Je ne suis pas une brute en Qt ni en C++, tu ne trouveras peut-être pas le code le plus élégant et efficace de la terre ^^ En tout cas, je suis preneur de toute remarque et idée. Si tu es membre de GitHub, tu peux directement commenter sur le site.

Bonne journée.
Pierre.


PS : je veux bien le sudoku en Qt STP ! Pour le compte est bon, je ne connais ni le principe du jeu ni Python, mais tu as un lien avec les sources, je jetterai aussi un oeil.

[anacharsis]

si tu veux t'instruire : http://cgi.cse.unsw.edu.au/~xche635/dlx_sodoku/.
c'est un programme un peu gourmand en espace mémoire, mais assez rapide en résolution.

A+

[anacharsis]

salut !
pour un générateur de grille, il faut en plus vérifier qu'il n'y a qu'une seule solution ...

A+

[Sve@r]

salut !
pour un générateur de grille, il faut en plus vérifier qu'il n'y a qu'une seule solution ...

C'est implicite avec mon algo.
Une fois la grille remplie, j'enlève 1 chiffre. Fatalement mon algo 1+2 arrive à le replacer.
J'enlève ensuite un second chiffre. Si mon algo 1+2 arrive à le replacer ça veut dire que le premier chiffre enlevé ne peut pas aller à sa place.
J'enlève un 3° chiffre. Si l'algo 1+2 arrive à le replacer ça veut dire qu'il est le seul possible et qu'aucun des deux autres n'y allait. Et etc etc...