Sudoku

1. Sudoku solver
2. Sudoku killer
3. Suguru solveur

1. Sudoku solver

1.1. Présentation du puzzle

L’objectif de ce puzzle est de résoudre une grille de sudoku. Le sudoku est un jeu en forme de grille dont on doit remplir les cases avec des chiffres, de façon à ce que chaque ligne, colonne et région (chacun des 9 carrés de 9 cases) ne contienne qu’une seule fois tous les chiffres de 1 à 9. Dans ce codingame, chaque entrée represente une ligne de la grille. Un 0 represente une valeur à modifier. On peut avoir en entrée :

La sortie attendu du programme est la grille résolu :

1.2. Présentation de ma méthode de résolution

1.2.1. Description

Pour résoudre ce puzzle je récupere d’abord chaque ligne et place chaque caractère de la ligne dans un tableau 2d d’entier grâce à la fonction atoi qui permet de convertir un caractère appartenant à ['0'-'9'] en entier. Ensuite j’appelle la fonction resoud_grille pour résoudre la grille de sudoku. Voici les fonctions utilisée:

La fonction est_valide permet de vérifier si une valeur i peut être placée dans une case donnée de la grille, sans enfreindre les règles du Sudoku. Elle parcourt les lignes, les colonnes et les carrés de 3x3 pour vérifier si la valeur n’est pas déjà présente. Si elle trouve la valeur dans l’un de ces cas, elle renvoie 0, sinon elle renvoie 1.

La fonction trouver_case_vide permet de trouver la première case vide de la grille, en parcourant la grille ligne par ligne et colonne par colonne. Elle renvoie 1 si une case vide est trouvée, et 0 sinon.

La fonction resoudre_grille est la fonction principale qui résout la grille. Elle commence par appeler trouver_case_vide pour trouver la première case vide. Si toutes les cases sont remplies, elle renvoie 1 pour indiquer que la grille est résolue. Sinon, elle parcourt les valeurs de 1 à 9 pour trouver la première valeur valide pour la case vide. Si une valeur valide est trouvée, elle place cette valeur dans la case, puis appelle récursivement la fonction resoudre_grille. Si la grille est résolue à ce stade, elle renvoie 1. Sinon, elle réinitialise la case et essaie avec une autre valeur.

1.2.2. Code

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

int est_valide(int grille[][9], int ligne, int colonne, int i) {
  int coin_x = ligne / 3 * 3;
  int coin_y = colonne / 3 * 3;

  for (int x = 0; x < 9; x++) {
    if (grille[ligne][x] == i) return 0;
    if (grille[x][colonne] == i) return 0;
    if (grille[coin_x + (x % 3)][coin_y + (x / 3)] == i) return 0;
  }
  return 1;
}

int trouver_case_vide(int grille[][9], int *ligne, int *colonne) {
  for (int x = 0; x < 9; x++) {
    for (int y = 0; y < 9; y++) {
      if (grille[x][y]==0) {
        *ligne = x;
        *colonne = y;

        return 1;
      }
    }
  }
  return 0;
}

int resoud_grille(int grille[][9]) {
  int ligne;
  int colonne;
  int i;
  if(trouver_case_vide(grille, &ligne, &colonne)==0) return 1;

  for (i = 1; i < 10; i++) {
    if (est_valide(grille, ligne, colonne, i)) {
      grille[ligne][colonne] = i;

      if(resoud_grille(grille)) return 1;
      grille[ligne][colonne] = 0;
    }
  }
  return 0;
}

int main() {
    int j;
    int grille[9][9];
    for (int i = 0; i < 9; i++) {
        char ligne_entree[10];
        scanf("%[^\n]", ligne_entree); fgetc(stdin);
        for (j=0;j<9;j++){
            char temp[2];
            temp[0] = ligne_entree[j];
            temp[1] = '\0';
            grille[i][j] = atoi(temp);
        }
    }


    if (resoud_grille(grille)) {
        for (int x = 0; x < 9; ++x) {
            for (int y = 0; y < 9; ++y) printf("%d", grille[x][y]);
            printf("\n");
        }
    }
    else {
        printf("Pas de sol");
    }

    return 0;
                                                                    }

1.2.3. Test

test 1:

Entrée:

On obtient la grille résolu:

test 2:

Entrée:

On obtient la grille résolu

test 3:

Entrée:

On obtient la grille résolu:

