J'ai testé la grille sur mon programme et pareil (après avoir attendu longtemps... xD), il ne me retourne rien (enfn, la grille telle quelle).
Le site qui a mit cette grille en ligne à dû se tromper quelque part.
J'ai testé la grille sur mon programme et pareil (après avoir attendu longtemps... xD), il ne me retourne rien (enfn, la grille telle quelle).
Moi aussi, j'ai attendu longtemps. Très longtemps, en fait (>40s).
Je me rends compte qu'un backtracking même ultra-optimisé (je maintiens que ma version peut résoudre n'importe quelle grille valide en quelques millisecondes, jusqu'à preuve du contraire bien sûr), reste désarmé devant une grille fausse (le principe est de faire sortir la solution au début, s'il n'y en a pas, ben... c'est embêtant ).
Ce genre de problème ne se pose pas avec un DLX, par exemple: je viens de tester, le programme répond instantanément qu'il n'y a pas de solution.
[edit]: En fait, théoriquement, dans un cas moyen, un backtracking ne devrait pas avoir trop de difficultés à terminer, vu qu'on élague énormément de branches, et les blocages sont censés se produire assez haut dans l'arbre. Visiblement, il doit néanmoins subsister des cas particuliers...
J'ai testé avec la grille de Pouet_forever et j'ai la solution instantanément.(bah oui, je me suis trompé en recopiant la grille.)
Pour changer un peu, j'ai voulu essayer de jouer certains coups triviaux avant de lancer le bactrack(recherche des singletons).
Dans le cas de la grille testée, ça n'apporte rien, le bactrack est effectué complètement.
J'ai testé 4, 5 grilles et ça semble rester très rapide.
attention , code moche...
#include <stdio.h>
#include <stdlib.h>
#define N 9
typedef struct
{
int pos;
int n;
} cell;
cell cells[N * N];
int possibility[N * N][N + 1];
int cmp(void const *p, void const *q)
{
return ((cell *)p)->n - ((cell *)q)->n;
}
void grid_display(int *g)
{
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
printf("%d", g[i * N + j]);
puts("");
}
puts("");
}
int check_square(int *g, int row, int col, int v)
{
int ox = (col / 3) * 3;
int oy = (row / 3) * 3;
for(int i = oy; i < oy + 3; i++)
for(int j = ox; j < ox + 3; j++)
if(g[i * N + j] == v)
return 0;
return 1;
}
int check_row_col(int *g, int row, int col, int v)
{
for(int i = 0; i < N; i++)
if(g[i * N + col] == v || g[row * N + i] == v)
return 0;
return 1;
}
int check_cell(int *g, int pos, int v)
{
int col = pos % N;
int row = pos / N;
return check_row_col(g, row, col, v) && check_square(g, row, col, v);
}
int backtrack(int *g, int id)
{
int pos = cells[id].pos;
if(id == N * N)
return 1;
if(g[pos])
return backtrack(g, id + 1);
else
{
for(int k = 1; k <= N; k++)
{
if(possibility[pos][k])
if(check_cell(g, pos, k))
{
g[pos] = k;
if(backtrack(g, id + 1))
return 1;
}
}
g[pos] = 0;
return 0;
}
}
int singleton_block(int *g)
{
int n_singletons = 0;
for(int i = 0; i < N; i += 3)
for(int j = 0; j < N; j += 3)
{
int pos = 0;
for(int k = 1; k <= N; k++)
{
int count = 0;
for(int ii = i; ii < i + 3; ii++)
for(int jj = j; jj < j + 3; jj++)
{
if(!g[ii * N + jj] && check_cell(g, ii * N + jj, k))
{
count++;
pos = ii * N + jj;
}
}
if(count == 1)
{
g[pos] = k;
n_singletons++;
}
}
}
return n_singletons;
}
int singleton_col(int *g)
{
int n_singletons = 0;
for(int col = 0; col < N; col++)
{
int pos;
for(int k = 1; k <= N; k++)
{
int count = 0;
for(int row = 0; row < N; row++)
{
if(!g[ row * N + col])
{
if(check_cell(g, row * N + col, k))
{
count++;
pos = row * N + col;
}
}
}
if(count == 1)
{
g[pos] = k;
n_singletons++;
}
}
}
return n_singletons;
}
int singleton_row(int *g)
{
int n_singletons = 0;
for(int row = 0; row < N; row++)
{
int pos;
for(int k = 1; k <= N; k++)
{
int count = 0;
for(int col = 0; col < N; col++)
{
if(!g[ row * N + col])
{
if(check_cell(g, row * N + col, k))
{
count++;
pos = row * N + col;
}
}
}
if(count == 1)
{
g[pos] = k;
n_singletons++;
}
}
}
return n_singletons;
}
void solve(int *g)
{
int find = 0;
do
{
find = singleton_row(g) + singleton_col(g) + singleton_block(g);
for(int i = 0; i < N * N; i++)
{
int n = 0;
int last = 0;
if(!g[i])
{
for(int k = 1; k <= N; k++)
if(check_cell(g, i, k))
{
possibility[i][k] = 1;
last = k;
n++;
}
if(n == 1)
{
g[i] = last;
find = 1;
}
}
cells[i].pos = i;
cells[i].n = n;
}
}
while(find);
qsort(cells, N * N, sizeof *cells, cmp);
backtrack(g, 0);
}
int main(void)
{
int grid[N * N] =
{
0, 0, 0, 0, 0, 5, 0, 8, 0,
0, 0, 0, 0, 6, 1, 0, 4, 3,
0, 0, 0, 0, 0, 0, 0, 0, 0,
0, 1, 0, 5, 0, 0, 0, 0, 0,
0, 0, 0, 1, 0, 6, 0, 0, 0,
3, 0, 0, 0, 0, 0, 0, 0, 5,
5, 3, 0, 0, 0, 0, 0, 6, 1,
0, 0, 0, 0, 0, 0, 0, 0, 4,
0, 0, 0, 0, 0, 0, 0, 0, 0
};
solve(grid);
grid_display(grid);
return 0;
}
81
123456789
456789123
789123456
214365897
365897214
897214365
531642978
642978531
978531642
Process returned 0 (0x0) execution time : 0.016 s
Press any key to continue.
edit: correction d'une coquille dans singleton_block et suppresion d'un test inutile dans la fonction solve.
@yosh: Merci de ton commentaire et désolé du retard de la réponse. En effet ça aurait été plus logique de traiter les cases déjà remplies dans la fonction solve, c'est pas très malin ce que j'ai fait là. Par "ça ne finit pas", j'entendais évidemment par là que ça risquait de prendre assez longtemps à finir. Enfin entre une chose et une autre je n'ai toujours pas eu le temps d'améliorer mon programme.
@GurneyH: Ca m'étonnait un peu que tu trouves une solution alors qu'un backtracking normal n'en trouve pas, mais j'ai compris pourquoi,
la position du 6 dans la deuxième ligne n'est pas "la bonne". En testant avec la grille donnée par Pouet, ça ne trouve pas de solution non plus. Enfin à mon avis la grille est fausse mais bon.
Par contre, en essayant ton code avec ce qui avait été pour moi le pire des cas, ça m'a donné :
donc soit je me sers mal de ton code, soit il y a un petit problème quelque part.
Pour cette grille, j'avais eu comme résultat (après que mon PC ait ramé pendant une bonne vingtaine de secondes, mais ça faut pas le dire ) :
J'avais un doute en recopiant la grille, mais je ne voyait pas le soucis...
Je corrige(j'essaye), le problême que tu as vu.
Je venais de voir que sur certaines grilles, c'était incorrect.
edit:
Coquille trouvée dans la fonction singleton_block c'est corrigé.
Et avec la grille de shaddan.
#include <stdio.h>
#include <stdlib.h>
#define N 9
typedef struct
{
int pos;
int n;
} cell;
cell cells[N * N];
int possibility[N * N][N + 1];
int cmp(void const *p, void const *q)
{
return ((cell *)p)->n - ((cell *)q)->n;
}
void grid_display(int *g)
{
for(int i = 0; i < N; i++)
{
for(int j = 0; j < N; j++)
printf("%d", g[i * N + j]);
puts("");
}
puts("");
}
int check_square(int *g, int row, int col, int v)
{
int ox = (col / 3) * 3;
int oy = (row / 3) * 3;
for(int i = oy; i < oy + 3; i++)
for(int j = ox; j < ox + 3; j++)
if(g[i * N + j] == v)
return 0;
return 1;
}
int check_row_col(int *g, int row, int col, int v)
{
for(int i = 0; i < N; i++)
if(g[i * N + col] == v || g[row * N + i] == v)
return 0;
return 1;
}
int check_cell(int *g, int pos, int v)
{
int col = pos % N;
int row = pos / N;
return check_row_col(g, row, col, v) && check_square(g, row, col, v);
}
int backtrack(int *g, int id)
{
int pos = cells[id].pos;
if(id == N * N)
return 1;
if(g[pos])
return backtrack(g, id + 1);
else
{
for(int k = 1; k <= N; k++)
{
if(possibility[pos][k])
if(check_cell(g, pos, k))
{
g[pos] = k;
if(backtrack(g, id + 1))
return 1;
}
}
g[pos] = 0;
return 0;
}
}
int singleton_block(int *g)
{
int n_singletons = 0;
for(int i = 0; i < N; i += 3)
for(int j = 0; j < N; j += 3)
{
int pos = 0;
for(int k = 1; k <= N; k++)
{
int count = 0;
for(int ii = i; ii < i + 3; ii++)
for(int jj = j; jj < j + 3; jj++)
{
if(!g[ii * N + jj] && check_cell(g, ii * N + jj, k))
{
count++;
pos = ii * N + jj;
}
}
if(count == 1)
{
g[pos] = k;
n_singletons++;
}
}
}
return n_singletons;
}
int singleton_col(int *g)
{
int n_singletons = 0;
for(int col = 0; col < N; col++)
{
int pos = 0;
for(int k = 1; k <= N; k++)
{
int count = 0;
for(int row = 0; row < N; row++)
{
if(!g[ row * N + col])
{
if(check_cell(g, row * N + col, k))
{
count++;
pos = row * N + col;
}
}
}
if(count == 1)
{
g[pos] = k;
n_singletons++;
}
}
}
return n_singletons;
}
int singleton_row(int *g)
{
int n_singletons = 0;
for(int row = 0; row < N; row++)
{
int pos = 0;
for(int k = 1; k <= N; k++)
{
int count = 0;
for(int col = 0; col < N; col++)
{
if(!g[ row * N + col])
{
if(check_cell(g, row * N + col, k))
{
count++;
pos = row * N + col;
}
}
}
if(count == 1)
{
g[pos] = k;
n_singletons++;
}
}
}
return n_singletons;
}
void solve(int *g)
{
int find = 0;
do
{
find = singleton_row(g) + singleton_col(g) + singleton_block(g);
for(int i = 0; i < N * N; i++)
{
int n = 0;
int last = 0;
if(!g[i])
{
for(int k = 1; k <= N; k++)
if(check_cell(g, i, k))
{
possibility[i][k] = 1;
last = k;
n++;
}
if(n == 1)
{
g[i] = last;
find = 1;
}
}
cells[i].pos = i;
cells[i].n = n;
}
}while(find);
qsort(cells, N * N, sizeof *cells, cmp);
backtrack(g, 0);
}
int main(void)
{
int grid[N * N] =
{
0,0,0,0,0,0,0,0,0,
0,0,0,0,0,3,0,8,5,
0,0,1,0,2,0,0,0,0,
0,0,0,5,0,7,0,0,0,
0,0,4,0,0,0,1,0,0,
0,9,0,0,0,0,0,0,0,
5,0,0,0,0,0,0,7,3,
0,0,2,0,1,0,0,0,0,
0,0,0,0,4,0,0,0,9
};
solve(grid);
grid_display(grid);
return 0;
}
987654321
246173985
351928746
128537694
634892157
795461832
519286473
472319568
863745219
Process returned 0 (0x0) execution time : 0.016 s
Press any key to continue.
le prétraitement avant le backtrack permet de remplir une quarantaine de cases dans le cas de cette grille.
@GurneyH: Ca m'étonnait un peu que tu trouves une solution alors qu'un backtracking normal n'en trouve pas, mais j'ai compris pourquoi,
[...]
la position du 6 dans la deuxième ligne n'est pas "la bonne". En testant avec la grille donnée par Pouet, ça ne trouve pas de solution non plus. Enfin à mon avis la grille est fausse mais bon.
J'aurais dû lire ton message plus tôt, j'ai vraiment eu peur en lisant le post de GurneyH jusqu’à ce que je me rende compte de ce petit détail. C'est fort, quand même de tomber sur une bonne grille en se trompant...
Au passage, la grille telle que l'a copiée GurneyH possède apparemment plusieurs solutions (pas compté). Peut-être ceci explique cela (en partie)...
________
Sinon, je voudrais bien poster mes codes, mais ils ne correspondent pas exactement à l'énoncé de l'exo, et je ne trouve pas de temps pour le faire. Au pire, je posterai tel quel.
Bon, je n'ai pas eu le temps d'adapter totalement mon code à l'exercice, j'ai préféré me concentrer sur l'ajout de commentaires. Comme promis, voici un backtracking "évolué", censé pouvoir résoudre n'importe quelle grille 9x9 (valide) extrêmement rapidement.
Le principe est de comptabiliser au cours de la descente récursive le nombre de valeurs possibles pour chaque case, et choisir à chaque fois la case comportant le minimum de solution. Cette technique a pour caractéristique d'"amener" la solution extrêmement rapidement (vous pouvez vous amuser à ajouter un compteur d'entrées dans la fonction de backtracking et comparer avec une version standard pour vous en convaincre).
Le code ci-dessous comprends quelques optimisations supplémentaires, mais elles sont mineures, mis à part le fait d'utiliser un tableau de variables globales pour stocker le nombre de valeurs candidates pour chaque case, qui apporte aussi un gain non négligeable.
Code en C99, à compiler avec l'option -std=C99
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#define N (3)
#define N_2 (N*N)
#define start (1)
////////////////////////////////////////////////////////////
// Fonction d'affichage
////////////////////////////////////////////////////////////
void affichage (int grille[N_2][N_2])
{
for (int i=0; i<N_2; i++)
{
for (int j=0; j<N_2; j++)
{
printf( ((j+1)%N) ? "%d " : "%d|", grille[i][j]);
}
putchar('\n');
if (!((i+1)%N))
puts("------------------");
}
puts("\n\n");
}
////////////////////////////////////////////////////////////
// Listes circulaires : définition et fonctions
////////////////////////////////////////////////////////////
typedef struct _node
{
struct _node* prev;
struct _node* next;
int i, j, b;
int nbValeursPossibles;
} CIRCL_LIST;
CIRCL_LIST* createRoot (void)
{
CIRCL_LIST* node = malloc(sizeof *node);
node->prev = node->next = node;
return node;
}
CIRCL_LIST* circular_list_append (CIRCL_LIST* root)
{
CIRCL_LIST* node = malloc(sizeof *node);
node->prev = root->prev;
node->next = root;
root->prev->next = node;
root->prev = node;
return node;
}
void deleteAll (CIRCL_LIST* root)
{
CIRCL_LIST *next;
for (CIRCL_LIST* iter = root->next; iter != root; iter = next)
{
next = iter->next;
free (iter);
}
free (root);
}
////////////////////////////////////////////////////////////
// Resolution Sudoku
////////////////////////////////////////////////////////////
// Variables globales pour la mémorisation
bool existeSurLigne[N_2][N_2];
bool existeSurColonne[N_2][N_2];
bool existeSurBloc[N_2][N_2];
////////////////////////////////////////////////////////////
// Backtracking "adaptatif" :
// décide dynamiquement la branche de l'arbre à explorer
////////////////////////////////////////////////////////////
bool estValide (int grille[N_2][N_2], CIRCL_LIST* root)
{
bool ret = false;
if (root == root->next) // la liste est vide
return true;
// cherche la case avec un nombre de valeurs possibles minimal
int min = N_2+1;
CIRCL_LIST* pos = NULL;
for (CIRCL_LIST* iter = root->next; iter != root && min != 0; iter = iter->next)
{
if (iter->nbValeursPossibles < min)
pos = iter, min = iter->nbValeursPossibles;
}
if (min == 0) return false; // si le nombre de valeurs possibles vaut 0, on stoppe
int i = pos->i, j = pos->j, b = pos->b;
// supprimme temporairement le noeud de la liste
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
// Crée une liste de voisins de la case sélectionnée (même ligne/colonne/bloc)
CIRCL_LIST* voisins[2*(N_2-1)+(N-1)*(N-1)];
unsigned n = 0;
for (CIRCL_LIST* iter = root->next; iter != root; iter = iter->next)
if ( iter->i == i || iter->j == j || iter->b == b )
voisins[n++] = iter;
unsigned nb = 0;
for (int k=0; k < N_2 && nb != min; k++)
{
// si on peut placer k+start
if ( !existeSurLigne[i][k] && !existeSurColonne[j][k] && !existeSurBloc[b][k] )
{
// on actualise le champ 'nbValeursPossibles' dans la liste
for (CIRCL_LIST** it = voisins; it != voisins+n; it++)
if ( !existeSurLigne[(*it)->i][k] && !existeSurColonne[(*it)->j][k] && !existeSurBloc[(*it)->b][k] )
(*it)->nbValeursPossibles--;
// Ajoute k aux valeurs enregistrées
existeSurLigne[i][k] = existeSurColonne[j][k] = existeSurBloc[b][k] = true;
if ( (ret = estValide(grille, root)) )
{
grille[i][j] = k+start;
break;
}
// Supprime k des valeurs enregistrées
existeSurLigne[i][k] = existeSurColonne[j][k] = existeSurBloc[b][k] = false;
// on re-actualise le champ 'nbValeursPossibles' dans la liste
for (CIRCL_LIST** it = voisins; it != voisins+n; it++)
if ( !existeSurLigne[(*it)->i][k] && !existeSurColonne[(*it)->j][k] && !existeSurBloc[(*it)->b][k] )
(*it)->nbValeursPossibles++;
nb++;
}
}
// avant de quitter, on restaure le noeud dans la liste
pos->prev->next = pos;
pos->next->prev = pos;
return ret;
}
// compte (naïvement) le nombre de solutions possibles pour une case
int nb_possibles (int i, int j, int b)
{
int ret = 0;
for (int k=0; k < N_2; k++)
if ( !existeSurLigne[i][k] && !existeSurColonne[j][k] && !existeSurBloc[b][k] )
ret++;
return ret;
}
bool resolution (int grille[N_2][N_2])
{
// Initialise les tableaux
for (int i=0; i < N_2; i++)
for (int j=0; j < N_2; j++)
existeSurLigne[i][j] = existeSurColonne[i][j] = existeSurBloc[i][j] = false;
// Enregistre toutes les valeurs déjà présentes dans la grille
int k;
for (int i=0; i < N_2; i++)
for (int j=0; j < N_2; j++)
if ( (k = grille[i][j]) != 0)
existeSurLigne[i][k-start] = existeSurColonne[j][k-start] = existeSurBloc[N*(i/N)+(j/N)][k-start] = true;
// Crée une liste circulaire doublement chainée contenant toutes les cases vides
CIRCL_LIST *positions = createRoot(), *node = NULL;
for (int i=0; i < N_2; i++)
for (int j=0; j < N_2; j++)
if ( grille[i][j] == 0 )
{
node = circular_list_append ( positions );
node->i = i, node->j = j, node->b = N*(i/N)+(j/N);
node->nbValeursPossibles = nb_possibles(i, j, node->b);
}
// Appelle la fonction récursive estValide()
bool ret = estValide (grille, positions);
deleteAll (positions);
return ret;
}
int main (void)
{
// int grille[N_2][N_2] =
// {
// {0,0,0,0,0,0,0,0,0},
// {0,0,0,0,0,3,0,8,5},
// {0,0,1,0,2,0,0,0,0},
// {0,0,0,5,0,7,0,0,0},
// {0,0,4,0,0,0,1,0,0},
// {0,9,0,0,0,0,0,0,0},
// {5,0,0,0,0,0,0,7,3},
// {0,0,2,0,1,0,0,0,0},
// {0,0,0,0,4,0,0,0,9},
// };
//
//
// int grille[N_2][N_2] =
// {
// {9,0,0,1,0,0,0,0,5},
// {0,0,5,0,9,0,2,0,1},
// {8,0,0,0,4,0,0,0,0},
// {0,0,0,0,8,0,0,0,0},
// {0,0,0,7,0,0,0,0,0},
// {0,0,0,0,2,6,0,0,9},
// {2,0,0,3,0,0,0,0,6},
// {0,0,0,2,0,0,9,0,0},
// {0,0,1,9,0,4,5,7,0}
// };
int grille[N_2][N_2] =
{
{0,0,0,0,0,0,0,3,1},
{6,0,0,0,2,0,0,0,0},
{0,0,0,0,7,0,0,0,0},
{0,5,0,1,0,8,0,0,0},
{2,0,0,0,0,0,6,0,0},
{0,0,0,3,0,0,0,7,0},
{0,0,0,0,4,0,2,0,0},
{0,3,0,5,0,0,0,0,0},
{7,0,0,0,0,0,0,0,0},
};
affichage(grille);
clock_t t1 = clock();
resolution (grille);
clock_t t2 = clock();
affichage(grille);
printf(" %gs\n\n", (double)(t2-t1)/CLOCKS_PER_SEC);
return 0;
}
Cette technique n'est pourtant absolument pas la meilleure (ni même la bonne) manière de résoudre un sudoku de dimension supérieure (16x16 ou 25x25). J’espère présenter prochainement un autre code le permettant.
PS : Si quelqu'un trouve une grille valide mettant ce code en échec (temps de résolution > 0.1s), merci de le signaler.
Merci de me faire mentir Marc. =)
Le truc c'est qu'encore une fois, c'est un truc pour débutants et je sais que yoch, GurneyH ou encore toi savent le faire. Donc au final, on reste sur 1 participant !
Par contre, un 'vrai' sudoku n'a qu'une seule et unique solution, donc s'il y en a plusieurs c'est que ce n'est pas un 'vrai' sudoku.
Bonjour, j'ai essayé defaire un bench des codes présentés pour le moment(hormis pour Marc dont le fonctionnement du code est un peu différent).
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
#include <time.h>
#define N (3)
#define N_2 (N*N)
#define start (1)
////////////////////////////////////////////////////////////
// Fonction d'affichage
////////////////////////////////////////////////////////////
void affichage (int grille[N_2][N_2])
{
for (int i=0; i<N_2; i++)
{
for (int j=0; j<N_2; j++)
{
printf( ((j+1)%N) ? "%d " : "%d|", grille[i][j]);
}
putchar('\n');
if (!((i+1)%N))
puts("------------------");
}
puts("");
}
/* Shaddan ------------------------------------------------------------------ */
#define SIZE 9
typedef int Grid[SIZE][SIZE];
/* verifie si la valeur est valide */
int check_case(Grid grid, int row, int col, int n)
{
int i,j;
int mini_row = row - row % 3;
int mini_col = col - col % 3;
if(grid[row][col] == n)
return 1;
if(grid[row][col] != 0)
return 0;
for(i = 0; i < SIZE; i++)
if(grid[row][i] == n || grid[i][col] == n)
return 0;
for(i = mini_row; i < mini_row + 3; i++)
for(j = mini_col; j < mini_col + 3; j++)
if(grid[i][j] == n)
return 0;
return 1;
}
void grid_cpy(Grid dest, Grid src)
{
int i,j;
for(i = 0; i < SIZE; i++)
for(j = 0; j < SIZE; j++)
dest[i][j] = src[i][j];
}
/* resolution par backtracking */
void shaddan_solve(Grid grid, int row, int col, Grid sol)
{
if(row < SIZE)
{
int i;
for(i = 1; i <= SIZE; i++)
{
if(check_case(grid, row, col, i))
{
int tmp = grid[row][col];
grid[row][col] = i;
if(col != SIZE - 1)
shaddan_solve(grid, row, col + 1, sol);
else
shaddan_solve(grid, row + 1, 0, sol);
grid[row][col] = tmp; /* on remet l'ancienne valeur */
}
}
}
else
grid_cpy(sol, grid); /* on copie la solution (quand trouvée) avant
que l'ancienne valeur ne soit rétablie */
}
void shaddan_solve1(Grid grid)
{
shaddan_solve(grid, 0, 0, grid);
}
/* Pouet_forever ------------------------------------------------------------ */
enum {
M = 3,
NNN = M * M,
NxN = NNN * NNN
};
int isValid(int * grid, int n, int pos) {
int i, j;
int col, lin;
col = pos % NNN;
lin = pos / NNN;
/* Line, column */
for (i = 0; i < NNN; i++) {
if (grid[lin * NNN + i] == n ||
grid[i * N + col] == n)
return 0;
}
/* case */
col = (col / M) * M;
lin = (lin / M) * M;
for (i = 0; i < M; i++) {
for (j = 0; j < M; j++) {
if (grid[(lin + i) * N + (col + j)] == n)
return 0;
}
}
return 1;
}
int resolve(int * grid, int pos) {
int i, tmp;
if (pos >= NxN)
return 1;
if (grid[pos] != 0)
return resolve(grid, pos + 1);
for (i = 1; i <= NNN; i++) {
if (isValid(grid, i, pos)) {
grid[pos] = i;
tmp = resolve(grid, pos + 1);
if (tmp != 0)
return tmp;
grid[pos] = 0;
}
}
return 0;
}
int resolve1(int * grid)
{
resolve(grid, 0);
}
/* GurneyH ------------------------------------------------------------------ */
#define NN 9
typedef struct
{
int pos;
int n;
} cell;
cell cells[NN * NN];
int possibility[NN * NN][NN + 1];
int cmp(void const *p, void const *q)
{
return ((cell *)p)->n - ((cell *)q)->n;
}
void grid_display(int *g)
{
for(int i = 0; i < NN; i++)
{
for(int j = 0; j < NN; j++)
printf("%d", g[i * NN + j]);
puts("");
}
puts("");
}
int check_square(int *g, int row, int col, int v)
{
int ox = (col / 3) * 3;
int oy = (row / 3) * 3;
for(int i = oy; i < oy + 3; i++)
for(int j = ox; j < ox + 3; j++)
if(g[i * NN + j] == v)
return 0;
return 1;
}
int check_row_col(int *g, int row, int col, int v)
{
for(int i = 0; i < NN; i++)
if(g[i * NN + col] == v || g[row * NN + i] == v)
return 0;
return 1;
}
int check_cell(int *g, int pos, int v)
{
int col = pos % NN;
int row = pos / NN;
return check_row_col(g, row, col, v) && check_square(g, row, col, v);
}
int backtrack(int *g, int id)
{
int pos = cells[id].pos;
if(id == NN * NN)
return 1;
if(g[pos])
return backtrack(g, id + 1);
else
{
for(int k = 1; k <= NN; k++)
{
if(possibility[pos][k])
if(check_cell(g, pos, k))
{
g[pos] = k;
if(backtrack(g, id + 1))
return 1;
}
}
g[pos] = 0;
return 0;
}
}
int singleton_block(int *g)
{
int n_singletons = 0;
for(int i = 0; i < NN; i += 3)
for(int j = 0; j < NN; j += 3)
{
int pos = 0;
for(int k = 1; k <= NN; k++)
{
int count = 0;
for(int ii = i; ii < i + 3; ii++)
for(int jj = j; jj < j + 3; jj++)
{
if(!g[ii * NN + jj] && check_cell(g, ii * NN + jj, k))
{
count++;
pos = ii * NN + jj;
}
}
if(count == 1)
{
g[pos] = k;
n_singletons++;
}
}
}
return n_singletons;
}
int singleton_col(int *g)
{
int n_singletons = 0;
for(int col = 0; col < NN; col++)
{
int pos = 0;
for(int k = 1; k <= NN; k++)
{
int count = 0;
for(int row = 0; row < NN; row++)
{
if(!g[ row * NN + col])
{
if(check_cell(g, row * NN + col, k))
{
count++;
pos = row * NN + col;
}
}
}
if(count == 1)
{
g[pos] = k;
n_singletons++;
}
}
}
return n_singletons;
}
int singleton_row(int *g)
{
int n_singletons = 0;
for(int row = 0; row < NN; row++)
{
int pos = 0;
for(int k = 1; k <= NN; k++)
{
int count = 0;
for(int col = 0; col < NN; col++)
{
if(!g[ row * NN + col])
{
if(check_cell(g, row * NN + col, k))
{
count++;
pos = row * NN + col;
}
}
}
if(count == 1)
{
g[pos] = k;
n_singletons++;
}
}
}
return n_singletons;
}
void solve(int *g)
{
int find = 0;
do
{
find = singleton_row(g) + singleton_col(g) + singleton_block(g);
for(int i = 0; i < NN * NN; i++)
{
int n = 0;
int last = 0;
if(!g[i])
{
for(int k = 1; k <= NN; k++)
if(check_cell(g, i, k))
{
possibility[i][k] = 1;
last = k;
n++;
}
if(n == 1)
{
g[i] = last;
find = 1;
}
}
cells[i].pos = i;
cells[i].n = n;
}
}
while(find);
qsort(cells, NN * NN, sizeof *cells, cmp);
backtrack(g, 0);
}
/* Yoch --------------------------------------------------------------------- */
////////////////////////////////////////////////////////////
// Listes circulaires : définition et fonctions
////////////////////////////////////////////////////////////
typedef struct _node
{
struct _node* prev;
struct _node* next;
int i, j, b;
int nbValeursPossibles;
} CIRCL_LIST;
CIRCL_LIST* createRoot (void)
{
CIRCL_LIST* node = malloc(sizeof *node);
node->prev = node->next = node;
return node;
}
CIRCL_LIST* circular_list_append (CIRCL_LIST* root)
{
CIRCL_LIST* node = malloc(sizeof *node);
node->prev = root->prev;
node->next = root;
root->prev->next = node;
root->prev = node;
return node;
}
void deleteAll (CIRCL_LIST* root)
{
CIRCL_LIST *next;
for (CIRCL_LIST* iter = root->next; iter != root; iter = next)
{
next = iter->next;
free (iter);
}
free (root);
}
////////////////////////////////////////////////////////////
// Resolution Sudoku
////////////////////////////////////////////////////////////
// Variables globales pour la mémorisation
bool existeSurLigne[N_2][N_2];
bool existeSurColonne[N_2][N_2];
bool existeSurBloc[N_2][N_2];
////////////////////////////////////////////////////////////
// Backtracking "adaptatif" :
// décide dynamiquement la branche de l'arbre à explorer
////////////////////////////////////////////////////////////
bool estValide (int grille[N_2][N_2], CIRCL_LIST* root)
{
bool ret = false;
if (root == root->next) // la liste est vide
return true;
// cherche la case avec un nombre de valeurs possibles minimal
int min = N_2+1;
CIRCL_LIST* pos = NULL;
for (CIRCL_LIST* iter = root->next; iter != root && min != 0; iter = iter->next)
{
if (iter->nbValeursPossibles < min)
pos = iter, min = iter->nbValeursPossibles;
}
if (min == 0) return false; // si le nombre de valeurs possibles vaut 0, on stoppe
int i = pos->i, j = pos->j, b = pos->b;
// supprimme temporairement le noeud de la liste
pos->prev->next = pos->next;
pos->next->prev = pos->prev;
// Crée une liste de voisins de la case sélectionnée (même ligne/colonne/bloc)
CIRCL_LIST* voisins[2*(N_2-1)+(N-1)*(N-1)];
unsigned n = 0;
for (CIRCL_LIST* iter = root->next; iter != root; iter = iter->next)
if ( iter->i == i || iter->j == j || iter->b == b )
voisins[n++] = iter;
unsigned nb = 0;
for (int k=0; k < N_2 && nb != min; k++)
{
// si on peut placer k+start
if ( !existeSurLigne[i][k] && !existeSurColonne[j][k] && !existeSurBloc[b][k] )
{
// on actualise le champ 'nbValeursPossibles' dans la liste
for (CIRCL_LIST** it = voisins; it != voisins+n; it++)
if ( !existeSurLigne[(*it)->i][k] && !existeSurColonne[(*it)->j][k] && !existeSurBloc[(*it)->b][k] )
(*it)->nbValeursPossibles--;
// Ajoute k aux valeurs enregistrées
existeSurLigne[i][k] = existeSurColonne[j][k] = existeSurBloc[b][k] = true;
if ( (ret = estValide(grille, root)) )
{
grille[i][j] = k+start;
break;
}
// Supprime k des valeurs enregistrées
existeSurLigne[i][k] = existeSurColonne[j][k] = existeSurBloc[b][k] = false;
// on re-actualise le champ 'nbValeursPossibles' dans la liste
for (CIRCL_LIST** it = voisins; it != voisins+n; it++)
if ( !existeSurLigne[(*it)->i][k] && !existeSurColonne[(*it)->j][k] && !existeSurBloc[(*it)->b][k] )
(*it)->nbValeursPossibles++;
nb++;
}
}
// avant de quitter, on restaure le noeud dans la liste
pos->prev->next = pos;
pos->next->prev = pos;
return ret;
}
// compte (naïvement) le nombre de solutions possibles pour une case
int nb_possibles (int i, int j, int b)
{
int ret = 0;
for (int k=0; k < N_2; k++)
if ( !existeSurLigne[i][k] && !existeSurColonne[j][k] && !existeSurBloc[b][k] )
ret++;
return ret;
}
bool resolution (int grille[N_2][N_2])
{
// Initialise les tableaux
for (int i=0; i < N_2; i++)
for (int j=0; j < N_2; j++)
existeSurLigne[i][j] = existeSurColonne[i][j] = existeSurBloc[i][j] = false;
// Enregistre toutes les valeurs déjà présentes dans la grille
int k;
for (int i=0; i < N_2; i++)
for (int j=0; j < N_2; j++)
if ( (k = grille[i][j]) != 0)
existeSurLigne[i][k-start] = existeSurColonne[j][k-start] = existeSurBloc[N*(i/N)+(j/N)][k-start] = true;
// Crée une liste circulaire doublement chainée contenant toutes les cases vides
CIRCL_LIST *positions = createRoot(), *node = NULL;
for (int i=0; i < N_2; i++)
for (int j=0; j < N_2; j++)
if ( grille[i][j] == 0 )
{
node = circular_list_append ( positions );
node->i = i, node->j = j, node->b = N*(i/N)+(j/N);
node->nbValeursPossibles = nb_possibles(i, j, node->b);
}
// Appelle la fonction récursive estValide()
bool ret = estValide (grille, positions);
deleteAll (positions);
return ret;
}
void bench(char const *s, int (*f)(int [N_2][N_2]))
{
int grille[3][N_2][N_2] =
{
{
{0,0,0,0,0,0,0,0,0},
{0,0,0,0,0,3,0,8,5},
{0,0,1,0,2,0,0,0,0},
{0,0,0,5,0,7,0,0,0},
{0,0,4,0,0,0,1,0,0},
{0,9,0,0,0,0,0,0,0},
{5,0,0,0,0,0,0,7,3},
{0,0,2,0,1,0,0,0,0},
{0,0,0,0,4,0,0,0,9},
},
{
{9,0,0,1,0,0,0,0,5},
{0,0,5,0,9,0,2,0,1},
{8,0,0,0,4,0,0,0,0},
{0,0,0,0,8,0,0,0,0},
{0,0,0,7,0,0,0,0,0},
{0,0,0,0,2,6,0,0,9},
{2,0,0,3,0,0,0,0,6},
{0,0,0,2,0,0,9,0,0},
{0,0,1,9,0,4,5,7,0}
},
{
{0,0,0,0,0,0,0,3,1},
{6,0,0,0,2,0,0,0,0},
{0,0,0,0,7,0,0,0,0},
{0,5,0,1,0,8,0,0,0},
{2,0,0,0,0,0,6,0,0},
{0,0,0,3,0,0,0,7,0},
{0,0,0,0,4,0,2,0,0},
{0,3,0,5,0,0,0,0,0},
{7,0,0,0,0,0,0,0,0},
}
};
printf("%s\n", s);
for(int i = 0; i < 3; i++)
{
//affichage(grille[i]);
clock_t t1 = clock();
f(grille[i]);
clock_t t2 = clock();
//affichage(grille[i]);
printf("Grille %d : %.3fs\n\n", i, (double)(t2-t1)/CLOCKS_PER_SEC);
}
}
int main (void)
{
bench("Yoch", resolution);
bench("GurneyH", solve);
bench("Pouet", resolve1);
bench("shaddan", shaddan_solve1);
return 0;
}
J'obtiens bien sur des warnings:
- Pouet et moi utilisons des tableaux 1d.
- Yoch utilise le type bool
- la fonction solve de shaddan ne retourne rien.
Il faudrait qu'on se fixe une interface commune, pour faire un bench sérieux.
Résultats avec les 3 grilles du code de Yoch(sauf erreur...)
Elle met mon code par terre(9s), et passe pas mal si j'enlève le qsort(0.1s) -> Il faut bien réévaluer dynamiquement.
Elle passe bien aussi avec vos codes.
Il y a un truc que je ne comprends pas du tout : le code de Pouet Forever (si c'est bien celui-ci) n'est pas du tout optimisé, et il donne les meilleures perfs ! Il doit y avoir un truc qui cloche quelque part...
J'ai refait un bench pour la grille 0 ("Near worst case" - tiré de Wikipédia) avec le code de Pouet Forever, et voici le résultat :
#include <stdlib.h>
#include <stdio.h>
enum {
M = 3,
N = M * M,
NxN = N * N
};
void printGrid(int * grid) {
int i;
for (i = 0; i < NxN; i++) {
if (i != 0) {
if (i % N == 0)
putchar('\n');
else if (i % M == 0)
putchar(' ');
if (i % (N * M) == 0)
putchar('\n');
}
printf("%d ", grid[i]);
}
puts("");
puts("-----------");
}
int isValid(int * grid, int n, int pos) {
int i, j;
int col, lin;
col = pos % N;
lin = pos / N;
/* Line, column */
for (i = 0; i < N; i++) {
if (grid[lin * N + i] == n ||
grid[i * N + col] == n)
return 0;
}
/* case */
col = (col / M) * M;
lin = (lin / M) * M;
for (i = 0; i < M; i++) {
for (j = 0; j < M; j++) {
if (grid[(lin + i) * N + (col + j)] == n)
return 0;
}
}
return 1;
}
int resolve(int * grid, int pos) {
int i, tmp;
if (pos >= NxN)
return 1;
if (grid[pos] != 0)
return resolve(grid, pos + 1);
for (i = 1; i <= N; i++) {
if (isValid(grid, i, pos)) {
grid[pos] = i;
tmp = resolve(grid, pos + 1);
if (tmp != 0)
return tmp;
grid[pos] = 0;
}
}
return 0;
}
int main (void) {
int grid[NxN] = {0,0,0,0,0,0,0,0,0,
0,0,0,0,0,3,0,8,5,
0,0,1,0,2,0,0,0,0,
0,0,0,5,0,7,0,0,0,
0,0,4,0,0,0,1,0,0,
0,9,0,0,0,0,0,0,0,
5,0,0,0,0,0,0,7,3,
0,0,2,0,1,0,0,0,0,
0,0,0,0,4,0,0,0,9};
printGrid(grid);
resolve(grid, 0);
printGrid(grid);
return EXIT_SUCCESS;
}
Sinon, +1 pour le voeu d'avoir une interface commune. Je crois que ce n'est pas imposé pour donner une plus grande liberté de codage, mais c'est vrai que ça devient difficile de faire des benchs...
EDIT :
Aussi, pour bien se rendre compte que le problème du sudoku est NP-Complet, et vu que beaucoup de codes postés ici sont assez génériques, je suggère aux membres d'essayer de passer à la dimension supérieure (16x16), histoire de s'en convaincre...
Attention tout de même, ça fait 256 cases au total contre 81, et je pense que ça va prendre plusieurs heures de calcul en moyenne, voire pire dans certains cas. Il est possible d'utiliser des grilles relativement pleines, pour éviter de tomber dans ce genre d’excès.
C'est quoi ce benchmark qui consiste à tester la fonction qu'une seule fois?
yoch: 0.000
GurneyH: 0.000
Ah bah oui c'est très parlant là
Tu as raison.
Mais c'était surtout pour voir les cas pouvant prendre plusieurs secondes, et j'ai pondu ça rapidement, même pas certain que ce soit correct(voir la remarque de Yoch sur les perfs du code de Pouet).
Citation : Marc Mongenet
Citation : GurneyH
Bonjour, j'ai essayé defaire un bench des codes présentés pour le moment(hormis pour Marc dont le fonctionnement du code est un peu différent).
Ah? Pourtant c'est un backtracking de base.
J'ai dû mal comprendre ton code sur l'instant, tu ne t'arrêtes pas à la première grille trouvée, non?
edit:
Alors le bench est un peu biaisé totalement faux.
le code de Pouet ressort avec la grille d'origine, et le mien avec des grilles incomplètes...
Je regarde le problême.
C'est quoi ce benchmark qui consiste à tester la fonction qu'une seule fois?
yoch: 0.000
GurneyH: 0.000
Ah bah oui c'est très parlant là
L'ennui, c'est que pour faire un benchmark correct, il faudrait des tas de grilles (je dirais de l'ordre de quelques milliers), donc impensable de le faire a la main...
Ce qui serait possible, c'est d'utiliser un générateur automatique de sudokus (j'en ai un si vous voulez, mais pour que ce soit équitable il faudrait employer un logiciel tiers, reconnu et éprouvé), mais ca va demander un petit effort d'adaptation...
Ce genre de liste me parait convenir pour un bench un peu plus sérieux (1465 grilles qui sont donnés comme humainement très difficiles).
Pour les plus exigeants, je propose cette liste de 49151 ( ) sudokus minimaux (17 cases dévoilées), au format légèrement différent.
EDIT :
J'ai adapté mon main pour la seconde liste de sudokus et j'ai effectué un benchmark. Comme c'est un peu long, je termine le test après les 2000 premières grilles. Voici mes résultats :
....................2000 grilles en 46.349s
Ce qui donne en moyenne 0.023s par grille.
Avec la première liste, j'obtiens encore mieux (normal, ce sont des sudokus difficiles pour humains, mais représentant un arbre de recherche plus petit pour un backtracking) :
..............1466 grilles en 5.198s
Soit en moyenne 0.0035s par grille !
Voici le main, pour les intéressés :
#define SZBUF 100
int main (void)
{
FILE* fp = fopen("shorters_sudokus.txt", "r");
if (fp == NULL)
{
fprintf(stderr, "Impossible d'ouvrir le fichier");
exit(0);
}
int grille[N_2][N_2] = {{0}};
char buffer[SZBUF] = {0};
size_t elapsed = 0, counter = 0;
while ( counter < 2000 /*!feof(fp) */ )
{
// charge une grille
fgets(buffer, SZBUF, fp);
for (int i=0; i<N_2; i++)
{
for (int j=0; j<N_2; j++)
{
grille[i][j] = buffer[i*N_2+j] - '0';
}
}
//affichage(grille);
clock_t t1 = clock();
resolution (grille);
clock_t t2 = clock();
elapsed += (t2-t1);
counter++;
if (counter % 100 == 0) putchar('.');
//affichage(grille);
}
printf("%u grilles en %gs\n\n", counter, (double)elapsed/CLOCKS_PER_SEC);
fclose(fp);
return 0;
}
EDIT 2 :
Je viens de retrouver la grille invalide soumise par Pouet Forever. L'auteur signale bien que c'est une grille invalide que son programme a généré (et qui lui a bouffé 1439 secondes avec un code python ).
Je viens de faire un petit programme qui marche normalement (en tout case je ne l'ai essaier que sur une seul grille).
Pour le niveau je pense que c'est 1, car j’évolue la valeur de chaque case de la grille et je regarder dans la collone, ligne et region s'il ya'a qu'une seul solution je retourne dans la premier case sinon je continue .
Le code :
#include <stdio.h>
#include <stdlib.h>
int chercheDansLigne(char grille[][9], int ligne, int nbr);
int chercheDansCollone(char grille[][9], int collone, int nbr);
int chercheDansRegion(char grille[][9], int X, int Y, int nbr);
int main()
{
char grille[9][9];
int i, j, k, entre, nbrT = 0, nbr = 0;
for(i = 0; i < 9; i++)
scanf("%1c%1c%1c%1c%1c%1c%1c%1c%1c%1c", &grille[i][0], &grille[i][1], &grille[i][2], &grille[i][3], &grille[i][4],
&grille[i][5], &grille[i][6], &grille[i][7], &grille[i][8], &entre);
for(i = 0; i < 9; i++)
for(j = 0; j < 9; j++)
grille[i][j] -= grille[i][j] == ' ' ? 32 : '0';
for(i = 0; i < 9; i++)
{
for(j = 0; j < 9; j++)
{
nbrT = 0, nbr = 0;
if(grille[i][j] == 0)
{
for(k = 0; k < 10; k++)
{
if(!chercheDansLigne(grille, i, k) && !chercheDansCollone(grille, j, k) && !chercheDansRegion(grille, i, j , k))
{
nbrT++;
nbr = k;
}
}
if(nbrT == 1)
{
grille[i][j] = nbr;
i = 0;
j = 0;
}
}
}
}
for(i = 0; i < 9; i++){
for(j = 0; j < 9; j++)
printf("%d ",grille[i][j]);
printf("\n");}
return 0;
}
int chercheDansLigne(char grille[][9], int ligne, int nbr)
{
int i;
for(i = 0; i < 9; i++)
if(grille[ligne][i] == nbr)
return 1;
return 0;
}
int chercheDansCollone(char grille[][9], int collone, int nbr)
{
int i;
for(i = 0; i < 9; i++)
if(grille[i][collone] == nbr)
return 1;
return 0;
}
int chercheDansRegion(char grille[][9], int X, int Y, int nbr)
{
int i, j;
for(i = ((int)floor(X / 3) * 3); i < ((int)floor(X / 3) * 3) + 3; i++)
for(j = ((int)floor(Y / 3) * 3); j < ((int)floor(Y / 3) * 3) + 3; j++)
if(grille[i][j] == nbr)
return 1;
return 0;
}
Sinon, j'aimerai avoir quellque commentaire pour l'améliorer.
Ah, ouais, c'est sur ce site que je l'avais chopée.
J'ai dû manger le mot 'impossible'.
Voilà le résultat de mon bench sur les 1465 grilles :
1465 grids solved in 565.23s
average : 0.56s
#include <ctype.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
enum {
M = 3,
N = M * M,
NxN = N * N
};
void printGrid(int * grid) {
int i;
for (i = 0; i < NxN; i++) {
if (i != 0) {
if (i % N == 0)
putchar('\n');
else if (i % M == 0)
putchar(' ');
if (i % (N * M) == 0)
putchar('\n');
}
printf("%d ", grid[i]);
}
puts("");
puts("-----------");
}
int isValid(int * grid, int n, int pos) {
int i, j;
int col, lin;
col = pos % N;
lin = pos / N;
/* Line, column */
for (i = 0; i < N; i++) {
if (grid[lin * N + i] == n ||
grid[i * N + col] == n)
return 0;
}
/* case */
col = (col / M) * M;
lin = (lin / M) * M;
for (i = 0; i < M; i++) {
for (j = 0; j < M; j++) {
if (grid[(lin + i) * N + (col + j)] == n)
return 0;
}
}
return 1;
}
int resolve(int * grid, int pos) {
int i, tmp;
if (pos >= NxN)
return 1;
if (grid[pos] != 0)
return resolve(grid, pos + 1);
for (i = 1; i <= N; i++) {
if (isValid(grid, i, pos)) {
grid[pos] = i;
tmp = resolve(grid, pos + 1);
if (tmp != 0)
return tmp;
grid[pos] = 0;
}
}
return 0;
}
int main (void) {
FILE * f;
int grid[NxN] = { 0 };
size_t t1, t2, tmp, elapsed, average;
int i, cnt;
f = fopen("sudoku1.txt", "r");
if (f == NULL) {
perror("fopen");
return EXIT_FAILURE;
}
cnt = 0;
elapsed = average = 0;
while (!feof(f)) {
for (i = 0; i < NxN; i++) {
int c = fgetc(f);
if (c == '\n') {
i--;
continue;
}
else if (c == EOF)
goto end;
if (c == '.')
grid[i] = 0;
else if (isdigit(c))
grid[i] = c - '0';
}
t1 = clock();
resolve(grid, 0);
t2 = clock();
tmp = t2 - t1;
average = (average + tmp) / 2;
elapsed += tmp;
cnt++;
}
end:
printf("%d grids solved in %.2fs\n", cnt, (double) elapsed / CLOCKS_PER_SEC);
printf("average : %.2fs\n", (double) average / CLOCKS_PER_SEC);
fclose(f);
return EXIT_SUCCESS;
}
Ton code a résolu 1466 grilles, où est la dernière ?
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
🍊 - Étudiant - Codeur en C | Zeste de Savoir apprenez avec une communauté | Articles - ♡ Copying is an act of love.