CodeS-SourceS est hébergé par Frontier.fr

Ce site au démarrage

begin process at 2012 05 27 19:05:31

Accueil Codes Tutoriels Forum Livres Emploi Services Connexion

Trouver un code source :

dans

[ Dernières recherches ]

Accueil >

Jeux

> RESOLUTION DE TOUS LES PROBLEMES DE SUDOKU

RESOLUTION DE TOUS LES PROBLEMES DE SUDOKU

Information sur la source

Note :

7,00 / 10

Catégorie :Jeux Classé sous :sudoku, algorithme, minimal Niveau :Initié Date de création :13/06/2007 Vu :18 753

Auteur : Fortix

Ecrire un message privé

Commentaire sur cette source (14)

Ajouter un commentaire et/ou une note

Description

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

#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;
}

#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;
}

Sources de la même categorie

JEU DES CARTES par eapaceinfo

PROGRAMME DE JEU DE MPT par KerizGarmm

JEUX SERPENT par antho974

PENDU EN SDL par Damsou91

STATE MACHINE MODIFICATION MATH BUCKHAM par billybones79

Toutes les sources de la catégorie Jeux

Sources en rapport avec celle ci

PROGRAMME DE SUDOKU par AffreuxJojp

UN EXAMPLE D'APPLICATION EN CUDA DE L'ALGORITHME DE SCAN POU... par oguzaras

RÉSOLUTION SUDOKU (9X9) PAR BACKTRACKING RÉCURSIF INTELLIGEN... par Gallien69

GÉRER UN COMBAT DANS UN JEU 2D / ALGORITHME PRIMAIRE D'UNE I... par Chiheb2010

SUDOKU NIVEAU FACIL, MOYEN DIFFICILE (GOOGLE) PAS AU PLUS par cool2source

Commentaires et avis

Commentaire de acx01b le 13/06/2007 20:21:46

salut

je ne sais pas si tu connais ce "truc":

il est (très) recommandé dans le backtracking de parcourir tout le sudoku pour trouver la case où le nombre de "possibles" est minimal

ensuite tu séléctionnes au hasard parmis ces cases où le nombre de "possibles" est minimal celle que tu traites en premier,
et en appelant ta fonction de backtracking sur une grille vide
tu obtiens une grille parfaitement aléatoire

a+

Commentaire de Kirua le 14/06/2007 11:48:01