test 4:

Entrée:

On obtient la grille résolu:

1.3. Code de Alain-Delpuch

Il y a une fonction auxiliaire “OK” qui vérifie si un nombre peut être placé dans une case de la grille sans enfreindre les règles du sudoku. Cette fonction vérifie les contraintes de ligne, de colonne et de bloc de 3x3.

La fonction “recur” effectue la récursivité pour placer les nombres dans les cases vides de la grille en appelant la fonction “OK” pour chaque nombre tenté. Si un nombre ne peut pas être placé, la fonction annule la tentative précédente (backtracking) et essaie le nombre suivant jusqu’à ce qu’elle atteigne une solution.

Le code est interressant car il est assez court et il utilise static inline int. J’ai fait quelque recherche et j’ai appris son utilité : Avantages : static inline peut améliorer les performances de votre programme en permettant au compilateur de “fusionner” les fonctions avec les appels, ce qui peut réduire les coûts d’appels de fonctions et de la surcharge d’empilement (stack). static inline peut également réduire la taille du binaire généré, en évitant la duplication de code pour des fonctions courtes ou très utilisées. Inconvénients : static inline peut augmenter la taille de votre code source, en raison de la duplication de code en ligne, ce qui peut rendre votre code moins lisible et moins maintenable. static inline peut également augmenter le temps de compilation, en raison de la nécessité de recompiler le code source chaque fois que la fonction est utilisée.

#include <stdio.h>
// ------------------------------------------------------------------------------------
char t [81+1];

static inline int
ko(int row, int col, char n){
    char * p = t + 9 * row + col;
    return *p == n;
}
// ------------------------------------------------------------------------------------
int
OK(int index, char n){
    int row = index / 9;
    int col = index % 9;
    for (int i = 0 ; i < 9 ; i++) {
        if ( ko( row ,   i , n ) ) return 0;        // check line
        if ( ko(   i , col , n ) ) return 0;        // check column
    }

    row = 3 * ( row / 3 );
    col = 3 * ( col / 3 );

    for (int i = 0 ; i < 3 ;i++){
        for (int j = 0 ; j < 3 ; j++){
            if ( ko ( row + i , col + j , n ) ){    // check little square
                return 0;
            }
        }
    }
    return 1;                                       // all pass, good!
}
// ------------------------------------------------------------------------------
int
recur(int depth, int index){
    for (;; index++) {                                   // find first empty slot
        if (   index  == 81 ) return 1;                  // yes! got solution
        if ( t[index] == '0') break;                     // got an empty slot
    }
    for ( char n = '1' ; n <= '9' ; n++){                // try all 9 digits
        if ( OK (index ,n)) {
            t[index]= n;
            if (recur(depth+1, index +1 )) return 1;
            t[index]= '0';
        }
    }
    return 0;
}
// ------------------------------------------------------------------------------
main(){
    for (int i = 0; i < 81; i +=9 ) {
        scanf("%s\n", t + i );
    }
    recur(0,0);
    for (int i = 0; i < 81; i++) {
        printf("%c", t[i]);
        if (i%9==8) printf("\n");
    }
}

1.4. Apprentissage

J’ai appris à mieux utiliser et comprendre les fonctions récursives. J’ai aussi appris à bien diviser mon code sous forme de fonctions. Observer d’autre code m’a permis d’apprendre de nouvelle chose sur le language C (static inline).

2. Sudoku killer

2.1. Presentation du puzzle

Les règles du sudoku sont les meme que celle du sudoku classique, avec une règle en plus. Il y a des cages mise en place dans la grille et dans chaque cage un nombre y est associé. Il faut que la somme de chaque chiffre dans la cage soit égal au nombre associé à la cage. Voici comment se présente une entrée du sudoku killer.

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

Les points représente les case à remplir, la grille de caractère à droite represente les délimitation de chaque cage. Enfin en dernière ligne on a pour chaque cage la valeur associé. On doit obtenir en sortie:

2.2. Présentation de ma méthode de résolution

2.2.1. Description

Pour résoudre ce sudoku j’ai d’abord utilisé la méthode de resolution d’un sudoku classique. A cela j’ai ajouté la conditions de la cage. J’utilise deux nouvelles fonctions pour cette conditions. La premiere qui est valeurCage(), qui retourne la somme actuel de la cage en question. J’ajoute a cela une fonction testCage qui regarde si le nombre que l’on teste a ajouter n’apparait pas deja dans la cage en question. Je modifie le code de la fonction est_valide pour ajouter la nouvelle conditions de la cage.

