Resolution de tous les problemes de sudoku

Soyez le premier à donner votre avis sur cette source.

Snippet vu 23 371 fois - Téléchargée 20 fois

Contenu du snippet

Ce code minimal résout les sudoku !

Il comprend 4 routines et un main et est indépendant de tout autre source.
main : lit les problèmes et appelle la routine de résolution
tree : exécute la recherche de la solution par parcours de l'arbre des cas possibles (7 lignes)
possible : teste la validité d'un nombre sur une case
prnt : print une grille
readpb : lit le fichier contenant les problèmes (la syntaxe est: chiffre|point espace)voir exemple

Durée d'exécution de l'ordre de la milliseconde/ problème. Testé sur plusieurs centaines de problèmes.

Source / Exemple :


#include <stdio.h>

/*

  • Je ne me suis pas cassé la tête pour faire une belle interface !
  • Seule la résolution par un programme minimum m'intéressait
  • Il suffit de compiler (pas d'autres sources nécessaire) de faire un fichier sudoku.txt contenant les problèmes
  • et de lancer l'exécution !
  • /
int tree(int); int possible(int, int); int readpb(FILE *); void prnt(); int Tab[81]; int main (void) { FILE *input = fopen("sudoku.txt", "r"); if (input == NULL) { printf("sudoku.txt not found\n"); return 1; } while (readpb(input)) { /* jusqu'à ce qu'il n'y ait plus de pb à résoudre */ printf("\nProblem :\n"); prnt(); /* print pb */ tree(0); /* le 1er noeud passé à la recherche en arbre est la racine */ printf("\nSolution :\n"); prnt(); /* print solution */ printf("\n"); } fclose(input); return 0; } int tree(int level) { /*
  • C'est cette routine de 7 lignes C (hors commentaires) qui fait tout
  • Tab[] est une variable globale pour minimiser la pile dans la récursion
  • /
int i; /* traversée de l'arbre */ if (level == 81) return 1; /* noeud final */ if (Tab[level]) return tree(level + 1); /* case occupée => noeud valide */ /* traversée du sous-arbre : noeud->frère */ for (i = 1;i <= 9;i++) if (possible(level, i) && tree(level + 1)) return 1; /* traversée : noeud->fils */ return (Tab[level] = 0); /* fin du sous-arbre : restauration noeud = free et return noeud->père */ } int possible(int n, int test) { int i, j, q, r, p; /*
  • Test s'il est possible de placer le nombre test sur la case n, les cases sont numérotées de 0 à 80
  • de gauche à droite et ligne par ligne
  • retour = 1 possible, 0 pas possible.
  • /
q = n / 9; r = n - 9 * q; for (i = 0;i < 9;i++) if (Tab[9 * q + i] == test || Tab[9 * i + r] == test) return 0; q /= 3; r /= 3; p = 3 * (9 * q + r); for (i = 0;i < 3;i++) for (j = 0;j < 3;j++) if (Tab[p + 9 * i + j] == test) return 0; Tab[n] = test; return 1; } void prnt() { /*
  • print d'une grille
  • /
int i, j; for (i = 0;i < 9;i++, printf("\n")) for (j = 0;j < 9;j++) printf("%c ", Tab[9 * i + j] ? Tab[9 * i + j] + '0' : '.'); } int readpb(FILE *input) { /* Exemple input file pour 3 problemes (sudoku.txt) : . . . . . . 3 . . . . . 9 . . . 7 . . . 9 . 5 . . 8 1 4 1 . . . 6 . . . . 6 . . 7 . . 2 . . . . 2 . . . 5 4 1 4 . . 3 . 2 . . . 8 . . . 2 . . . . . 5 . . . . . . . 6 . . . 3 1 8 . 2 . 1 6 5 . . . 7 . . . . . . . . . 8 . 3 7 2 . . . 9 . 1 . . . 5 2 3 . . . . . . . . . . . 8 7 3 . 4 . . . . 3 2 5 . 1 . . . . . . . . . 6 5 . . . 9 8 . . 1 . 7 7 6 . . 5 9 . 4 . . . . . . . . . . 8 1 . . 6 4 . 2 . . . 7 5 . . 8 . 6 . . . . . . . . . 4 . 1 3 . 8 . . . 6 . 8 7 . 5 . . . . . . . . . 5 . 9
  • /
char buf[20]; int i, j, k; if (fgets(buf, sizeof(buf), input) == 0) return 0; for (k = i = 0;i < 9;i++, fgets(buf, sizeof(buf), input)) for (j = 0;j < 18;j += 2) Tab[k++] = buf[j] == '.' ? 0 : buf[j] - '0'; return 1; }

A voir également

Ajouter un commentaire Commentaires
Messages postés
166
Date d'inscription
mercredi 24 avril 2002
Statut
Membre
Dernière intervention
23 juin 2009

Bon code améliorable comme tu l'as dit toi même mais 35ms et 15 secondes ce n'est pas négligeable.
Je tiens à dire que je doute que Kirua est plagié quoi que ce soit...
La notation des variables c'est normal faut être explicite et la fonction isValid j'en est une dans quasiment tous mes programmes...
Messages postés
12303
Date d'inscription
mardi 10 février 2004
Statut
Modérateur
Dernière intervention
30 juillet 2012
41
j'ai eu l'honneur de me faire battre par kirua en algo :)
je m'etais attaque a ce probleme il y a quelques temps (durant mes longues nuits d'insomnies)

j'en avais conclu ceci :
[[
plus de 700 ms pour l'algo de bourrin
moins de 20 ms pour un melange basic de l'iteratif et du recursif
moins de 15 ms quand on optimise un peu : on ne recalcule plus a
chaque fois les possibilitees, mais on les fait evoluer intelligement
On optimise aussi le code de retour de la fonction intelligente
j'espere pouvoir passer a moins de 5 ms...
]]

Mon algo calculait UNE solution

j'avais une gestion des chiffres possibles (avec suppression si un test me disait que c'etait pas possible), une deduction lorsqu'une case n'avait plus qu'un chiffre, ou qu'une zone n'avait plus qu'une case pour un chiffre. et une gestion de l'ordre des tests a faire (tester un chiffre sur une case qui comporte peu de possibilites offre evidement un gain de temps)

j'ai pas teste sur beaucoup de plateaux, ni meme overteste mon algo ce qui explique que je ne l'ai pas poste...
les rapports semblent ne pas etres si disproportionnes que la realite semble le laisser paraitre
Messages postés
280
Date d'inscription
dimanche 7 septembre 2003
Statut
Membre
Dernière intervention
8 juillet 2014
5
salut fortix

juste une petite chose:

"l'heuristique que je te propose est une des heuristiques utilisées dans la résolution des problèmes SAT: les contraintes augmentant quand on descend dans l'abre, on choisit un noeud où les contraintes sont les plus fortes ce qui aménera à ne jamais considérer de noeud où les contraintes sont faibles, et donc fera gagner du temps"

l'idée est qu'on parcourt toujours l'arbre (des possibles solutions) entièrement !

c'est seulement l'ordre dans lequel on parcourt les cases du sudoku qui change

il me semble que cette heuristique est généralisable à tous les problèmes qui peuvent s'exprimer par une équation booléenne, et où l'arbre est donc "commutatif", c'est à dire qu'on peut mettre n'importe quelle variable de l'équation booléenne à la racine de l'arbre, ça ne changera pas le nombres de feuilles

par contre quand on parcourt l'arbre, on sait à l'avance que certaines branches sont incorrectes (deux cases avec un 5 dans la même ligne!)

donc il vaut mieux faire remonter "le plus haut possible dans l'arbre" ces noeuds que l'on sait l'avance être faux

voila c'est comme ça que je me représente cette astuce, mais
"les contraintes augmentant quand on descend dans l'abre, on choisit un noeud où les contraintes sont les plus fortes ce qui aménera à ne jamais considérer de noeud où les contraintes sont faibles" me semble déja assez convainquant
Messages postés
17286
Date d'inscription
mercredi 2 janvier 2002
Statut
Modérateur
Dernière intervention
23 décembre 2019
69
Message interessant que tu nous postes là, vais tacher de voir ce que je vais faire pour accelerer ma résolution d'arbre, sur mon projet, au boulot, en triant mes chemins...

pour la petite histoire, j'ai un script, en langage propriétaire, qui conditionne, l'appel de différents modules, en fonction d'un ensemble de variables en entrée.
Mon objectif est de générer le nombre minimal de cas de tests, mais qui passent au final dans tous les modules pouvant être appelé. Je cherche a automatiser la génération de mes fichiers de données de test. Ca fonctionne impeccable, c'est un simplem probleme d'arbre ^^ Mais pour un script en particulier, j'ai 400 et quelques chemins qui visitent une bonne 50aine de 'feuilles'... et mon appli mets 45 minutes a me générer mes cas de tests.

Un peu trop lent a mon gout ^^ D'autant pluq, que j'affine la chose, en parsant maintenant les sous-modules appelés, et qui contiennent eux aussi parfois quelques conditions, ajoutant ainsi de nouvelles feuilles dans mon arbre.

...

pas de rapport direct avec le Sudoku, m'enfin...
Messages postés
3
Date d'inscription
mardi 25 juillet 2006
Statut
Membre
Dernière intervention
18 juin 2007

ACX01B,

Bien sûr, le problème du sudoku peut être reformulé en terme de résolution d'un système d'équations booléennes (comme toute recherche en arbre) ce qui ne change pas sa complexité qui restera toujours celle d'un problème NP-complet.

Les coupures alpha-beta sont utilisées dans la résolution des problèmes à 2 joueurs (par ex. échecs) mais ce procédé peut être étendu à toutes les recherches en arbre. Il consiste à évaluer une borne inférieure et supérieure en tout noeud et à ne pas examiner un sous arbre dont les noeuds mèneront à coup sur à une valeur plus grande (resp. plus petite) qu'une solution déjà connue.

Il y a deux aspects dans le problème sudoku :

- Soit on veut obtenir une solution, et, à la première trouvée on arrête la recherche
- Soit on veut obtenir toutes les solutions et il faut parcourir l'arbre entièrement, même après avoir trouvé une solution

L'heuristique que tu proposes (cases avec contraintes les plus fortes à examiner en premier), ne fait que trier l'ordre d'examen des sous-arbres. Si l'on n'examine pas un noeud où les contraintes sont faibles, on risque de ne pas trouver la solution. En effet, rien ne prouve qu'un tel sous-arbre ne contient pas la solution. On peut construire un problème où l'une des cases n'a aucune contrainte, c'est à dire où n'importe quel chiffre de 1 à 9 peut convenir à priori, et qui pourtant est racine d'un sous-arbre qui contient la solution.

En suivant les URL de ton post, j'ai trouvé une démonstration intéressante de théorèmes sur le sujet, je vais l'examiner en détail :
www.ams.org/notices/200706/tx070600708p.pdf

Autre point :
En examinant le morceau de source fourni par Kirua, j'ai failli tomber à la renverse ! Voilà l'histoire :
Au premier trimestre 2006, l'un de mes collaborateurs et ami m?avait posé plusieurs défis :
- Trouver un algo pour résoudre le problème du sudoku
- Trouver un algo pour résoudre un pb topologique de traversée de ponts (facile)
- Un autre problème topologique dont je ne me souviens plus exactement

A l'époque je lui avais donné les petits sources correspondants.
Je ne poste pratiquement jamais sur les forums (ceci est mon unique contribution, à part une fois en 2002 pour résoudre un TSP à 250 villes, autre pb NP-complet) mais lui le fait très souvent.

Il s'est déjà souvent attribué des travaux qu'il n'a pas fait (Nous sommes tous les 2 Docteurs, lui en analyse numérique et moi en algorithmique).

Il y a un certain nombre d'indices qui me mettent la puce à l'oreille :
Le nom des variables et surtout celui de la fonction de test isValid exactement écrit comme cela, ce qui est quand même curieux.
Il y a également le fait que dans la routine que je lui ai filée je testais la prochaine case à remplir.

Lorsque j'ai posté sur ce forum, j'ai réécrit le programme, n'ayant pas gardé l'original. Je me suis rendu compte qu'il était inutile de faire ce test puisque le prochain noeud à examiner est donné par level. S'il est déjà rempli (Tab[level] != 0) le noeud est valide et l'on passe au suivant level + 1.

Je ne dis pas que ce source est celui que je lui avais passé, je n'ai aucune preuve formelle, mais je dis que tout cela est bizarre. Si mes souvenirs sont exacts, j'avais appelé à l'époque la routine récursive « arbre ». Il serait intéressant que Kirua nous montre la routine de test de validité pour la comparer avec la mienne ainsi que le nom de la routine récursive.

Bref, ceci n'est qu'une anecdote, sans grande importance.

Concernant les 7 lignes de résolution, je n'ai pas intégré dedans la routine « possible » car, à mon avis, elle peut très bien être modifiée pour résoudre d'autres pb que le sudoku (par exemple carrés magiques).

Pour en terminer avec ce post :

Dans les URL que tu m?as données il y a celle ci :
http://www.techno-science.net/?onglet=news&news=4160

Qui donne un problème réputé difficile (seulement 17 cases remplies) c'est le minimum actuellement connu. J'ai testé mon algo dessus, la durée de résolution est de 15 secondes sur un pentium 1,73 Ghz (on est quand même loin des 5 mn)

J'ai également adapté mon algo pour tester les noeuds à analyser dans l'ordre des plus contraints en premier, comme tu le suggérais, ce qui est assez simple.

Le résultat, pour le pb précité à 17 cases est une durée de résolution qui tombe à 35 ms au lieu des 15 secondes. Le tri d'ordre d'examen est donc rentable, bien que l'on ne soit pas à quelques secondes près !

Cordialement
Afficher les 14 commentaires

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.