Partage
  • Partager sur Facebook
  • Partager sur Twitter

solveur de sudoku

    7 décembre 2023 à 19:35:05

    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";
    }
    }







    • Partager sur Facebook
    • Partager sur Twitter
      10 décembre 2023 à 1:58:23

      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

      • Partager sur Facebook
      • Partager sur Twitter

      Le Tout est souvent plus grand que la somme de ses parties.

        11 décembre 2023 à 10:44:07

        Hello,

        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.

        • Partager sur Facebook
        • Partager sur Twitter
          11 décembre 2023 à 14:48:54

          Bonjour

          il y a fort longtemps il y avait eu un échange très intéressant sur les grilles de sudoku

          et notamment un programme réalisé avec l'algorithme DLX sur une grille de 25x25 le temps d'exécution est assez bluffant

          voir là

          https://openclassrooms.com/forum/sujet/fait-defis-3-des-sudokus-en-folie-29452?page=3

          te reste plus qu'à mettre tout ça en vrai C++

          • Partager sur Facebook
          • Partager sur Twitter
            11 décembre 2023 à 17:18:05

            > bonjour pour un projet à la fac je dois faire un solveur de sudoku. Pour le défi j'ai essayé de l'optimiser

            Et pour le défi "faire un solveur de sudoku 9x9 qui marche", tu en es où ?

            • Partager sur Facebook
            • Partager sur Twitter
              11 décembre 2023 à 17:35:55

              Silence radio ... le PO s'est perdu dans les méandres de son algo.
              • Partager sur Facebook
              • Partager sur Twitter

              Le Tout est souvent plus grand que la somme de ses parties.

                13 décembre 2023 à 16:29:13

                PierrotLeFou a écrit:

                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;
                }



                int main(){

                if (SolverSudoku()== true){
                grillecomplete();
                }
                else{
                cout << "Sudoku insolvable";
                }
                }

                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";
                }
                }





                Et merci beaucoup à tous de m'aider :)

                • Partager sur Facebook
                • Partager sur Twitter
                  13 décembre 2023 à 16:49:01

                  @ThomasMejean3 Bonjour, je retire votre dernier message des spams, si cela se reproduit vous pouvez poster dans ce sujet Si votre message est considéré comme spam

                  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.

                  La modération.

                  -
                  Edité par AbcAbc6 13 décembre 2023 à 16:49:28

                  • Partager sur Facebook
                  • Partager sur Twitter
                    13 décembre 2023 à 16:56:08 - Message modéré pour le motif suivant : Doublon


                      13 décembre 2023 à 17:39:55

                      > 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

                      • Partager sur Facebook
                      • Partager sur Twitter
                        14 décembre 2023 à 1:16:38

                        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é.
                            }


                            // Exemple arbitraire.


                            int position = 63;


                            int chiffre = 3;


                            if( ! (flags[indices[position][LIGNE] + chiffre-1] || flags[indices[position][COLONNE] + chiffre-1] || flags[indices[position][CARRE] + chiffre-1]) ) {


                                std::cout << "La case est libre" << std::endl;


                                flags[indices[position][LIGNE]+chiffre-1] = true;   // La ligne contien maintenant ce chiffre.


                                flags[indices[position][COLONNE]+chiffre-1] = true;   // La colonne contien maintenant ce chiffre.


                                flags[indices[position][CARRE]+chiffre-1] = true;   // Le carré contient maintenant ce chiffre.


                            }


                            return 0;


                        }

                        -
                        Edité par PierrotLeFou 14 décembre 2023 à 5:15:19

                        • Partager sur Facebook
                        • Partager sur Twitter

                        Le Tout est souvent plus grand que la somme de ses parties.

                          14 décembre 2023 à 11:38:40

                          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é.

                          • Partager sur Facebook
                          • Partager sur Twitter
                            14 décembre 2023 à 13:38:51

                            Bonjour,

                            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;				   
                            }
                            



                            • Partager sur Facebook
                            • Partager sur Twitter
                              14 décembre 2023 à 14:02:16

                              Il y a quelques années, j'avais organisé un concours sur le sudoku.

                              Si ca peut t'inspirer:
                              Concours - sudoku par Deedolith - page 1 - OpenClassrooms

                              • Partager sur Facebook
                              • Partager sur Twitter
                                16 décembre 2023 à 17:34:43

                                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;
                                }
                                

                                Le main lit une grille, résoud et affiche

                                #include <stdlib.h>
                                #include <stdio.h>
                                
                                #include "lecture.h"
                                #include "contraintes.h"
                                #include "resolution.h"
                                
                                int main(int argc, char * argv[])
                                {
                                  int grille[81], solution[81];
                                  
                                  if (argc != 2) {
                                    printf("Usage: %s nom-fichier\n", argv[0]);
                                    exit(EXIT_FAILURE);
                                  }
                                  calculer_contraintes();
                                  lire_grille(argv[1],grille);
                                  ecrire_grille(grille);
                                  bool resolu = resoudre(grille,solution);
                                  if (resolu) {
                                    ecrire_grille(solution);
                                  } else {
                                    printf("Pas de solution\n");
                                  }
                                  exit(EXIT_SUCCESS);
                                }
                                

                                Les lectures affichages se font là dedans (mal nommé lecture.c)

                                // lecture.c - fait aussi les écritures
                                
                                #include "lecture.h"
                                
                                #include <stdio.h>
                                
                                void lire_grille(char fichier[], int grille[81])
                                {
                                    FILE * f = fopen(fichier,"r");
                                    int nb = 0;
                                    while (nb<81) {
                                        char c = fgetc(f);
                                        if (c=='.') {
                                            grille[nb++] = 0;
                                        } else if (('1' <= c) && (c <= '9')) {
                                            grille[nb++] = c-'0';
                                        }
                                    }
                                    fclose(f);
                                }
                                
                                void ecrire_grille(int grille[81])
                                {
                                    int i=0;
                                    for (int gl=0; gl<3; gl++) {
                                        for (int l=0; l<3; l++) {
                                            for (int gc=0; gc<3; gc++) {
                                                for (int c=0; c<3; c++) {
                                                    if (grille[i] == 0) {
                                                        printf(".");
                                                    } else {
                                                        printf("%d",grille[i]);
                                                    }
                                                    i++;
                                                }
                                                printf(" ");
                                            }
                                            printf("\n");
                                        }
                                        printf("\n");
                                    }
                                }
                                

                                Un exemple de grille, dans le format correspondant

                                .7. .63 ...
                                2.. ... 7..
                                ... ... 49.
                                
                                ... .7. ..1
                                5.. 9.6 ..8
                                1.. .2. ...
                                
                                .28 ... ...
                                ..3 ... ..6
                                ... 48. .5.
                                








                                -
                                Edité par michelbillaud 16 décembre 2023 à 17:36:08

                                • Partager sur Facebook
                                • Partager sur Twitter
                                  17 décembre 2023 à 7:18:29

                                  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

                                  • Partager sur Facebook
                                  • Partager sur Twitter

                                  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.
                                  • Editeur
                                  • Markdown