Sudoku

Discussions générales concernant les mathématiques.
[ce forum est modéré par les modérateurs globaux du site]
Règles du forum
Merci d'éviter le style SMS dans vos messages et de penser à utiliser la fonction Recherche avant de poster un message. Pour joindre des fichiers à vos messages, consulter ce sujet.
> Penser à utiliser le mode LaTeX (voir ici) afin de rendre vos formules plus lisibles.
> Pour obtenir de l'aide sur un exercice ou un problème, consulter cette section. (ce forum est destiné aux discussions plutôt théoriques)

Sudoku

Messagepar jeje2k2 » Mardi 09 Août 2005, 13:14

Bonjour à tous,

Je ne sais pas si vous connaissez le casse tête appelé Sudoku! Il nous vient du japon et s'apparente au carré magique. Bref une recherche sur google vous le fera découvrir très facilement. Je m'intéresse plutot à l'aspect mathématique qu'il y a derrière! J'ai donc plusieurs questions:


  • Comment dénombrer le nombre de grilles de sudoku que l'on peut générer?
  • Existe-t-il une solution unique à chaque grille de sudoku?
  • Pourquoi est-ce qu'il y a différents niveaux de sudoku?
  • Comment programmer efficacement un algorithme permettant de résoudre nimporte quelle grille?
  • Et bien sur, comment construire une grille de sudoku!?


Voila, toutes ces questions attendent des réponses, et j'espère que quelques personnes s'y intéresseront!

Merci
jeje2k2
Utilisateur
 
Messages: 1
Inscription: Mardi 09 Août 2005, 13:09

Publicité

Re: Sudoku

Messagepar cerise » Mardi 09 Août 2005, 18:32

jeje2k2 a écrit:Existe-t-il une solution unique à chaque grille de sudoku?

Déjà, ça dépend du nombre de chiffres que tu inscris dedans au début... Si tu as une grille vide, il y a évidemment autant de solutions que de grilles possibles ;-)
Il fallait être Newton pour apercevoir que la Lune tombe quand tout le monde voit bien qu'elle ne tombe pas.
Paul Valéry
cerise
Méga-utilisateur
 
Messages: 448
Inscription: Mercredi 08 Juin 2005, 17:03
Statut actuel: Actif et salarié

Re: Sudoku

Messagepar minnolina » Dimanche 28 Août 2005, 00:09

jeje2k2 a écrit:Comment dénombrer le nombre de grilles de sudoku que l'on peut générer?


J'ai seulement une reponse a ca:

http://www.inf.tu-dresden.de/~bf3/sudoku/sudoku.pdf
Gloria
minnolina
Déca-utilisateur
 
Messages: 21
Inscription: Mardi 31 Mai 2005, 08:26
Localisation: Toulon
Statut actuel: Actif et salarié | Maître de conférence

Algorithme

Messagepar TaeKrage » Jeudi 12 Janvier 2006, 12:05

J'ai programmé un solveur de la façon suivante :
L'utilisateur rentre une grille,

Le programme va déterminer l'ordre dans lequel il va résoudre les cases, par exemple, s'il manque 2 chiffres sur la première ligne, et que ce nombre d'inconnues s'avère être le minimum, le programme définit cette ligne prioritère et place le nombre 1 dans un tableau réservé pour l'ordre de résolution. 1 correspond à la 1ère ligne, 2 à la 2ème ... 10 à la première colonne, 11 à la 2ème, 19 au premier carré, 20 au 2ème, etc. ... Le programme simule le remplissage de cette ligne, et on recommence jusqu'à ce que le tableau soit rempli. A la fin, on a donc un tableau Tab_ordre = [1, 10, 6, ... ] par exemple.

Ensuite il s'agit de tester les combinaisons,
On commence par la priorité 1, soit ici la 1ère ligne. On teste toutes les combinaisons qui pourraient convenir, puis on passe au 2ème ordre, jusqu'au dernier ...

Note : Il ne faut pas enregistrer les tableaux pour les réutiliser plus tard car la mémoire risque d'être insuffisante, il faut donc procéder par récurrence. C'est à dire que si une solution convient pour l'odre 1, on passe à l'ordre 2 directement ...

J'ai testé plusieurs niveaux sur Internet, mon programme met 4 secondes pour des niveaux faciles et moyens mais 30 secondes pour un difficile ...
TaeKrage
Déca-utilisateur
 
Messages: 20
Inscription: Mardi 27 Décembre 2005, 20:48

Messagepar nirosis » Vendredi 13 Janvier 2006, 11:41

Intéressant tout ça ! Même si j'ai jamais joué au sudoku encore, j'en entend de plus en plus parler... Tout le monde y joue dans le train j'ai l'impression :D
Tu as programmé en quel langage ?
nirosis
Administrateur
 
Messages: 1806
Inscription: Samedi 28 Mai 2005, 13:48
Localisation: Orsay, France
Statut actuel: Actif et salarié | Maître de conférence

Messagepar w3fh5 » Jeudi 19 Janvier 2006, 04:27

Bonjour, je suis étudiant a la fac de science de montpellier. Je dois faire un projet pour étudier comment réussir a ne générer que des grilles a une unique solution.

Pour la question 1, il y a $6.671 \times 10^{21}$ d'apres la publication http://web.inf.tu-dresden.de/~bf3/sudoku/sudoku.pdf

Pour la question 2, oui il ne faut qu'une unique solution. Un sudoku avec une grille vide n'est donc pas un vrai sudoku

Pour la question 3, un sudoku facile se résout uniquement par déduction, un plus dur par hypothèse, supposition incluant plus ou moins de variables. Pour plus d'information voir sudoku sur wikipedia par exemple.

Pour la question 4, il suffit d'utiliser un systeme de résolution de contraintes performant (voir l'api choco par exemple). En placant les règles chaque nombre de chaque ligne/colonne et zone doit etre différent, on peut résoudre une grille en une vingtaine de ligne.

Mon problème est qu'est ce qui permet de générer une grille a solution unique.
Tous les programmes que j'ai essayé pour l'instant génèrent des grilles et les testent ensuite pour vérifer qu'il y a bien une unique solution avant de les présenter ou d'en regénérer une autre.

Voila si vous avez des indications la dessus... :)

[edit : sotwafits] : LaTeX
w3fh5
Utilisateur
 
Messages: 1
Inscription: Jeudi 19 Janvier 2006, 04:19
Localisation: montpellier


Retourner vers Tribune des mathématiques

Qui est en ligne

Utilisateurs parcourant ce forum: Aucun utilisateur enregistré et 4 invités