Rapport sur sudoku solver

Table of Contents

Isima-logo_INP-RVB.jpg

1. Sudoku solver

1.1. Présentation du problème

sudoku solver est un problème du site codingame. Le but est des créer un solveur de sudoku, c’est un jeux en forme de grille, ou il faut compléter les cases vides avec des valeurs entre 1 et la valeur de la dimension de la grille. Le but est qu’une valeur ne soit présente qu’une seule fois sur une même ligne, une même colonne, et aussi un même bloc. Le bloc est un carré de 3 x 3 pour un sudoku de 9 x 9, c’est une sorte de sous grille qui comprend exactement 9 cases, et il faut que chaque valeurs ne soit présentent qu’une seule fois dans ce bloc. Sur codingame, on nous donne un sudoku de dimension 9 x 9, en donnant en entrée 9 lignes de 9 caractères, avec les cases “vide” qui sont initialisé a 0 et les cases dont on connait deja la valeur sont rempli avec cette valeurs.

1.2. Méthode de résolution

1.2.1. Détail algorithmique

voici la méthode de fonctionnement du code:

graph_sudoku.svg

1.2.2. code de résolution

initialisation de la fonction nvalide, elle reçoit en argument les coordonnees de la case (x,y) ainsi que la valeur de la case que l’ont veut tester (n). cette fonction regarde si dans cette case, il est possible de mettre cette valeur, elle analyse d’abord la ligne grâce à une boucle ’for’ qui va analyser chaque case et renvoyer 0 si la valeurs est déjà présente. On regarde ensuite la colonne grâce à une autre boucle ’for’ qui va analyser chaque case de la colonne et renvoyer 0 si la valeur est déjà présente, puis enfin le bloc dans lequel se trouve la case en se positionant dans le coin en haut a gauche du bloc et une double boucle ’for’ et regarde chaque case du bloc et renvoie 0 si la valeur est déjà présente. 

int n_valide(int y, int x, int n) {
    int x0, y0;

    //on regarde si la valeur n'est pas sur la ligne
    for (x0 = 0; x0 < 9; x0++) {
        if (grid[y][x0] == n) {
            return 0;
        }
    }

    //on regarde si la valeur n'est pas sur la colonne
    for (y0 = 0; y0 < 9; y0++) {
        if (grid[y0][x] == n) {
            return 0;
        }
    }

    //on regarde si la valeur n'est pas dans le bloc,
    //les deux lignes suivantes permmettent de se place
    //dans le coin en haut à gauche de la case
    x0 = (x / 3) * 3;
    y0 = (y / 3) * 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (grid[y0 + i][x0 + j] == n) {
                return 0;
            }
        }
    }
    return 1;
}

initialisation de la fonction résoudre, elle ne prend pas d’argument. Elle crée une double boucle afin de parcourir chaque case de la grille, puis en fonction de si la case est vide ou pas, elle lance une troisième boucle qui permet de tester chaque valeurs (1 à 9), pour enfin, si la fonction nvalide renvoie un résultat favorable, faire la récursion en rappellant la fonction avec la valeurs tester ajoutée a la grille. Une fois que tout cela est finie, la fonction affiche la grille qui est le retour attendu 

void résoudre() {
    int y, x, n;
    for (y = 0; y < 9; y++) {
        for (x = 0; x < 9; x++) {
            if (grid[y][x] == 0) {
                for (n = 1; n <= 9; n++) {
                    if (n_valide(y, x, n)) {
                        grid[y][x] = n;
                        résoudre();
                        grid[y][x] = 0;
                    }
                }
                return;
            }
        }
    }

    //affichage de la grille
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            printf("%d", grid[i][j]);
        }
        printf("\n");
    }
    exit(0);
}

intialisation du main, on initialise la grille en la remplissant avec les charactères données en entrée, qui sont donc de type ’char’, en les remplacant par leurs équivalents en type ’int’. On appelle ensuite la fonction résoudre qui remplit la grille et affiche le résultat 

int main() {
    int i, j;
    char line[10];

    //remplissage de la grille en recevant les caractères de type
    //char et en les transformant en int
    for (i = 0; i < 9; i++) {
        scanf("%s", line);
        for (j = 0; j < 9; j++) {
            grid[i][j] = line[j] - '0';
        }
    }
    //lancement du remplissage de la grille puis de l'affichage
    résoudre();
    return 0;
}

1.2.3. le code en entier

#include <stdio.h>
#include <stdlib.h>

int grid[9][9];