2.2.2. Code

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


int valeurCage(int tab[9][9],char cage[9][10],char recherche,int n){
    int somme=n;
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            if (cage[i][j]==recherche){
                    somme+=tab[i][j];
            }
        }
    }
    return somme;
}

int testCage(int tab[9][9],char cage[9][10],char recherche,int n){
    for(int i=0;i<9;i++){
        for(int j=0;j<9;j++){
            if (cage[i][j]==recherche){
                if (tab[i][j]==n){
                    return 1;
                }
            }
        }
    }
    return 0;
}
int est_valide(int grille[][9], int ligne, int colonne, int i,char cage[9][10],char cages[251]) {
  int coin_x = ligne / 3 * 3;
  int coin_y = colonne / 3 * 3;

  for (int x = 0; x < 9; x++) {
    if (grille[ligne][x] == i) return 0;
    if (grille[x][colonne] == i) return 0;
    if (grille[coin_x + (x % 3)][coin_y + (x / 3)] == i) return 0;
  }
  char t[3];
  for(int k=0;k<(int)strlen(cages);k++){
        if (cages[k]==cage[ligne][colonne]){
            t[0]=cages[k+2];
            if (cages[k+3]!=' '){
                t[1]=cages[k+3];
            }
        }
    }

    int val=atoi(t);
    if(valeurCage(grille,cage,cage[ligne][colonne],i)>val){
        return 0;
    }

    if(testCage(grille,cage,cage[ligne][colonne],i)){
        return 0;
    }
  return 1;
}

int trouver_case_vide(int grille[][9], int *ligne, int *colonne) {
  for (int x = 0; x < 9; x++) {
    for (int y = 0; y < 9; y++) {
      if (grille[x][y]==0) {
        *ligne = x;
        *colonne = y;

        return 1;
      }
    }
  }
  return 0;
}

int resoud_grille(int grille[][9],char cage[9][10],char cages[251]) {
  int ligne;
  int colonne;
  int i;
  if(trouver_case_vide(grille, &ligne, &colonne)==0) return 1;

  for (i = 1; i < 10; i++) {
    if (est_valide(grille, ligne, colonne, i,cage,cages)) {
      grille[ligne][colonne] = i;

      if(resoud_grille(grille,cage,cages)) return 1;
      grille[ligne][colonne] = 0;
    }
  }
  return 0;
}

int main() {
    int j;
    int grille[9][9];
    char cage[9][10];
    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 (j=0;j<9;j++){
        if (grid_line[j]=='.'){
          grille[i][j]=0;
        }else{
          grille[i][j]=(int)grid_line[j]-'0';
        }
        cage[i][j]=grid_cages[j];
      }
      cage[i][9]='\0';
    }
    char cages[251];
    scanf("%[^\n]", cages);

    resoud_grille(grille,cage,cages);
    for (int x = 0; x < 9; ++x) {
            for (int y = 0; y < 9; ++y){
            printf("%d", grille[x][y]);
        }
        puts("");
    }
    return 0;
}

2.2.3. Test

test 1:

Entrée:

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

On obtient la grille résolu:

test 2:

Entrée:

.1..65..7 abcccdeee
6.7....15 fbbgddhie
.54..1..3 fjggdkhil
......... fjmgkknil
16..3.5.. ooppqqnrr
..8..2... sotuvqnnw
3......7. xxtuyyzzA
...3..... BCDDEFzAA
.2.1..349 BBDGGGzzz
a=9 b=16 c=17 d=21 e=18 f=12 g=18 h=15 i=12 j=12 k=15 l=5 m=9 n=19 o=10 p=6 q=12 r=17 s=5 t=13 u=15 v=1 w=4 x=7 y=11 z=33 A=12 B=17 C=9 D=10 E=7 F=4 G=14

On obtient la grille résolu:

test 3:

Entrée:

........1 abbcdddef
....5.... agccchfff
...3..... ijjjhhkkl
.......9. ijmmnnokp
..6...... qrrsttuvv
....9.7.. qwxsyuuzA
.....3... qwxxyBBCA
......... qDxEEBBCC
..8..5... DDFFFBGHH
a=14 b=9 c=17 d=22 e=3 f=20 g=3 h=9 i=6 j=21 k=19 l=7 m=9 n=11 o=4 p=6 q=16 r=15 s=11 t=11 u=10 v=9 w=9 x=20 y=16 z=5 A=5 B=22 C=19 D=17 E=11 F=15 G=3 H=11

