bonjour pour un projet à la fac je dois faire un solveur de sudoku. Pour le défi j'ai essayé de l'optimiser et de le faire marcher pour des grille de sudoku de taille n*n. L'optimisation marche, la taille n*n marche, mais quand il sagit de faire mercher la taille n*n avec l'optimisation le programme mouline indéfiniment. J'espère que quelqu'un pourra m'apporter des solution
voila le programme qui ne marche pas
#include<iostream> #include<vector> #include<cmath> #include<utility> #include <algorithm> #define N 16 using namespace std; vector<pair<int,pair<int,int> > > V; int T = N*N; int n = sqrt(N); int grille[N][N]={{3,1,8,9,2,5,10,13,4,6,11,14,7,12,15,16}, {2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {5,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {1,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {7,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0}, {9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {11,0,0,0,0,0,0,0,0,0,0,0,12,0,0,3}, {12,0,13,0,0,0,0,0,0,0,0,0,0,0,0,0}, {13,0,0,0,0,0,7,0,0,0,0,0,0,0,0,0}, {14,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {15,0,12,0,0,14,0,0,0,0,0,0,5,0,0,0}, {16,0,0,0,8,0,0,0,0,0,0,0,0,0,0,0}} ;
bool danscolonne(int colonne, int nombre ){ //regarde si le nombre donné est dans la colonne for(int ligne=0; ligne<N; ligne++){ if (grille[ligne][colonne] == nombre){ return true;} } return false; }
bool dansligne(int ligne, int nombre ){ // regarde si le nombre donné est dans la ligne for(int colonne=0; colonne<N; colonne++){ if (grille[ligne][colonne] == nombre){ return true;} } return false; }
bool dansregion(int colonne, int ligne, int nombre){ int c = 0; int l = 0; int COL= colonne- colonne%n; int LIG= ligne - ligne%n; for(int i=0; i<N; i++){ c=i%n; //reste l=i/n; //quotien if(grille[LIG+l][COL+c]==nombre){ return true; } } return false; }
bool PlacePossible(int ligne, int colonne, int nombre){ //regarde si le nombre peut être dans la case donné return !danscolonne(colonne, nombre) && !dansligne(ligne, nombre) && !dansregion(colonne,ligne,nombre); }
bool àremplir(int &colonne, int &ligne){ //regarde si la grille est finie for(int i=0; i<T; i++){ colonne = V[i].second.first; ligne = V[i].second.second; if (grille[ligne][colonne] == 0){ return true; } } return false; }
void grillecomplete(){ for (int ligne = 0; ligne < N; ligne++){ for (int colonne = 0; colonne < N; colonne++){ bool b = false; for (int k = n; k < N; k = k + n){ if(colonne == k){ cout << " | "; cout << grille[ligne][colonne] << " "; b = true; } } if(!b){ cout << grille[ligne][colonne] << " "; } } cout << endl; for(int l = n-1; l < N-1; l = l + n){ if(ligne == l){ for(int i=0; i<N; i++){ cout << "---"; } cout << endl; } }
} }
bool SolverSudoku(){ //bloc principal récursif int ligne,colonne; if (!àremplir(colonne,ligne)){ return true;} for (int nombre=1; nombre<N+1; nombre++){ // parcourt linéairement la grille if (PlacePossible(ligne ,colonne , nombre)){ grille[ligne][colonne]= nombre; if (SolverSudoku()){ return true;} grille[ligne][colonne] = 0; // si cela ne marche pas on recommence } } return false; }
bool tri(const pair<int,pair<int,int> >& a,const pair<int,pair<int,int> >& b){ // fonction tri croissant d'un vecteur return a.first<b.first;
}
int main(){ for(int colonne=0;colonne<N;colonne++){ for(int ligne=0;ligne<N;ligne++){ int Nbr=0; for(int nombre=1;nombre<N+1;nombre++){ if (PlacePossible(ligne,colonne,nombre)){ Nbr+=1;} // compte le nombre de chiffres que l'on peut mettre dans la case donné } pair <int,int> a (colonne,ligne); pair <int,pair<int,int> > b (Nbr , a); V.push_back(b) ; } } sort(V.begin(),V.end(),tri);// création d'un vecteur qui ordonne les cases ayant le moins de chiffres possibles à celles qui en ont le plus if (SolverSudoku()){ grillecomplete(); } else{ cout << "Sudoku insolvable"; } }
Comme l'a signalé PierrotLeFou, la première chose a faire est d'écrire du C++ correcte, même si tu n'as pas de classes: - Vires moi cette directive "using namespace std", son utilisation est considéré comme une mauvaise pratique (une recherche sur le forum te dira pourquoi). - Utilise les conteneurs de la librairie standard, en l'occurrence std::vector (puisque le sudoku est de taille n, inconnue selon ton énoncé), ca te permettra de virer ces horribles #define et variables globales.
Tu parles d'optimisation, l'une des technique qui revient souvent sur le forum, est de linéariser tes données au lieu d'utiliser un tableau 2D, à ta charge d'écrire les fonctions utilitaire ou classe histoire de le manipuler plus facilement.
Ton C++ ressemble plutôt à du C. Ton tableau 2D devrait plutôt être un std::array<std::array<int, N>, N>
Peux-tu expliquer ce que tu entends par optimisation?
Tu dis que tu peux résoudresans optimisation. Ça veut dire quoi?
Est-ce que ta fonction dansRegion fonctionne bien?
Selon moi, tu ne testes qu'une ligne du carré, pas les n * n cases.
Ta grille de base semble correcte, mais tu aurais intérêt à écrire une fonction de validation.
Pour chaque case, tu sauves la valeur et tu places 0.
Tu vérifie si la valeur sauvée est dans la ligne, la colonne ou la région.
Si c'est le cas, ta grille de départ n'est pas valide.
edit:
dans solverSudoku, tu ne modifies pas la ligne ou la colonne. Où le fais-tu?
Ils ne sont même pas initialisés.
Tu dois les passer en paramètre. Tu commences avec (0, 0)
Tu fais l'appel récursif avec colonne+1 et tu vérifies au début de la fonction que colonne < N
sinon, tu mets colonne à 0 et tu augmentes ligne et tu testes si c'est < N, sinon tu as réussi.
- Edité par PierrotLeFou 10 décembre 2023 à 4:31:36
L'optimisation consiste juste à classer les positions de la grille par le nombre de nombre que l'on peut mettre dedans. Comme ca vue que le programme est récursif il y aura au pire moins de calcul a faire. En gros, comme mon programme test (comme une brute) si on peut mettre un nombre a une position particulière alors c'est mieux de cibler les positions où il y a moins de nombre possible donc moins d'erreur possible.
Par résoudre sans optimisation ça veut dire que j'ai un programme qui tourne qui arrive à résoudre des sudoku taille 4x4. A savoir celui là :
#include<iostream> #include<cmath> #define N 16 using namespace std;
int n = sqrt(N); int grille[N][N]={{3,1,8,9,2,5,10,13,4,6,11,14,7,12,15,16}, {2,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {5,4,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {6,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {4,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {1,8,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {7,0,0,0,3,0,0,0,0,0,0,0,0,0,0,0}, {9,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {8,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {10,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {11,0,0,0,0,0,0,0,0,0,0,0,12,0,0,3}, {12,0,13,0,0,0,0,0,0,0,0,0,0,0,0,0}, {13,0,0,0,0,0,7,0,0,0,0,0,0,0,0,0}, {14,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {15,0,12,0,0,14,0,0,0,0,0,0,5,0,0,0}, {16,0,0,0,8,0,0,0,0,0,0,0,0,0,0,0}}
;
bool danscolonne(int colonne, int nombre ){ //regarde si le nombre donné est dans la colonne for(int ligne=0; ligne<N; ligne++){ if (grille[ligne][colonne] == nombre){ return true;} } return false; }
bool dansligne(int ligne, int nombre ){ // regarde si le nombre donné est dans la ligne for(int colonne=0; colonne<N; colonne++){ if (grille[ligne][colonne] == nombre){ return true;} } return false; }
bool dansregion(int colonne, int ligne, int nombre){ int c = 0; int l = 0; int COL= colonne- colonne%n; int LIG= ligne - ligne%n; for(int i=0; i<N; i++){ c=i%n; //reste l=i/n; //quotien if(grille[LIG+l][COL+c]==nombre){ return true; } } return false; }
bool PlacePossible(int ligne, int colonne, int nombre){ //regarde si le nombre peut être dans la case donné return !danscolonne(colonne, nombre) && !dansligne(ligne, nombre) && !dansregion(colonne,ligne,nombre); }
bool aremplir(int &colonne, int &ligne){ //regarde si la grille est finie for(colonne=0; colonne<N; colonne++){ for(ligne=0; ligne<N; ligne++){ if (grille[ligne][colonne] == 0){ return true; } } } return false; }
void grillecomplete(){ for (int ligne = 0; ligne < N; ligne++){ for (int colonne = 0; colonne < N; colonne++){ bool b = false; for (int k = n; k < N; k = k + n){ if(colonne == k){ cout << " | "; cout << grille[ligne][colonne] << " "; b = true; } } if(!b){ cout << grille[ligne][colonne] << " "; } } cout << endl; for(int l = n-1; l < N-1; l = l + n){ if(ligne == l){ for(int i=0; i<N; i++){ cout << "---"; } cout << endl; } }
} }
bool SolverSudoku(){ //bloc principal récursif int ligne,colonne; if (!aremplir(colonne,ligne)){ return true; } for (int nombre=1; nombre<N+1; nombre++){ // parcourt linéairement la grille if (PlacePossible(ligne ,colonne , nombre)){ grille[ligne][colonne]= nombre; if (SolverSudoku()){ return true;} grille[ligne][colonne] = 0; // si cela ne marche pas on recommence } } return false; }
Pour moi dans région marche bien.Pour ce que tu dis sur la ligne, normalement c'est à ça que sert les variable c et l. Elles marche un peut comme les vielles machine à écrire un fois que t'as taper le bord tu revient à la ligne.
La grille est bien correct et normalement la parti récursive marche comme un vérificateur de possibilité, dans le snes ou un fois avoir essayé toute sles grille possible, ça renvoie que ca marche pas.
La modification de valeur de la grille se fais dans la boucle récursive
bool SolverSudoku(){ //bloc principal récursif int ligne,colonne; if (!àremplir(colonne,ligne)){ return true;} for (int nombre=1; nombre<N+1; nombre++){ // parcourt linéairement la grille if (PlacePossible(ligne ,colonne , nombre)){ grille[ligne][colonne]= nombre; if (SolverSudoku()){ return true;} grille[ligne][colonne] = 0; // si cela ne marche pas on recommence } } return false; }
à la ligne 7 du bout ci dessus t'as grille[ligne][colonne]= nombre qui en gros va changer les valeur en lieu et place des variables ligne et colonne, ce qui va le modifier que dans la boucle récursive et si à la fin le programme remarque que c'est pas possible avec cette position la grille va retourner au tout début et être "écrasé".
Et en fait c'est aremplir qui décide que case on modifie.
Pour aussi répondre à michelbillaud voici le programme de en 9x9 :
#include<iostream> using namespace std;
int grille[9][9]={{7,0,9,4,0,0,0,6,8}, {0,0,0,0,2,0,0,4,0}, {0,0,3,0,0,0,0,0,0}, {0,6,0,0,0,0,0,0,0}, {0,0,0,0,0,1,5,0,0}, {8,0,4,2,0,0,0,0,9}, {0,3,0,7,0,0,0,0,0}, {0,2,0,0,0,0,0,0,6}, {6,0,7,0,5,0,9,0,0}};
bool danscolonne(int colonne, int nombre ){ //regarde si le nombre donné est dans la colonne for(int ligne=0; ligne<9; ligne++){ if (grille[ligne][colonne] == nombre){ return true;} } return false; }
bool dansligne(int ligne, int nombre ){ // regarde si le nombre donné est dans la ligne for(int colonne=0; colonne<9; colonne++){ if (grille[ligne][colonne] == nombre){ return true;} } return false; }
bool dansregion(int colonne, int ligne, int nombre){ int c = 0; int l = 0; int COL= colonne- colonne%3; int LIG= ligne - ligne%3; for(int i=0; i<9; i++){ c=i%3; l=i/3; if(grille[LIG+l][COL+c]==nombre){ return true; } } return false; }
bool PlacePossible(int ligne, int colonne, int nombre){ //regarde si le nombre peut être dans la case donné return !danscolonne(colonne, nombre) && !dansligne(ligne, nombre) && !dansregion(colonne,ligne,nombre); }
bool àremplir(int &colonne, int &ligne){ //regarde si la grille est finie for(colonne=0; colonne<9; colonne++){ for(ligne=0; ligne<9; ligne++){ if (grille[ligne][colonne] == 0){ return true; } } } return false; }
void grillecomplete(){ // affichage de la grille for (int ligne = 0; ligne < 9; ligne++){ for (int colonne = 0; colonne < 9; colonne++){ if(colonne == 3 || colonne == 6) cout << " | "; cout << grille[ligne][colonne] <<" "; } if(ligne == 2 || ligne == 5){ cout << endl; for(int i = 0; i<9; i++) cout << "---"; } cout << endl; } }
bool SolverSudoku(){ //bloc principal récursif int ligne,colonne; if (!àremplir(colonne,ligne)){ return true; } grillecomplete(); for (int nombre=1; nombre<10; nombre++){ // parcourt linéairement la grille if (PlacePossible(ligne ,colonne , nombre)){ grille[ligne][colonne]= nombre; if (SolverSudoku()){ return true;} grille[ligne][colonne] = 0; // si cela ne marche pas on recommence } } return false; }
int main(){ if (SolverSudoku()== true){ grillecomplete();} else{ cout << "Sudoku insolvable"; } }
Merci d'éditer vos messages pour y insérer votre code avec le bouton code </> de la barre d'outil du forum.
Merci de colorer votre code à l'aide du bouton Code </>
Les forums d'Openclassrooms disposent d'une fonctionnalité permettant de colorer et mettre en forme les codes source afin de les rendre plus lisibles et faciles à manipuler par les intervenants. Pour cela, il faut utiliser le bouton </> de l'éditeur, choisir un des langages proposés et coller votre code dans la zone prévue. Si vous utilisez l'éditeur de messages en mode Markdown, il faut utiliser les balises <pre class="brush: php;">Votre code ici</pre>.
Merci de modifier votre message d'origine en fonction.
> L'optimisation consiste juste à classer les positions de la grille par le nombre de nombre que l'on peut mettre dedans. Comme ca vue que le programme est récursif il y aura au pire moins de calcul a faire. En gros, comme mon programme test (comme une brute) si on peut mettre un nombre a une position particulière alors c'est mieux de cibler les positions où il y a moins de nombre possible donc moins d'erreur possible.
En matière d'optimisation, il faut se méfier parce que ce qu'on trouve "intuitif" est rarement vrai, quand on se donne la peine de faire des mesures pour vérifier que c'est effectivement le cas.
Par exemple, si on remplit "bêtement", ligne par ligne, il se trouve qu'on crée rapidement des contraintes sur les premières lignes, puis les blocs du haut, ce qui de fait réduit rapidement les possibilités en dessous. Si on veut prendre les cases dans l'ordre du nombre de possibilités qui restent dedans, pourquoi pas, mais il y a un coût supplémentaires pour, à chaque étape, trouver une des cases qui en a le moins. Est-ce que c'est plus efficace, en temps de calcul final ? On peut penser que oui mais on peut aussi penser le contraire, donc c'est à prouver... et pour ça, il faut écrire les deux programmes, et mesurer sur un nombre conséquent d'exemples.
- Edité par michelbillaud 13 décembre 2023 à 17:43:56
Comme l'a dit Deedolith, une façon d'optimiser est de linéariser le tableau (de longueur N*N).
On peut associer à chaque position un tuple qui sera évalué au départ, et qui donne pour chaque position, la ligne, la colonne, et le carré ou elle se trouve.
Ça évite déjà beaucoup de calculs.
Surtout que tu gardes tes variables en global. Je ne suis pas trop d'accord avec ça. L'alternative serait de tout garder dans une structure et la passer en référence.
Une autre chose qui coute cher est le balayage des lignes, colonnes et carrés pour savoir si le symbole / chiffre s'y trouve.
Si on pouvait associer à chaque position 3 indices dans un vecteur de flags et si on ajoutait le "symbole" ou sa valeur, on pourrait vérifier d'un seul coup si le symbole est dans la ligne / colonne / carré.
(avec 3 tests seulement)
Par exemple, pour un carré 9 x 9 avec 9 symboles:
ligne 0 en position 0
ligne 1 en position 9 (pour garder 9 places)
etc.
En général pour une grille N x N:
ligne k (0 < k < N) en position k*N, et on ajoute l'indice du symbole.
Colonne k en position N*N + k*N + indice
carré k: en position 2*N*N + k*N + indice
Pour chaque position / symbole, on ira chercher 3 indices et 3 flags pour tester.
Si ça marche, on devra cependant allumer ces 3 flags.
Si ça ne marche pas en retour de la récursivité, on devra effacer ces 3 flags.
Ce tableau de flags pourrait être un std::vector<bool> ou std::array<bool, 3*N*N> si c'est en fixe.
edit: J'ai codé ma suggestion, mais en remplaçant le tuple par un array de 3 positions. Le tableau indices sera initialisé une seule fois au début du code. Le calcul est plus compliqué que je pensais pour les carrés. Je donne un exemple arbitraire de test et d'assignation des flags. Même s'il y a beaucoup de calcul d'indices, je crois que ce serait plus rapide que les balayages.
-
#include <iostream>
#include <vector>
#include <array>
#include <cmath>
enum {LIGNE, COLONNE, CARRE, TOUS};
int main(void) {
int N {9}; // Doit être un carré parfait.
int n = sqrt(N); // Dimension des petits carr és.
int B = N*N; // Base de décalage pour les colonnes et les carrés.
std::vector<std::array<int, TOUS>> indices (N*N);
std::vector<bool> flags (TOUS*N*N, false);
for(int position {0}; position < N*N; position++) {
indices[position][LIGNE] = position / N * N; // Pour la ligne.
indices[position][COLONNE] = B + position % N * N; // Pour la colonne.
indices[position][CARRE] = 2 *B + (position / (n*N) * n + position % N / n) * N; // Pour le carré. }
En linéarisant, la correspondance entre la position (dans le tableau de 81 cases dans le case de 9x9) et les coordonnées est simple
position = 9 * ligne + colonne
et inversement :
colonne = position modulo 9
ligne = position / 9
jusque là tout va bien. Maintenant pour parcourir
la même ligne : on tronque la position au multiple de 9 inférieur, ça nous donne la position du début de ligne, et on ajoute k entre 0 et 8
la même colonne : le numéro de colonne (= position modulo 9) , en ajoutant 9*k (k entre 0 et 8)
le même bloc : on trouve la position du coin, et on lui ajoute i+9*j, avec i et j entre 0 et 2. Mais pour ça faut le coin, qui a pour coordonnées les numéro de ligne et de colonne tronqués au multiple de 3. Je vous laisse les calculs, en exercice
PS : pour tronquer a au multiple de b inférieur, en C (et avec des nombres positifs), c'est a - ( a % b ). Pas compliqué.
Dans le temps, j'avais fait ce genre de truc mais en C, avec une fonction récurrente
Je ne sais si ça peut t'aider:
/* Programme de resolution de grilles de sudoku par backtracking */
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#define VIDE 0
#define TRUE 1
#define FALSE 0
int grille[81];
int compteur_noeuds;
void lire_grille(void);
void afficher_grille(void);
int constraintes_OK(int);
void backtrack(int);
int main()
{
lire_grille();
system("cls");
printf("\nGrille de depart:\n");
afficher_grille();
backtrack(0);
printf("%d noeuds cherches\nAppuyer sur une touche ...", compteur_noeuds);
_getche();
return 0;
}
/* Saisie de la grille. Les caracteres autres que . ou 0 à 9 sont ignores. */
void lire_grille()
{
int k = 0;
char c;
printf("\n********************** SUDOKU 9x9 *****************************\n\n");
printf("Entrer les valeurs sous la forme suivante (point=case inconnue) :\n");
printf("53..7....\n");
printf("6..195...\n");
printf("etc ..\n\n");
while (k < 81) {
c = getchar();
if (c >= '1' && c <= '9')
grille[k++] = c-'0';
else if (c == '.')
grille[k++] = VIDE;
else if (c == EOF) {
fprintf(stderr, "Lecture de la grille : mauvais format\n");
exit(1);
}
}
printf("\n");
}
/* Affichage de la grille courante */
void afficher_grille()
{
int c, l, k;
for (l = 0; l < 9; l++) {
for (c = 0; c < 9; c++) {
k = l*9+c;
if (grille[k] == VIDE)
printf(".");
else
printf("%c", grille[k]+'0');
printf(" ");
}
printf("\n");
}
printf("\n");
}
/* Verification des contraintes qui font intervenir la case i */
int constraintes_OK(int i)
{
int l = i / 9;
int c = i % 9;
int lb = l / 3;
int lr = l % 3;
int cb = c / 3;
int cr = c % 3;
int l2, c2, lr2, cr2;
/* verifier la colonne contenant la case i */
for (l2 = 0; l2 < 9; l2++)
if (l2 != l && grille[l2*9+c] == grille[i])
return FALSE;
/* verifier la ligne contenant la case i */
for (c2 = 0; c2 < 9; c2++)
if (c2 != c && grille[l*9+c2] == grille[i])
return FALSE;
/* verifier la region (carre 3x3) contenant la case i */
for (lr2 = 0; lr2 < 3; lr2++)
for (cr2 = 0; cr2 < 3; cr2++)
if ((lr2 != lr || cr2 != cr) && grille[(lb*3+lr2)*9+(cb*3+cr2)] == grille[i])
return FALSE;
return TRUE;
}
/* resolution par backtracking, en supposant que toutes les cases
d'indices j<i ont deja ete remplies */
void backtrack(int i)
{
/* afficher la solution */
if (i == 81) {
printf("Trouve !\n");
afficher_grille();
return;
}
/* case deja remplie, on passe a la suivante*/
if (grille[i] != VIDE) {
backtrack(i+1);
return;
}
/* Case vide : verification des contraintes*/
compteur_noeuds++;
for (grille[i] = 1; grille[i] <= 9; grille[i]++)
if (constraintes_OK(i))
backtrack(i+1);
/* laisser la grille dans l'etat ou on l'a trouvee en entrant */
grille[i] = VIDE;
}
J'ai retrouvé une version itérative que j'avais écrite en 2021.
La résolution se fait là dedans (résolution.c)
#include <stdio.h>
#include "resolution.h"
#include "contraintes.h"
bool resoudre(int grille[81], int solution[81])
{
enum { CALL, EXIT, FAIL, REDO, CHECK } etat = CALL;
for (int p = 0; p < 81; p ++) {
solution[p] = grille[p];
}
int position = 0;
for(;;) {
if (position < 0) {
return 0;
}
if (position == 81) {
return 1;
}
switch (etat) {
case CALL:
if (grille[position] == 0) {
solution[position] = 1;
etat = CHECK;
} else
etat = EXIT;
break;
case CHECK:
etat = incompatibilite(ncl[position], solution)
|| incompatibilite(ncc[position], solution)
|| incompatibilite(ncb[position], solution) ? REDO : EXIT;
break;
case EXIT:
position ++;
etat = CALL;
break;
case FAIL:
position --;
etat = REDO;
break;
case REDO:
if (grille[position] == 0) {
solution[position]++;
if (solution[position] <= 9) {
etat = CHECK;
} else {
solution[position] = 0;
etat = FAIL;
}
} else {
etat = FAIL;
}
break;
}
}
}
Ca s'appuie sur une structure de données qui mémorise les incompatibilités. De mémoire, ncl, ncc et ncb, ça veut dire non-compatible par ligne, colonne ou bloc.
contraintes.h
ifndef CONTRAINTES_H
#define CONTRAINTES_H
typedef int CONTRAINTE[9];
//
extern CONTRAINTE contrainte[27];
extern int ncl[81], ncc[81], ncb[81];
void calculer_contraintes();
int incompatibilite(int nc, int grille[81]);
#endif
contraintes.c
#include "contraintes.h"
#include <assert.h>
// yes, we use global variables
CONTRAINTE contrainte[27];
int ncl[81], ncc[81], ncb[81];
void calculer_contraintes()
{
/*
construction de la table des contraintes
une contrainte est une table de 9 positions
qui représente une ligne, une colonne ou un bloc.
ncl[p] = numero de la contrainte de ligne de la position p
ncc[p], ncb[p] idem pour colonne ou bloc
*/
int nc = 0;
/* contraintes par ligne */
for (int l=0; l<9; l++) {
for(int c=0; c<9; c++) {
int p= 9*l + c;
assert(p >= 0);
assert(p < 81);
contrainte[nc][c] = p;
ncl[p] = nc;
}
nc++;
}
/* contrainte par colonne */
for(int c=0; c<9; c++) {
for (int l=0; l<9; l++) {
int p = 9*l + c;
assert(p >= 0);
assert(p < 81);
contrainte[nc][l] = p;
ncc[p] = nc;
}
nc++;
}
/* contrainte par bloc */
for (int bl=0; bl<3; bl++) {
for (int bc=0; bc<3; bc++) {
/* bloc de coin 3*bl , 3*bc */
for (int l=0; l<3; l++) {
for (int c=0; c<3; c++) {
int p = 9*(3*bl+l) + (3*bc+c);
assert(p >= 0);
assert(p < 81);
contrainte[nc][3*l+c] = p;
ncb[p] = nc;
}
}
nc++;
}
}
}
/*
teste si il y a une incompatibilité dans la grille par rapport
à la contrainte numéro nc
*/
int incompatibilite(int nc, int grille[81])
{
int marque[10];
for (int i=1; i<10; i++)
marque[i] = 0;
for (int i=0; i<9; i++) {
int j = grille[contrainte[nc][i]];
if (j == 0)
continue;
if (marque[j]++) {
/* une autre case de la grille a la même valeur */
return 1;
}
}
return 0;
}
Est-ce qu'il y a une règle ou une formule qui m'indiquerait le temps relatif d'exécution en foncion de la dimension de la grille?
Je parle de la complexité temporelle.
Je me doute que ça dépend également des contraintes qui sont dans la grille.
Supposons des grilles vides sans contraintes.
J'essaie d'écrire une version itérative en C++ avec mon truc des flags.
Pour une grille 16x16 sans contraintes ou la grille de ThomasMejean3, ça va assez vite.
Mais avec une grille 25x25, ça prend beaucoup de temps.
Je n'affiche rien. Je me contente de valider au début et à la fin.
- Edité par PierrotLeFou 17 décembre 2023 à 16:06:02
Le Tout est souvent plus grand que la somme de ses parties.
solveur de sudoku
× 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.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.