//fonction n_valide qui vérifie qu'il est possible de mettre la
//valeur dans cette case
int n_valide(int y, int x, int n) {
    int x0, y0;

    //on regarde si la valeur n'est pas sur la ligne
    for (x0 = 0; x0 < 9; x0++) {
        if (grid[y][x0] == n) {
            return 0;
        }
    }

    //on regarde si la valeur n'est pas sur la colonne
    for (y0 = 0; y0 < 9; y0++) {
        if (grid[y0][x] == n) {
            return 0;
        }
    }

    //on regarde si la valeur n'est pas dans le bloc
    x0 = (x / 3) * 3;
    y0 = (y / 3) * 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (grid[y0 + i][x0 + j] == n) {
                return 0;
            }
        }
    }
    return 1;
}

//fonction récursive qui remplit la grille
void résoudre() {
    int y, x, n;
    for (y = 0; y < 9; y++) {
        for (x = 0; x < 9; x++) {
            if (grid[y][x] == 0) {
                for (n = 1; n <= 9; n++) {
                    if (n_valide(y, x, n)) {
                        grid[y][x] = n;
                        résoudre();
                        grid[y][x] = 0;
                    }
                }
                return;
            }
        }
    }

    //affichage de la grille
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            printf("%d", grid[i][j]);
        }
        printf("\n");
    }
    exit(0);
}


int main() {
    int i, j;
    char line[10];

    //remplissage de la grille en recevant les caractères de type
    //char et en les transformant en int
    for (i = 0; i < 9; i++) {
        scanf("%s", line);
        for (j = 0; j < 9; j++) {
            grid[i][j] = line[j] - '0';
        }
    }
    //lancement du remplissage de la grille puis de l'affichage
    résoudre();
    return 0;
}

1.3. tests

1.3.1. premier test

avec la chaine de caractère suivante, 

120070560
507932080
000001000
010240050
308000402
070085010
000700000
080423701
034010028

cela donne: 

123874569
567932184
849651237
916247853
358196472
472385916
291768345
685423791
734519628

si on compare le résultat au résultat attendu: 

Test Passé

on voit que le code renvoie bien le bon résultat

On peut d’ailleurs voir que le test passe bien les test de valgrind, ce qui veut dire qu’il n’y a pas d’erreur mémoire 

==29410== Memcheck, a memory error detector
==29410== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==29410== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==29410== Command: ./sudoku
==29410== 
==29410== 
==29410== HEAP SUMMARY:
==29410==     in use at exit: 0 bytes in 0 blocks
==29410==   total heap usage: 2 allocs, 2 frees, 8,192 bytes allocated
==29410== 
==29410== All heap blocks were freed -- no leaks are possible
==29410== 
==29410== For lists of detected and suppressed errors, rerun with: -s
==29410== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

1.3.2. deuxième test

on peut voir qu’avec ces entrées: 

800000000
003600000
070090200
050007000
000045700
000100030
001000068
008500010
090000400

le test passe bien, 

812753649
943682175
675491283
154237896
369845721
287169534
521974368
438526917
796318452

Test Passé

On peut d’ailleurs remarquer que le test passe bien les test du debugger valgrind 

==23514== Memcheck, a memory error detector
==23514== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==23514== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==23514== Command: ./sudoku
==23514== 
==23514== 
==23514== HEAP SUMMARY:
==23514==     in use at exit: 0 bytes in 0 blocks
==23514==   total heap usage: 2 allocs, 2 frees, 8,192 bytes allocated
==23514== 
==23514== All heap blocks were freed -- no leaks are possible
==23514== 
==23514== For lists of detected and suppressed errors, rerun with: -s
==23514== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

1.4. solution de la communauté

J’ai choisi de présenter la solution de Juanmv94 qui a crée une solution non récursive pour réussir ce code. 

#include <stdio.h>

typedef struct {
    unsigned char val : 4;
    unsigned char pred : 1;
} scell;

int main() {
    scell s[9][9];
    for (int i=0;i<9;i++) {
        for (int j=0;j<9;j++) {
            s[i][j].val=getchar()-'0';
            s[i][j].pred=s[i][j].val?1:0;
        }
        getchar();
    }

    int p=0;
    while(p<9*9) {
        int i=p/9,j=p%9;
        if (s[i][j].pred) p++;
        else {
            while (++s[i][j].val<=9) {
                int t;
                for(t=0;t<9;t++) {
                    int si=i/3*3+(t%3);
                    int sj=j/3*3+(t/3);
                    if ((t!=i && s[t][j].val==s[i][j].val) ||
                        (t!=j && s[i][t].val==s[i][j].val) ||
                        ((si!=i || sj!=j) && s[si][sj].val==s[i][j].val)) break;
                }
                if (t>=9) break;
            }
            if (s[i][j].val>=10) {
                s[i][j].val=0;
                do {p--;} while (s[p/9][p%9].pred);
            } else p++;
        }
    }


    for (int i=0;i<9;i++) {
        for (int j=0;j<9;j++) putchar(s[i][j].val+'0');
        putchar('\n');
    }
    return 0;
}