On obtient la grille résolu:

test 4:

Entrée:

......... 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 temps d’execution est trop long, il n’y a pas de resultats.

2.3. Apprentissage

Lors de ce codingame j’ai appris à appliquer d’autres condition sur un code contenant des fonctions récursives. J’ai aussi appris à gérer des chaines de caractère pour récuperer des nombres et leurs valeurs. J’ai aussi appris que la recursivité n’etait pas toujours optimisée. Le dernier test ne passe pas car il a un temps d’execution bien trop long ce qui montre que mon code ou mon algorithme n’est pas assez optimisée. Je n’ai malheureusement pas réussi à trouver de code valide d’autres personnes pour passer les tests et apprendre sur d’autres méthode.

3. Suguru solveur

3.1. Presentation du puzzle

Suguru (également connu sous le nom de Tectonics) est un jeu de puzzle similaire à Sudoku. Le puzzle est composé de différentes zones, appelées cages. Chaque cage est constituée de 1 à 6 cellules et contient les chiffres de 1 à la taille de la cage. Par exemple, une cage de 2 cellules contient les chiffres 1 et 2, et une cage de 5 cellules contient les chiffres de 1 à 5. Les cellules adjacentes, même en diagonale, ne peuvent jamais contenir le même chiffre. Voici une grille de suguru :

En entrée du programme on a par exemple :

4 5
G. G4 G1 G.
R. G. B. B.
G. R. R4 B.
G. R. R2 B.
G3 G. R. B.

On a une grille de taille 4 x 5. Chaque lettre correspond à une cage, cependant si les lettres ne sont pas adjacentes alors ce sont deux cages différentes. Un . correspond à un espace vide à remplir. Il y a deja quelque chiffre de placée.

La sortie de cette entrée doit etre :

3.2. Description de ma méthode de résolution

3.2.1. Description algorithmique

Pour resoudre ce puzzle je creer plusieurs tableau 2D. Le premier qui est la grille que j’initialise au valeurs donnée, avec 0 si l’emplacement est à modifier. Il y a aussi grillecage est un tableau de caractere qui recupere les cages de la grille. Cependant il peut y avoir deux cages differentes qui ont le meme caractere. Pour palier à cela j’initialise un nouveau tableau 2d de caractere au caractere ’0’. J’utilise des fonctions récursives pour creer ce nouveau tableau. La fonction modif() me permet cela. Elle fonctionne de la manière suivante : Elle cherche le prochain ’0’ de grillecage2 grace à la fonction trouve0() qui renvoie la position (i,j) du prochain 0 et si il n’y a plus de ’0’ alors cette fonction renvoie (-1,-1). J’initialise un caractere lettre à ’A’. Puis tant qu’il y a toujours un 0 dans grillecage2 alors j’ajoute une nouvelle lettre à cette emplacement puis j’appelle la fonction récursive ajoutelettre() qui modifie grillecage2 de sorte que la cage soit remplie de la lettre associé. Grâce à la fonction modif j’obtiens une nouvelle grille de caractere qui sont tous different pour chaque cage. Ensuite après avoir recuperer chaque ligne de l’entrée. Je modifie ces lignes avec les nouveaux caractere associé. Ensuite je boucle sur chaque élement de la grille. J’utilise un tableau de cage. Cage est une structure qui contient : une lettre (qui est identifiant), un nombre qui est la taille de la cage et enfin un tableau d’entier variant entre 0 et 1. Si il y un 1 à l’indice i du tableau alors i apparait deja dans la cage. A l’inverse si il y a un 0 alors i n’apparait pas dans la cage. Ainsi j’ajoute dans mon tableau tabcage chaque cage et ses informations.

