Sudoku

Soyez le premier à donner votre avis sur cette source.

Vue 19 580 fois - Téléchargée 3 651 fois

Description

Sudoku réalisé en C++ avec une interface Win 32.
Ce Sudoku comprend le chargement d'une grille à partir d'un .txt, le jeu d'un joueur humain, la résolution de la grille par l'IA, et la génération d'une grille.

Conclusion :


Ce fichier zip, comprend le jeu, ses programmes tests, le rapport et les sources compilées sous Dev C++.

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

jvpic
Messages postés
5
Date d'inscription
dimanche 4 juin 2006
Statut
Membre
Dernière intervention
3 août 2006
-
Bonjour,

Oui l'algorithme de Knuth est générique aux problèmes de couvertures complètes d'une surface avec des éléments et des contraintes. Problème des cartes politiques à 4 couleurs, mosaïques de pentaminos etc... Le Sudoku est un problème du mëme genre, il suffit en interface avec l'algo Dlx de préparer la matrice à résoudre avec les contraintes et les données.

Non Knuth n'est pas mort... Il doit avoir 60-65 ans...

Reste que le problème de l'évaluation reste entier. Je pense qu'il n'est pas indispensable de coder les simulations lorsque les méthodes logiques complètes n'arrivent pas à résoudre une grille dont on la déjà solutionpar Dlx, elle est nécessairement "diabolique" !

JP
cs_Kirua
Messages postés
3006
Date d'inscription
dimanche 14 avril 2002
Statut
Membre
Dernière intervention
31 décembre 2008
-
Il me semble aussi qu'une simulation des méthodes manuelles (y compris les spéculations avec une profondeur limitée, typiquement 1 ou 2 niveaux max) est la seule façon d'objectiver un niveau de difficulté.

Quant à l'unicité, l'algo implémenté ici permet tout à fait, avec modifs sans doute, j'ai pas regardé, de générer toutes les solutions. Il suffit de vérifier qu'il n'y en a qu'une in fine. Aucun problème.

L'algo de Knuth comme tu dis, c'est un algo générique, ou Knuth s'est vrmnt intéressé aux sudokus?? Il est pas mort d'ailleurs? :p
jvpic
Messages postés
5
Date d'inscription
dimanche 4 juin 2006
Statut
Membre
Dernière intervention
3 août 2006
-
Le code source applique en réalité la force brutale par récursivité. Cette méthode présente deux handicaps :
1) Elle est relativement longue par rapport à l'algorithme de Knuth (Dlx)
2) De plus on s'arrête à la première szolution : on a aucune garantie sur l'unicité de la solution et donc de la correction de la grille générée.

Une autre critique concerne cet algorithme, mais aussi celui de Dlx :

Nous n'avons aucun critère objectif de classification de difficulté de la grille générée, en effet le nombre de caractère n'est pas un critère robuste. Le temps de résolution n'en est pas un non plus.

Après avoir codé moi-même un jeu de Sudoku, par les deux algorithmes, je m'arrête sur le choix Dlx (rapidité et complétude) et pour la gébération, j'y rajoute un module de résolution "manuelle" (candidat unique, jumeaux, X-Xing, swordfish etc...) pour avoir une évaluation convenable (mais pas absolue).

J'aimerai avoir des opinions concernant ce vrai problème : EVALUATION DE LA DIFFICULTE d'une grille.

Merci

JP
cs_Urgo
Messages postés
780
Date d'inscription
lundi 16 décembre 2002
Statut
Membre
Dernière intervention
16 avril 2009
1 -
Chaque VRAI sudoku a une et une seule solution.
Celui qui en a plusieurs c'est à envoyer à la poubelle.
masternico
Messages postés
494
Date d'inscription
dimanche 5 octobre 2003
Statut
Membre
Dernière intervention
1 septembre 2011
-
Tout les sudoku ne sont pas forcément à solution unique?...

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.