Il définie d’abord une structure scell contenant 2 charactères non signées val et pred, ensuite tout se passe dans le main. Il définie un tableau 2D de 9 x 9, et de type scell, il remplie ensuite son tableau avec les valeurs, puis il commence l’analyse, avec une boucle non bornée qui parcours chaque case du tableau, ensuite il analyse pour chaque valeurs possible dans la case. Lorsque tout cela est finie il affiche la grille.

2. killer sudoku solver

2.1. présentation du problème

killer sudoku est une version un peut plus complexe du sudoku, en effet il respecte les mêmes règles que le sudoku classique, mais on ajoute des cages avec une valeurs pour chaque cages, et la somme de tout les éléments de la cages doit être égale a cette valeur

2.2. méthode de résolution

2.2.1. détail algorithmique

graph_sudoku_killer.svg

2.2.2. le code entier

#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int tab[10][10];
char cage[10][10];
int valeur[100];
char lettre[100];
int compteur[100];

// fonction find_cages qui trouve le nombre de cases dans une cages et regarde
// si la valeur est possible
int find_cage(int x, int y, int n) {

  int somme = n;
  int k = 0;
  int stop = 0;
  int i = 0;
  int j = 0;
  int count = 0;

  while ((lettre[k] != '\0') && (stop != 1)) {
    if (lettre[k] == cage[y][x]) {
      stop = 1;
    }

    k++;
  }

  while ((i < 9) && (compteur[k - 1] != count)) {
    while ((j < 9) && (compteur[k - 1] != count)) {
      if ((cage[i][j] == cage[y][x]) && (tab[i][j] != 0)) {
        somme += tab[i][j];
        count++;
        if (somme > valeur[k - 1]) {
          return -1;
        }
      } else if ((cage[i][j] == cage[y][x]) && (tab[i][j] == 0) &&
                 ((i != y) || (j != x))) {
        return 1;
      }
      j++;
    }
    j = 0;
    i++;
  }

  if (somme == valeur[k - 1]) {
    return 1;
  }
  return 0;
}

// fonction test qui teste les règles du sudoku basique (colonne ,ligne et bloc
// 3x3)
int test(int y, int x, int n) {
  int x0 = 0, y0 = 0;
  int count = 1;

  while (x0 < 9 && count == 1) {
    if (tab[y][x0] == n) {
      count = 0;
    }
    x0++;
  }

  while (y0 < 9 && count == 1) {
    if (tab[y0][x] == n) {
      count = 0;
    }
    y0++;
  }

  x0 = (x / 3) * 3;
  y0 = (y / 3) * 3;
  int i = 0;
  while (i < 3 && count == 1) {
    int j = 0;
    while (j < 3 && count == 1) {
      if (tab[y0 + i][x0 + j] == n) {
        count = 0;
      }
      j++;
    }
    i++;
  }
  return count;
}

// fonction solve récursive qui va analyser toute la grille en testant tout ce
// qui est possible
void solve() {
  int y, x, n;
  for (y = 0; y < 9; y++) {
    for (x = 0; x < 9; x++) {
      if (tab[y][x] == 0) {
        for (n = 1; n < 10; n++) {
          int find = find_cage(x, y, n);
          int test2 = test(y, x, n);
          if ((test2 == 1) && (find == 1)) {
            tab[y][x] = n;
            solve();
            tab[y][x] = 0;
          } else if ((test2 == 1) && (find == -1)) {
            break;
          }
        }
        return;
      }
    }
  }

  for (int i = 0; i < 9; i++) {
    for (int j = 0; j < 9; j++) {
      printf("%d", tab[i][j]);
    }
    printf("\n");
  }
  exit(0);
}

// fonction voisin qui va renvoyer le nombre de voisins d'une case
int voisin(int i, int j, char name, int count, int teste[10][10]) {

  if (cage[i][j] != name) {
    return count;
  }

  count++;
  teste[i][j] = 1;

  if ((i != 0) && (teste[i - 1][j] != 1)) {
    count = voisin(i - 1, j, name, count, teste);
  }
  if ((j != 0) && (teste[i][j - 1] != 1)) {
    count = voisin(i, j - 1, name, count, teste);
  }
  if ((j != 8) && (teste[i][j + 1] != 1)) {
    count = voisin(i, j + 1, name, count, teste);
  }
  if ((i != 8) && (teste[i + 1][j] != 1)) {
    count = voisin(i + 1, j, name, count, teste);
  }

  return count;
}