J’appelle ensuite la fonction de backtracking resoud_grille qui va résoudre la grille. Cette fonction parcours chaque élément de la grille. Si il y a un 0 alors on va chercher grace a la fonction trouve la position k de ou se trouve la cage correspondante dans tabcage. On boucle ensuite sur la taille de la grille. Si on croise un 0 dans le tableau d’apparition de la cage on teste alors si le nombre l (qui represente l’indice du 0 dans le tableau) n’apparait pas autour (les 8 cases autour). Pour cela j’utilise la fonction la fonction testautour() qui renvoie 1 si aucune des cases autour n’est égal à l. Dans ce cas on ajoute dans notre grille à l’indice correspondant le nombre i. Ainsi on modifie aussi la tableau d’apparition de la cage. On rappelle la fonction resoud_grille() avec la méthode de backtracking. Finalement on affiche la grille grâce à la fonction affichegrille(). Ensuite dans notre main on libère tout l’espace alloué grâce à malloc.

3.2.2. Code

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

struct cage{
  char lettre;
  int nombre;
  int tab[50];
};typedef struct cage cage;

struct pos{
    int i;
    int j;
};typedef struct pos pos;

pos trouve0(char **nouv,int w,int h){
    for (int i=0;i<h;i++){
        for (int j=0;j<w;j++){
            if (nouv[i][j]=='0'){
                return (pos){i,j};
            }
        }
    }
    return (pos){-1,-1};
}

void ajoutelettre(char lettre,char **nouv,char **tab,int i,int j,int w,int h){
    if (j<w-1){
        if (tab[i][j+1]==tab[i][j]){
            nouv[i][j+1]=lettre;
            ajoutelettre(lettre,nouv,tab,i,j+1,w,h);
        }
    }
    if (i<h-1){
        if (tab[i+1][j]==tab[i][j]){
            nouv[i+1][j]=lettre;
            ajoutelettre(lettre,nouv,tab,i+1,j,w,h);
        }
    }
    if (i>0){
      if(tab[i-1][j]==tab[i][j] && nouv[i-1][j]=='0'){
        nouv[i-1][j]=lettre;
        ajoutelettre(lettre,nouv,tab,i-1,j,w,h);
      }
    }
    if (j>0){
      if (tab[i][j-1]==tab[i][j] && nouv[i][j-1]=='0'){
        nouv[i][j-1]=lettre;
        ajoutelettre(lettre,nouv,tab,i,j-1,w,h);
      }
    }
    return;
}

void modif(char **tab,char **nouv,int w,int h){
    pos next0=trouve0(nouv,w,h);
    char lettre='A';
    do{
        nouv[next0.i][next0.j]=lettre;
        ajoutelettre(lettre,nouv,tab,next0.i,next0.j,w,h);
        next0=trouve0(nouv,w,h);
        lettre+=1;
    }while (next0.i!=-1);
}

void affichegrille(int **grille,int w,int h){
    for (int i=0;i<h;i++){
      for (int j=0;j<w;j++){
        printf("%d",grille[i][j]);
      }
      puts("");
    }
    puts("");
}

int trouve(char cle,cage tabcage[],int maxtabcage){
  for (int i=0;i<=maxtabcage;i++){
    if (cle==tabcage[i].lettre){
      return i;
    }
  }
  return -1;
}

int testautour(int x, int y,int test,int **tab,int h,int w){
  if (x+1<h){
        if (tab[x+1][y]==test){
            return 0;
        }
        if (y+1<w){
            if (tab[x+1][y+1]==test){
                return 0;
            }
        }
        if (y-1>=0){
            if (tab[x+1][y-1]==test){
                return 0;
            }
        }
    }
    if (x-1>=0){
        if (tab[x-1][y]==test){
            return 0;
        }
        if (y+1<w){
            if (tab[x-1][y+1]==test){
                return 0;
            }
        }
        if (y-1>=0){
            if (tab[x-1][y-1]==test){
                return 0;
            }
        }
    }
    if (y+1<w){
        if (tab[x][y+1]==test){
            return 0;
        }
    }
    if (y-1>=0){
        if (tab[x][y-1]==test){
            return 0;
        }
    }
    return 1;
}

int deja_dans_tabcage(cage tabcage[],char lettre,int max){
  int i;
  for (i=0;i<max;i++){
    if (tabcage[i].lettre==lettre) {
      return i;
    }
  }
  return -1;
}

