Resolution de tous les problemes de sudoku

Commenter

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

S'inscrire maintenant

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.