int main() {
  for (int i = 0; i < 9; i++) {
    char grid_line[10];
    char grid_cages[10];
    scanf("%s%s", grid_line, grid_cages);
    fgetc(stdin);
    for (int j = 0; j < 9; j++) {
      if (grid_line[j] != '.') {
        tab[i][j] = grid_line[j] - '0';
      } else {
        tab[i][j] = 0;
      }

      cage[i][j] = grid_cages[j];
    }
  }
  char cages[251];
  scanf("%[^\n]", cages);

  int j;
  int i = 0;
  int k = 0;
  int y = 0;
  int x = 0;
  char stock_nb[10];
  int trouve = 0;
  int xsave, ysave;

  while (cages[i] != '\0') {
    if (((cages[i] <= 'Z') && (cages[i] >= 'A')) ||
        ((cages[i] <= 'z') && (cages[i] >= 'a'))) {
      j = 2;

      while ((cages[i + j] <= '9') && (cages[i + j] >= '0')) {
        stock_nb[j - 2] = cages[i + j];
        j++;
      }

      valeur[k] = atoi(stock_nb);
      lettre[k] = cages[i];
      while (trouve != 1) {
        while ((trouve != 1) || (x < 9)) {
          if (lettre[k] == cage[y][x]) {
            trouve = 1;
            xsave = x;
            ysave = y;
          }
          x++;
        }
        x = 0;
        y++;
      }
      y = 0;
      trouve = 0;

      int teste[10][10] = {0};
      compteur[k] = voisin(ysave, xsave, cage[ysave][xsave], 0, teste);
      stock_nb[0] = '\0';
      stock_nb[1] = '\0';
      stock_nb[2] = '\0';
      k++;
    }
    i++;
  }

  solve();

  return 0;
}

2.3. tests

2.3.1. premier test

on peut voir qu’avec ces entrées: 

56..1..2. aabbccdde
..72..68. afghhiide
..2.87.15 jfggklmme
......3.9 jjgnklopp
.7....2.. qqgnooorr
9.634.8.. stuuvwwxx
2.9..8... stuuvvwyz
..41.2... sAuuByyyz
.8.4...3. CADDBEEFF
a=12 b=17 c=4 d=14 e=15 f=13 g=19 h=7 i=10 j=16 k=10 l=13 m=10 n=15 o=15 p=13 q=11 r=11 s=18 t=3 u=28 v=15 w=20 x=8 y=22 z=12 A=11 B=13 C=6 D=9 E=10 F=5

le test passe bien, 

568913427
197254683
342687915
851726349
473891256
926345871
219538764
734162598
685479132

Test Passé

On peut d’ailleurs remarquer que le test passe bien les test du debugger valgrind 

==23533== Memcheck, a memory error detector
==23533== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==23533== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==23533== Command: ./killer
==23533== 
==23533== 
==23533== HEAP SUMMARY:
==23533==     in use at exit: 0 bytes in 0 blocks
==23533==   total heap usage: 2 allocs, 2 frees, 8,192 bytes allocated
==23533== 
==23533== All heap blocks were freed -- no leaks are possible
==23533== 
==23533== For lists of detected and suppressed errors, rerun with: -s
==23533== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

2.3.2. deuxième test

on peut voir qu’avec ces entrées, les entrées du 4ème test: 

......... abbcccddd
......... aabefghii
......... jkkefghil
......... jmnnnooil
......... mmmppqqrl
......... sttpuuqrr
......... svwwwxxxy
......... zvvABBCCy
......... zDDAAEEFF
a=7 b=23 c=13 d=13 e=5 f=10 g=17 h=11 i=28 j=12 k=8 l=16 m=20 n=9 o=11 p=22 q=14 r=8 s=15 t=13 u=4 v=17 w=11 x=16 y=8 z=4 A=19 B=10 C=7 D=13 E=15 F=6

le test passe bien, mais seulement sur machine, le code n’est pas assez optimisé et ducoup provoque une erreur sur codingame car le temps d’execution est trop long… Seul ce test ne passe pas, les 3 premiers passe sans problèmes 

496175238
218369547
753248691
531627489
827594316
649813752
962451873
374982165
185736924

Test Passé

On peut d’ailleurs remarquer que le test passe bien les test du debugger valgrind 