void resoud_grille(cage tabcage[],int **grille,char **grillecage,int w,int h,int maxtabcage){
  int k;
  for (int i=0;i<h;i++){
    for (int j=0;j<w;j++){
      if (grille[i][j]==0){
        k=trouve(grillecage[i][j],tabcage,maxtabcage);
        for (int l=1;l<=tabcage[k].nombre;l++){
            if (tabcage[k].tab[l]==0){
              if (testautour(i,j,l,grille,h,w)==1){
                grille[i][j]=l;
                tabcage[k].tab[l]=1;
                resoud_grille(tabcage,grille,grillecage,w,h,maxtabcage);
                grille[i][j]=0;
                tabcage[k].tab[l]=0;
              }
            }
        }
        return;
      }
    }
  }
  affichegrille(grille,w,h);
  exit(0);
}

int main()
{
    int w;
    int h;
    int i,j,k,l,nbdecage=0;
    int **grille;
    char **grillecage;
    char **grillecage2;
    char **tabline;
    cage tabcage[50];
    scanf("%d%d", &w, &h); fgetc(stdin);

    grille=malloc(h*sizeof(*grille));
    grillecage=malloc(h*sizeof(*grillecage));
    grillecage2=malloc(h*sizeof(*grillecage2));
    tabline=malloc(h*sizeof(*tabline));
    for (i=0;i<h;i++){
      grille[i]=malloc(w*sizeof(int));
      grillecage[i]=malloc(w*sizeof(char));
      grillecage2[i]=malloc(w*sizeof(char));
      tabline[i]=malloc((3*w+1)*sizeof(char));
    }

    for (i = 0; i < h; i++) {
        char line[60];
        scanf("%[^\n]", line); fgetc(stdin);
        strcpy(tabline[i],line);
        for (j=0;j<(int)strlen(line);j=j+3){
          grillecage[i][j/3]=line[j];
          grillecage2[i][j/3]='0';
        }
    }

    modif(grillecage,grillecage2,w,h);

    for (i=0;i<h;i++){
      for (j=0;j<w;j++){
        tabline[i][j*3]=grillecage2[i][j];
      }
    }

    for(i=0;i<h;i++){
        for (j=0;j<(int)strlen(tabline[i])-1;j=j+3){
          k=deja_dans_tabcage(tabcage,tabline[i][j],nbdecage);
          if (k!=-1){
              tabcage[k].nombre+=1;
              if (tabline[i][j+1]=='.'){
                grille[i][j/3]=0;
              }else{
                grille[i][j/3]=(int)tabline[i][j+1]-'0';
              }
              tabcage[k].tab[grille[i][j/3]]=1;
            }else{
            tabcage[nbdecage].lettre=tabline[i][j];
            tabcage[nbdecage].nombre=1;
            for (l=0;l<=6;l++) tabcage[nbdecage].tab[l]=0;
            if (tabline[i][j+1]=='.'){
                grille[i][j/3]=0;
            }else{
                grille[i][j/3]=(int)tabline[i][j+1]-'0';
            }
            tabcage[nbdecage].tab[grille[i][j/3]]=1;
            nbdecage+=1;
          }
        }
    }

    resoud_grille(tabcage,grille,grillecage2,w,h,nbdecage);

    // Libération de la mémoire
    for (i=0;i<h;i++){
        free(grille[i]);
        free(grillecage[i]);
        free(grillecage2[i]);
        free(tabline[i]);
    }
    free(grille);
    free(grillecage);
    free(grillecage2);
    free(tabline);
    return 0;
}

3.3. Test

3.3.1. test 1:

Entrée:

4 5
G. G4 G1 G.
R. G. B. B.
G. R. R4 B.
G. R. R2 B.
G3 G. R. B.

On obtient la grille résolu:

3.3.2. test 2:

Entrée:

8 8
G. G. G. M. M5 R. R. G.
R. R. R. R. M. M. G. G.
G. M. R. C. C4 M. G. R.
G. M. M. C. C. B. B. R.
G. M. M. C. B. B. R. R.
R. B. G. G. B. G. G4 G.
R. B. B. G. R. R. G. G.
R. B. B. G. G. R. R. B.

On obtient la grille résolu:

3.3.3. test 3:

Entrée:

15 10
R. B5 B. B4 B. R. R4 R. B. B5 B. R1 R4 R. B.
R4 R. B1 B. R. R6 G. R. B. G4 R. R. G. R6 B1
R. R6 R. G5 G. G. G2 B. B. G3 G. G. G. B. B4
B. B1 B. G. B. B. B. R1 R. R6 C1 C. C. B5 B.
B5 B. R. R. R. B. R. R. G. R. C. C6 R. R1 R.
B. R. R. C. R. B6 B. G. G. G. C. R. R. G. R.
G2 G. C. C1 C. C. R. R3 G. B. B. G. G. G. G4
C. G4 G. C. B3 B. B4 R. R6 R. B. R. R. R. G.
C2 C. C. B. B. R. B. G. R. G. R. R. B. R. B.
C. C6 R3 R5 R. R. R. G5 G. G. G. B6 B2 B4 B.