Ca fait beaucoup plus que 7 lignes, je me sens eu dans ma naïveté :(. C'est mal de mentir, au moins aussi mal que les variables globales.

Commentaire de shenron666 le 14/06/2007 13:08:44

ton code pourrait faire 1 seule ligne si tu supprimais les retour chariot :-/

à part le "7 lignes" attrape nigeaux le code est pas mal du moment que ça fonctionne

Commentaire de BruNews le 14/06/2007 15:37:49 administrateur CS

"EN 7 LIGNES" enlevé.

Commentaire de Fortix le 14/06/2007 21:05:03

Devant la totale maîtrise de l'algorithmique par Kirua et notamment :

- de sa capacité à comprendre ce qui relève de la résolution d'un problème et ce qui relève de routines annexes sans rapport avec la résolution proprement dite

- de sa profonde compréhension de l'utilisation optimale de variables locales/globales (dans ce cas, passer Tab en variable locale multiplierait la durée du traitement par 40, voit-il seulement pourquoi ?)

- de la perspicacité avec laquelle il comprend le fonctionnement du programme récursif

Je ne peux que m'incliner devant sa science qui prouve à l'évidence son très haut niveau d'étude.

Bon, cela dit, pour les gens sérieux et intéressés par l'intégration de ce source à leur code, il suffit

- de copier/coller les 2 routines tree et possible
- remplir Tab avec les données du problème Tab[0]...Tab[8] = 1ère ligne; Tab[9]...Tab[17] = 2ème ligne etc. (0 = case vide); ça ce n'est pas très difficile
- appeler tree(0)
- récupérer la solution du problème dans Tab au retour de l'appel

Après on n'en fait ce que l'on veut (affichage, print dans un fichier, etc.) mais tout le reste n'est que cosmétique

durée de résolution 0.001 seconde

Commentaire de Kirua le 15/06/2007 13:06:07

Extrait d'un de ses codes pour les sudoku:

   //On récupère l'index de la première case à remplir.
   int zero_cell = firstZeroIndex(start);

   //S'il n'y a plus de case à remplir, c'est gagné!
   if(zero_cell == -1) return true;

   //On essaye de mettre les 9 valeurs dans la cellule vide, une à une.
   for(int val = 1; val <= 9; ++val)
   {
      //On essaye la valeur
      grid[zero_cell] = val;

      //Si elle est valide et qu'on peut résoudre le sudoku (récursion)
      //avec cette valeur, on termine avec succes.
      if(isValid(zero_cell) && solve(zero_cell)) return true;
   }

   //Aucune des valeurs testées n'est acceptable: échec.
   grid[zero_cell] = 0;
   return false;

apparemment, 7 lignes, c'est standard.

Non vraiment, il ne comprend rien à rien.

Mais peut-être estime-t-il que le nombre de lignes dans la routine récursive ne rend pas justice au reste du code qu'il a dû écrire, et que tu as dû écrire aussi.

Peut-être qu'il est un idiot, ça, on ne peut pas l'exclure.

Mais peut-être qu'il sait un peu de quoi il parle, ça, on ne peut pas l'exclure non plus.

Et peut-être, finalement, que tu as pris la mouche de façon excessive eut égard au message qu'il a posté. Et somme toute, sa remarque concernant les variables globales était sans doute une boutade de programmeur pour alléger le ton, puisqu'il est manifeste qu'il n'a pas lu ton code et que donc cette note ne le concernait.

Au fait, peut-être peut-il même amméliorer la constante universelle 7, en proposant ce programme-ci, issu du même code:

SudokuSolver sudoku(argv[i]);
bool success = sudoku.solve();

Il a apparamment réussi l'exploit d'écrire un solveur de sudoku en 2 lignes, c'est proprement impressionnant. Non, réellement, je vous le dis, sa science extrême et sa compétence ne sont pas sujet à débattre.

Commentaire de acx01b le 15/06/2007 16:12:13

salut

le temps de résolution est variable avec ton programme, et il peut monter à 5 minutes au moins sur certaines grilles

regarde la technique que je t'ai donné si tu veux faire mieux

et il y en a d'autres aussi mais qui sont sûrement moins utiles pour la génération de grilles

Commentaire de Fortix le 15/06/2007 21:45:43

Salut ACX01B,

Heureusement, il y a quelques commentaires pertinents !

- En modifiant légèrement le code on peut effectivement générer des grilles, mais ce n’était pas mon objectif
- Concernant la durée de résolution, c’est vrai celle-ci est variable et peut monter à plus de 5 minutes (peut-être beaucoup plus) pour certains problèmes très difficiles (qui seraient probablement hors de portée pour un humain)
- Le tri d’exploration des sous-arbres selon le nombre croissants de fils de sa racine est une heuristique (parmi d’autres) qui permet de descendre globalement plus rapidement dans l’arbre, sans être assuré d’ailleurs d’aller jusqu'à une feuille terminale (on peut très bien être bloqué un peu plus loin, la solution pouvant être dans un sous-arbre dont la racine comporte beaucoup de fils et qui sera donc exploré après les autres)

Pour que cette heuristique soit performante, il faut disposer d’une fonction d’évaluation qui attribue a priori une estimation de valeur globale d’un sous-arbre (et permette des coupures alpha-beta). Or dans ce problème, il ne semble pas possible de calculer une telle fonction.

Le temps de traitement d’une milliseconde est celui résultant d’environ 300 tests effectués sur des grilles trouvées dans les journaux. Ces problèmes ne sont pas trop complexes (sinon personne ne pourrait les résoudre) et l’algorithme trouve donc la solution très rapidement.

J’ai aussi supposé que le problème était « bien posé » c'est-à-dire comportait une solution et une seule, ce qui semble être le cas des problèmes édités dans les journaux.

Pour estimer le temps de traitement maximum (approximativement) on peut fournir une grille ne comportant pas de solution. Il suffit de proposer un problème inexact au départ, par exemple comportant deux fois le même chiffe dans un carré 9x9. Le problème étant supposé bien posé, un cas semblable n’est pas testé ni rejeté. On force ainsi la routine à parcourir tout l’arbre. Comme il y a restauration des emplacements vides la routine renverra la grille proposée sans la solutionner.

Commentaire de acx01b le 16/06/2007 11:30:30

salut

il n'y a pas de rapport entre l'exploration d'arbre de type min et max et le sudoku !

le problème du sudoku est exactement équivalent à un problème sur les graphes
http://www.techno-science.net/forum/viewtopic.php?t=9123
ou à un problème de résolution d'équation booléenne
http://complexite.blog2geek.com/formalisation-du-probleme-du-sudoku-pour-la-reduction-a-sat-717.html
la résolution d'un sudoku est donc un problème NP-complet

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
il y a aussi une autre heuristique qui apparement est efficace pour résoudre à la main les sudoku:
choisir la variable qui est la plus contraignante

je verrais l'algo alors comme ça (dans la fonction backtracking):

min = 10000000000
case_choisie = -1
pour toute case i du sudoku
  soit A l'alphabet des possibles
  pour tout a(k) appartenant à A
    mettre la lettre a(k) dans la case i
    compter n la somme du nombre de possibles de chaque case du sudoku
    si n < min alors min = n et case_choisie = i
  fin pour
fin pour
traiter la case "case_choisie" dans le backtracking

je ne connais pas en détail le moyen d'implémenter les deux heuristiques en même temps mais je pense qu'il est possible de choisir la case qui est à la fois la plus contrainte et la plus contraignante, en faisant d'abord une liste des cases les plus contraignantes puis en choisissant la case la plus contrainte dans cette liste...

a+

Commentaire de Fortix le 18/06/2007 15:36:28

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 <B>isValid</B> 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é, <U>je n’ai aucune preuve formelle</U>, 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

Commentaire de Renfield le 18/06/2007 15:51:29 administrateur CS

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...

Commentaire de acx01b le 18/06/2007 20:59:24

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

Commentaire de coucou747 le 20/06/2007 01:14:41 administrateur CS

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

Commentaire de skone007 le 20/06/2007 02:10:51

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...

Ajouter un commentaire

Discussions en rapport avec ce code source dans le forum

Projet d'été sur SUDOKU!! Aidez-nous s'il vous plait... [ par Naruttibayo ] Au préalable, nous tenons à remercier tous ceux qui contribuerons à notre projet...On nous demande d'écrire un programme C qui permet de Générer des G sudoku en GTK [ par myossi ] Bonjour,J'ai un projet de sudoku à faire en GTK. J'ai trouvé beaucoup de code de sudoku en C. Cependant, il est difficile, même si le GTK c'est du C, algorithme génitique [ par rahma_bou22 ] je veut avoir si c'est possible l'algorithme de probléme de sac à dos Probleme avec backtracking [ par sda2 ] Bonsoir à tous, Je vous expose vite mon probleme, je souhaite realiser un sudoku (9x9), cependant il ne resoud que les sudokus facile, moyen et lui re Probleme backtracking [ par sda2 ] Bonsoir à tous, Je vous expose vite mon probleme, je souhaite realiser un sudoku (9x9), cependant il ne resoud que les sudokus facile, moyen et lui r Interface d'un sudoku sous Gtkmm [ par Jedi_Yoda ] Je cherche a faire afficher dans les 81 labels le "int" resolu qui lui correpond. Mais le set_label(param) n'accepte que les parametres de types "ustr algorithme de conversion de fichier [ par novaghost ] Bonjour, j'aimerais un coup de pouce pour faire un algorithme de conversion de fichier texte. Voila je doit pour exercice, faire un programme qui conv algorithme du bestfit [ par youma85 ] salut tous le monde svp est ce que vous pouvez me donner l'algorithme qui permet de charger un prgramme et le décharger à la mémoire centrale en utili systèmes experts [ par azamharir ] Salut. Je suis en 4° année maîtrise informatique à une faculté des sciences et techniques. Notre prof nous a chargé de faire un mini projet dans le ca Probleme avec un sudoku [ par thomasvd ] Bonjour!je dois réaliser un jeu sudoku et je rencontre quelques problemes dont un qui m'embette particulierement et j'aimerais bien que quelqu'un m'or

Nos sponsors

Derniers Blogs

IMAGINE CUP 2012, MAKE A SIGN EN FINALE par junarnoalg

KINECT 1.5 IS OUT ! par Vko

LES ACTUALITéS DE LA SEMAINE SUR C2I.FR (14 MAI - 20 MAI) par richardc

REACTIVE EXTENSIONS : CONSOMMER DES SERVICES AVEC RX PARTIE 3, LES PIèGES à éVITER par Groc

SHAREPOINT BLOG SITE, PROBLèME D'ARCHIVES par junarnoalg

Forum

SUPERVISION DE LA BATTERIE par romanticgirl

RE : OPENCV ET INTERFACE GRAPHIQUE VISUAL STUDIO par buno

RE : SAC A DOS par hadjkaddour

OPENCV ET INTERFACE GRAPHIQUE VISUAL STUDIO par ssaif

RE : EFFACER UNE IMAGE AVEC SDL EN C par mouni12imane

Côté IT

Offres d'emploi

Formations Video

Appels d'offres

Realisation d-une version 2 d-un site e-commerce existant sous prestashop-REPUBLICATION
Budget : 5 000€
Recherche Infogerance Serveur Debian Linux
Budget : 1 800€
Creation d-un site vitrine avec MagentO
Budget : 2 000€

Logiciels

sDEVIS-FACTURES vlPRO (8.1.0.3)
SDEVIS-FACTURES VLPRO (8.1.0.3)

sDEVIS-FACTURES vlPRO a été mis au point pour les particuliers, créateurs, entrepreneurs, artisa...

Cliquez pour télécharger sDEVIS-FACTURES vlPRO
974 Application Server (12.2.4.6)
974 APPLICATION SERVER (12.2.4.6)

Développez de puissantes applications dans un environnement de 'cloud computing', clusterisé, séc...

Cliquez pour télécharger 974 Application Server
vPicture (1.4.2.1)
VPICTURE (1.4.2.1)

Avec vPicture, hébergez vos images facilement et rapidement. vPicture est un utilitaire simple, ...

Cliquez pour télécharger vPicture
Easy-Planning (2.2.1.6)
EASY-PLANNING (2.2.1.6)

Easy-Planning permet de créer des plannings sous la représentation de diagrammes et est adapté au...

Cliquez pour télécharger Easy-Planning
COM-BACKUP (2.0)
COM-BACKUP (2.0)

COM-BACKUP est un logiciel de sauvegarde qui permet de planifier les sauvegardes de vos dossiers ...

Cliquez pour télécharger COM-BACKUP