==33091== Memcheck, a memory error detector
==33091== Copyright (C) 2002-2017, and GNU GPL'd, by Julian Seward et al.
==33091== Using Valgrind-3.18.1 and LibVEX; rerun with -h for copyright info
==33091== Command: ./killer
==33091== 
==33091== 
==33091== HEAP SUMMARY:
==33091==     in use at exit: 0 bytes in 0 blocks
==33091==   total heap usage: 2 allocs, 2 frees, 8,192 bytes allocated
==33091== 
==33091== All heap blocks were freed -- no leaks are possible
==33091== 
==33091== For lists of detected and suppressed errors, rerun with: -s
==33091== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)

3. suguru solver

3.1. présentation du problème

Le suguru est un autre type de problèmes assez similaire au sudoku ou au killer sudoku, on dispose d’une grille composée de cages, un peut a la manière du killer sudoku, cependant les règles diffèrent du killer sudoku. On ne respecte plus les règle du sudoku simple, on regarde seulement les cages. Il faut mettre chaque valeur de 1 à n dans une cage, avec n qui représente le nombre de cases qu’il y a dans une cage. Il faut aussi que deux valeurs identique ne se “touche” pas même en diagonale, cela n’est pas possible:

1 2 3
4 5 6
7 8 5

car deux “5” sont à coter.

3.2. méthode de résolution

le gros problème de cet exercice est de réussir a trouver les cages, car comme dit dans la consigne, un meme indice de cages peut etre utilisé pour plusieurs cages.

Ce que je n’ai pas réussi à faire malheureusement, en essayant plusieurs méthode, récursive et itérative

3.2.1. le code entier

voila le morceau de code que j’ai reussi a faire en repartant de la base de mon sudoku. 

#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <stdbool.h>

char grille[60][60]={"\0"};
char cages[60][60]={"\0"};
int w;
int h;

int taille_case(int i, int j){
    int s=0;
    if (i<h && cages[i+1][j]==cages[i][j]){
        s+=1+taille_case(i+1,j);
    }
    /*if(i>0 && cages[i-1][j]==cages[i][j]){
        s+=1+taille_case(i-1,j);
    }*/
    if (j<w && cages[i][j+1]==cages[i][j]){
        s+=1+taille_case(i,j+1);
    }
    /*if(j>0 && cages[i][j-1]==cages[i][j]){
        s+=1+taille_case(i,j-1);
    }*/
    return s;
}



int n_valide(int y, int x, int n) {
    int x0=0, y0=0;
    int arret=1;

    while (x0 < 9 && arret==1) {
        if (grille[y][x0] == n) {
            arret=0;
        }
        x0++;
    }

    while (y0 < 9 && arret==1) {
        if (grille[y0][x] == n) {
            arret=0;
        }
        y0++;
    }
    
    x0 = (x / 3) * 3;
    y0 = (y / 3) * 3;
    int i=0;
    while (i < 3 && arret==1) {
        int j = 0;
        while (j < 3 && arret==1) {
            if (grille[y0+i][x0+j] == n) {
                arret=0;
            }
            j++;
        }
        i++;
    }
    return arret;
}

void résoudre() {
    int y, x, n;
    for (y = 0; y < h; y++) {
        for (x = 0; x < w; x++) {
            if (grille[y][x] == '0') {
                printf("%d",taille_case(y,x));
                for (n = 1; n < taille_case(y,x); n++) {
                    if (n_valide(y, x, n)) {
                        grille[y][x] = n;
                        résoudre();
                        grille[y][x] = 0;
                    }
                }
                return;
            }
        }
    }
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            printf("%d", grille[i][j]);
        }
        printf("\n");
    }
    exit(0);
}


int main()
{
    scanf("%d%d", &w, &h); fgetc(stdin);
    for (int i = 0; i < h; i++) {
        char line[60]={"\0"};
        scanf("%[^\n]", line); fgetc(stdin);
        for(int j=0;j<60;j++){
            if(line[j]>='A' && line[j]<='Z'){
                sprintf(cages[i],"%s%c",cages[i],line[j]);
            }
            else if(line[j]>='1' && line[j]<='9'){
                sprintf(grille[i],"%s%c",grille[i],line[j]);
            }
            else if(line[j]=='.'){
                sprintf(grille[i],"%s%c",grille[i],'0');
            }
        }
    }

    résoudre();

    return 0;
}

4. conclusion

Les sudoku, killer sudoku, et suguru sont des problèmes qu’il est possible de coder de plusieurs manière, la vraie difficultés est de trouver une méthode de résolution qui soit fonctionnelle et optimisée pour ne pas prendre trop de temps.

vous pouvez retrouver ce rapport sur ma page personelle

Author: Benoit DAJOUX

Created: 2023-03-26 dim. 22:11