On obtient la grille résolu:

156423423561452
431316151423261
562543242356134
213621515613456
542143232426214
636356451353536
215142134212614
343635426534325
251212634215163
463564151646245

3.3.4. test 4:

Entrée:

20 20
R. R6 R. B6 B. R. B. B6 B. R. R. B. B5 R6 R. R1 G. G. G. B.
R3 B. B. B2 R. R. R. B. B. B. G6 B. B. R2 R. R. B. G. G. B2
R5 G. B. G. R. G. G3 R. R. G. G. B3 B. G. G. G. B. B5 R. B5
R. G. G5 G. R. G. G. R. B. G. B. R. R. R. G. G. B. B. R. B.
B. B. G. R. B. B. G. B4 B. G. B4 B. R. R. Y. R4 R. B6 R. B.
B5 R. R3 R1 R. Y. G. B. B. G. B. B6 Y. Y. Y. Y. R. R. Y. B4
B. B. G. R. Y. Y. Y. G1 B. R. B. R. B. B5 B. R. R. G. Y. Y.
R. B. G4 G. Y2 Y. R. G3 G. R. R. R5 G. B. B. G3 G. G. G. Y.
R. R. G. G. R. R. R. G. B6 B. R. G4 G. G1 B6 R. G. B. B. G.
R. B3 G. B. B5 R. G. G5 B. B. B2 G. R. G. R. R. R2 R. G. G.
B. B. R. B. B1 Y. Y. R. R. G. B. R6 R. R. B. Y. Y. R. G3 G.
B. B5 R. B. G. R. Y. R. G. G4 R. R. B. B. B3 B. Y4 Y. Y. Y.
G. B. R6 B. G5 R. Y. Y3 G. Y. Y. Y. B. R. G. G. G. G. R1 R4
G. G. R. R3 G. G. R. Y. G. G. Y. G. R. R4 R. Y. G5 G. R3 R.
G. G. B. R. G. G. R4 B. B. B6 G. G5 R. R2 Y. Y. Y. B1 R. R.
R. B5 B. B. B. B. R. R6 B. B. G2 G. G. B. Y. Y1 B. B. B5 G.
R. G. G. G. G. R. R. G. G. B3 R1 B. B6 B. B. R. B. B6 Y. G.
R. B. G6 G. R. G2 G. G. G6 R. R. B. G. R. R3 R4 R. Y. Y. G.
B1 B. B. R. R4 R. R3 B. B. R4 R. G. G. G. R. G. G. Y5 Y. R.
B. B. G. G. G. G. R. B. B3 R. G5 G1 B. B. B. G. G4 G. Y. R.

On obtient la grille résolu après 4-5 min:

3.4. Apprentissage

J’ai appris à mieux me servir des tableau de structure creer par moi-meme. J’ai appris à utiliser de la recursivité pour me déplacer dans un tableau 2D selon des conditions. Cela à été intérressant car j’ai compris une solution d’un exercice de partiels (exercice sur chemin sur une matrice). Cependant mon code n’est pas optimisé car il met 4-5min pour le dernier test. Je trouve que j’ai beaucoup appris lors de ce codingame.

Sudoku

Table of Contents

1. Sudoku solver

1.1. Présentation du puzzle

1.2. Présentation de ma méthode de résolution

1.2.1. Description

1.2.2. Code

1.2.3. Test

1.3. Code de Alain-Delpuch

1.4. Apprentissage

2. Sudoku killer

2.1. Presentation du puzzle

2.2. Présentation de ma méthode de résolution

2.2.1. Description

2.2.2. Code

2.2.3. Test

2.3. Apprentissage

3. Suguru solveur

3.1. Presentation du puzzle

3.2. Description de ma méthode de résolution

3.2.1. Description algorithmique

3.2.2. Code

3.3. Test

3.3.1. test 1:

3.3.2. test 2:

3.3.3. test 3:

3.3.4. test 4:

3.4. Apprentissage