Le sudoku
Fermé
yanilunga
Messages postés
1
Date d'inscription
lundi 9 février 2009
Statut
Membre
Dernière intervention
9 février 2009
-
9 févr. 2009 à 20:37
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 - 10 févr. 2009 à 01:26
mamiemando Messages postés 33079 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 23 avril 2024 - 10 févr. 2009 à 01:26
A voir également:
- Le sudoku
- Télécharger sudoku gratuit pour mobile - Télécharger - Puzzle & Réflexion
- Sudoku gratuit - Télécharger - Jeux vidéo
- Sudoku pc - Télécharger - Outils professionnels
- Sudoku ✓ - Forum Jeux vidéo
- Sudoku en c - Forum Programmation
1 réponse
mamiemando
Messages postés
33079
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
23 avril 2024
7 749
10 févr. 2009 à 01:26
10 févr. 2009 à 01:26
Ce n'est pas très compliqué si tu vois le sudoku comme un problème CSP (constraint satisfaction program). Un CSP se compose :
- d'un ensemble X de variable (les cases à remplir)
- d'un ensemble D de domaine (les valeurs que peuvent prendre chaque variable, ici {1...9})
- d'un ensemble C de contraintes (qui décrit l'interdiction de mettre plusieurs fois le même chiffre sur une ligne, dans un carré, ou dans une colonne).
Note que ce formalisme est particulièrement adapté au sudoku car on peut tout à fait le généraliser à des sudoku n^2 * n^2 au lieu de forcément prendre n = 3 (soit une grille de 9 x 9).
1) Histoire d'être sûr que tout va bien, tu peux commencer par vérifier la cohérence de la grille (typiquement pour une ligne donnée, le même chiffre n'apparaît qu'au plus une fois, idem avec les colonnes et les carrés).
2) Pour résoudre ton problème efficacement, tu dois au préalable réduire le domaine de chacune de tes variables. Par exemple si tu as un "trou" sur une ligne comportant déjà un 3, un 5 et un 8, tu sais que le domaine de cette variable est inclu dans [1,2,4,6,7,9} (même raisonnement avec les carrés et les colonnes). Cette phase de réduction doit être répétée tant que tu arrives à réduire un ou plusieurs domaines.
Si au cours de cette phase tu as une variable dont le domaine :
- est de taille 1 : alors tu sais quelle valeur attribuer à cette case
- est de taille 0 : le sudoku n'a pas de solution
3) Arrivé à cette étape tu devrais déjà avoir bouché quelques cases, voir résolu le sudoku si la grille était facile. S'il reste des cases vacantes, cela signifie qu'il va falloir faire une hypothèse pour continuer à remplir la grille (noeud de branchement). Il est donc important de mémoriser cette configuration pour pouvoir y retourner, car on va a présent faire une hypothèse pour tenter d'avancer (par exemple j'hésite entre mettre un 3 et un 5 dans telle case, je vais essayer de voir ce qui se passe en y mettant par exemple un 3).
Une fois l'hypothèse faite, on relance l'étape (2) (réduction de domaine).
a- si un domaine devient vide, cette hypothèse était mauvaise et donc il est inutile de continuer à l'explorer, donc on revient au dernier noeud et on essaye une autre hypothèse (je mets un 5 au lieu du 3)
b- si on parvient à résoudre la grille on s'arrête
c- dernier cas possible, on arrive à un nouveau noeud de branchement (et on va donc faire une seconde hypothèse). Inévitablement au fil des hypothèses on finira par se trouver dans le cas (a) ou (b).
Au final le programme aura donc probablement fait plusieurs noeuds de branchement. Ces noeuds forme un arbre qui permet de retracer les différentes hypothèses que le programme de résolution a évalué. Si l'on a exploré tout l'arbre sans trouver de solution (c'est-à-dire testé toutes les hypothèses) alors la grille n'a pas de solution.
Bonne chance
- d'un ensemble X de variable (les cases à remplir)
- d'un ensemble D de domaine (les valeurs que peuvent prendre chaque variable, ici {1...9})
- d'un ensemble C de contraintes (qui décrit l'interdiction de mettre plusieurs fois le même chiffre sur une ligne, dans un carré, ou dans une colonne).
Note que ce formalisme est particulièrement adapté au sudoku car on peut tout à fait le généraliser à des sudoku n^2 * n^2 au lieu de forcément prendre n = 3 (soit une grille de 9 x 9).
1) Histoire d'être sûr que tout va bien, tu peux commencer par vérifier la cohérence de la grille (typiquement pour une ligne donnée, le même chiffre n'apparaît qu'au plus une fois, idem avec les colonnes et les carrés).
2) Pour résoudre ton problème efficacement, tu dois au préalable réduire le domaine de chacune de tes variables. Par exemple si tu as un "trou" sur une ligne comportant déjà un 3, un 5 et un 8, tu sais que le domaine de cette variable est inclu dans [1,2,4,6,7,9} (même raisonnement avec les carrés et les colonnes). Cette phase de réduction doit être répétée tant que tu arrives à réduire un ou plusieurs domaines.
Si au cours de cette phase tu as une variable dont le domaine :
- est de taille 1 : alors tu sais quelle valeur attribuer à cette case
- est de taille 0 : le sudoku n'a pas de solution
3) Arrivé à cette étape tu devrais déjà avoir bouché quelques cases, voir résolu le sudoku si la grille était facile. S'il reste des cases vacantes, cela signifie qu'il va falloir faire une hypothèse pour continuer à remplir la grille (noeud de branchement). Il est donc important de mémoriser cette configuration pour pouvoir y retourner, car on va a présent faire une hypothèse pour tenter d'avancer (par exemple j'hésite entre mettre un 3 et un 5 dans telle case, je vais essayer de voir ce qui se passe en y mettant par exemple un 3).
Une fois l'hypothèse faite, on relance l'étape (2) (réduction de domaine).
a- si un domaine devient vide, cette hypothèse était mauvaise et donc il est inutile de continuer à l'explorer, donc on revient au dernier noeud et on essaye une autre hypothèse (je mets un 5 au lieu du 3)
b- si on parvient à résoudre la grille on s'arrête
c- dernier cas possible, on arrive à un nouveau noeud de branchement (et on va donc faire une seconde hypothèse). Inévitablement au fil des hypothèses on finira par se trouver dans le cas (a) ou (b).
Au final le programme aura donc probablement fait plusieurs noeuds de branchement. Ces noeuds forme un arbre qui permet de retracer les différentes hypothèses que le programme de résolution a évalué. Si l'on a exploré tout l'arbre sans trouver de solution (c'est-à-dire testé toutes les hypothèses) alors la grille n'a pas de solution.
Bonne chance
