premierement si le titre est choquant, il n´y a qu´a le virer, je trouverais un autre nom.

J´ai fais un petit prog pour jouer au sudoku (C/SDL), dans un premier temps le jeu ne faisait que permetre de jouer en detectant les erreurs mais sans avoir de correction.
Puis j´ai ajouter un correcteur idiot (force brute).

Puis, me rappelant d´une remarque sur un topic de JYY, j´ai addapté le principe du sudoku a une grille de (n²)*(n²) avec n un entier naturel. Le probleme c´est que la complexité de la correction explose, rien que pour les grilles de 16*16, le prog peine a mort pour trouver une soluce.

Il y a un mode editeur qui permet de corriger les grilles trouvée de ci de là, possibilité de jouer sur une grille construite au pif, possibilité de choisir la difficulté.
le fichier zip ci dessous contient le sudoku normal et le choduku (16*16).
pour de plus amples infos sur le moyen d´utiliser le programme, lire le fichier readme.

le jeu fonctionne sous windows et linux (pour linux, il suffit de me demander les sources)
http://www.info.univ-angers.fr/pub/letouzey/perso/jeux/dl/sudoku.zip

j´arrive pas a telecharger ca met forbidden acces

argh, a tout les coup j´ai oublier de faire un petit chmod 777.

2 minutes...

J´l´aime bien moi ton titre (°° )

bon eh bein je ne comprend pas, sur les 3 fichiers que j´ai uploader ce soir, un seul fonctionne....
pourquoi ? sans doute la magie de l´informatique.
bon je REupload ça et je reviens quand ça marche

désolé

bon et bien apparament ça marche ?? ??????????

nickel ton jeu, bien aussi la correction de grille

juste une precision: Il se peut que le prog bug (tourne a l´infini) si tu tente de coriger une grille sans solution.
Et si en plus les commentaires sont activé, le fichier stdout.txt peut voir sa taille exploser. (je me suis retrouvé un coup avec un fichier de plus de 1.5Go! en le laissant tourner 10-15 minutes)

en gros si il n´y a pas de solution au bout de 30 secondes -> arreter tout

Cà marche très bien, et la correction est très rapide même pour le choduku.

Par contre l´éditeur je vais éviter de faire mumuse avec, je suppose qu´il faut déjà être un joueur confirmé de sudoku (et c´est pas mon cas du tout) avant de faire ses grilles persos et qu´il y a des sortes de règles à suivre pour celà. J´ai juste essayé une fois pour voir, cà a planté à la correction

très bon petit programme... t´aurais pas envie de nous en donner la source ?? ?

pour l´editeur:
au debut c´etait parce qu´il n´y avait pas de generateur de grille et donc pour jouer avec une "vraie" grille il fallait qu´elle existe.
Sinon deuxiemme utilité c´est de corriger les grilles trouvée a droite ou a gauche.
exemple: ton pere s´arrache les cheuveux depuis 3 heures sur la grille du ouest france; toi tu arrive et pouf 0.1 seconde plus tard tu deballe la réponse a ton pere niark niark.

pour les sources:
pas de probleme; elles seront disponibles dans le prochain fichier que je mettrai en ligne (sources + makefile pour linux).
je vous tien au courant (peut-etre ce soir)

voila c´est fait. meme lien.
en +:
- les sources
- un makefile pour linux
$ make
-> crée l´executable
$ make pack
-> fabrique un dossier independant qui contient tout ce qu´il faut pour le copier/coller n´importe où.
$ make clean
-> efface tout ce qui a été construit (pack et executable)

pour passer de sudoku a choduku:
ouvrir outils/Agck.h
modifier la ligne du haut

1. define TAILLE 3

en

1. define TAILLE 4

voila

c´est vraiment bien j´ai un pote qui va kiffer l´option Choduku

attention pour le choduku. la fonction de correction est recursive et dans le cas du choduku la recursivité va jusqua 265 niveau de profondeur (en gros ça prend enormement de memoire) meme si j´ai essayer de limiter les informations inutiles... enfin maintenant tout le monde a des pc avec 15Go de memoire vive

je me permet de reuploader ce vieu topic car aujourd´hui j´ai reçut mon affectation pour mon projet de fin d´année (licence info) et j´ai un mois pour répondre au sujet suivant:
"concevoir une interface graphique d´aide a la résolution d´une grille de sudoku"
(ha ha ha je me marre)
donc maintenant que j´ai deja fais mon projet j´aimerais avoir des idées d´ammeliorations:
- des menus
- plus de choix
- meilleur gestion des grilles pré-construites
- ...

et aussi j´aimerai savoir si il existe un algo plus efficace pour la correction que la force brute.
(Il me semble avoir lu sur le topic de Fvirtman que non.)

si bien sûr il y en a.

Le plus courant est d´utiliser un certain nombre d´heuristiques pour trouver des contraintes sur ce que tu doit faire.

En gros, si dans une ligne ou colonne (ou carré) il y a tout les chiffres sauf 1 dans la case libre tu mets celui là.

Mais l´astuce consiste ensuite à croiser les info sur les lignes et les colonne pour avoir le plus de contrainte possible.

An mettant bout à bout toutes les contrainte, tu peut résoudre même les grilles "impossibles" des journaux avec une profondeur de récursion de 2 ou 3 seulement (c´est le nombre d´hypothèses que tu doit faire).

Si tu connais un peu, j´ai un programme en Caml qui fait ça :
http://wall.sectionpc.info/Caml/sudoku.ml
(les grille 16*16 sont résolu en moins d´une seconde).

Par contre il y a une très grosse amélioration possible (pa dans mon programme), pour la gestion de la récursion qui est d´utiliser la structure "dancing links" très efficace dans ce cas-ci.
Plus d´info là :
http://en.wikipedia.org/wiki/Dancing_Links ou le papier de D. Knuth (qui a inventé l´algo en question) :
http://xxx.lanl.gov/PS_ca_cache/cs/pdf/0011/0011047.pdf

Pour information je connais un programme de 15 lignes qui résoud les grille de sudoku. Qui fait mieux ? (écrit en prolog, par mon prof de physique, malheureusement je n´ais pas le code source)

nikel tout ca moi qui adore le sudoku ;) bien joué pour ton programe ;)

merci bien dnob.
pour le caml je me debrouillait bien quand on en faisait a la fac mais je pense avoir un peu perdu.
Mais bon un algo est un algo. il suffit de comprendre la récurence. (surtout en Caml)
Je vais aussi prendre un peu de temps pour lire (et surtout comprendre) la page wiki.

encore merci.

voila le sujet complet :
"
Le projet consiste à définir une interface permettant à l´utilisateur de saisir une grille initiale de Sudoku. Le logiciel doit générer une représentation de la grille sous forme de programme logique étendu (le format vous sera précisé) et lancer la résolution du problème grâce à l´exécution d´un démonstrateur qui vous sera fourni. La sortie du démonstrateur sera analysée pour afficher la ou les grilles solutions.

Langage de développement: Java ou C++
"

"le format vous sera precisé"
"un démonstrateur qui vous sera fourni"

en gros j´ai plus qu´a recoller les morceaux...