Ton constructeur de Bloc ne fait rien, il faut l'enlever. Le simple fait d'en ajouter un rend l'optimisation plus difficile pour le compilateur (cf. https://www.youtube.com/watch?v=3LsRYnRDSRA). La seule différence serait si tu n'appelle pas explicitement le constructeur de bloc, mais de toute façon il faut initialiser ses variables, n'est-ce pas ?
struct Bloc {
int pos, n;
};
int main() {
Bloc b1; // non initialisé (mais à éviter généralement)
Bloc b2{}; // initialisé par le constructeur par défaut
// on a bien b2.pos == 0 && b2.n == 0
return 0;
}
Ensuite il est normal que la pile d'exécution explose, déjà parce que tu utilises une fonction récursive, bien que ça ne soit pas gênant dans la plupart des cas, mais on préférera des versions itératives si possibles, sauf si la fonction est récursive terminale, auquel cas le compilateur peut trivialement la rendre itérative. Mais le plus gros problème est que tu prends à chaque fois la grille par valeur, autrement dit à chaque appel, l'entièreté de la grille est copiée.
Le C++ ne fonctionne pas comme d'autres langages style Java, quand tu prends un objet par valeur, c'est une copie qui est faite. Il faut donc plutôt le prendre par référence (constante si tu n'as pas l'intention de modifier la grille) :
bool backtrack(const std::vector<std::vector<int>>& grille, int id);
Mais ici, tu as besoin de modifier la grille avant de lancer l'appel récursif, tu devrais donc faire une copie de la grille juste avant l'appel récursif, pour éviter de le copier à chaque fois. Sinon d'une manière générale, si tu as l'intention de copier l'objet passé en paramètre, il est plus clair de le prendre explicitement par copie, et non par référence constante et le copier juste après. Mais ici cela peut éviter de faire des copies inutiles à chaque appel récursif. D'ailleurs tu ne veux pas vraiment copier la grille passé en paramètre, tu veux plutôt générer les noeuds "fils" de l'état courant.
Aussi, on pourrait discuter sur le fait d'utiliser un vecteur de vecteur pour représenter la grille, qui n'est pas forcément la solution optimale, étant donné que tu connais la taille de la grille à la compilation. Tu pourrais utiliser std::array, et au passage remplacer le #define par une variable constexpr, qui a l'avantage de passer par le système de typage, pour plus de "sécurité". Et tant qu'on y est, tu peux renommer le tableau de tableau en "Grille" par exemple, comme ça c'est plus court à taper et ça enlève la responsabilité à toutes les fonctions qui l'utilisent de savoir que c'est un "tableau de tableau" :
constexpr int N = 9;
using Grille = std::array<std::array<Bloc, N>, N>;
bool backtrack(const Grille& grille, int id);
Si tu veux aller plus loin et entrer dans le territoire de "l'overengineering", tu peux faire une véritable classe "Grille" qui en interne utilise un tableau de tableau et qui expose des fonctions permettant de manipuler la grille, accéder à ses éléments, etc, En redéfinissant operator[] par exemple pour utiliser la syntaxe des crochets. Je te conseille cependant de savoir que tu as effectivement besoin d'une telle complexité avant de te de faire ça, car souvent on pense trop et on se retrouve à devoir modifier la spec dans tous les cas, ce qui est au mieux une perte de temps et au pire on passe à côté d'une solution plus simple (puisqu'on a réfléchi à une solution sans réellement avoir les problèmes pratiques sous les yeux, puisqu'on a pas encore commencé à coder).
- Edité par JadeSalina 26 septembre 2021 à 15:31:26
N'aurais-tu pas compris le fonctionnement de assert à l'envers ?
Ta ligne :
assert(i == 81 && "i = 81");
termine le programme si i est différent de 81, alors que ça devrait être l'inverse. La condition dans l'assertion doit être vraie pour laisser le programme continuer, or i ne devrait jamais dépasser 80 en fonctionnement normal.
Je suis allé revoir mon premier code. Si tu remarques, j'ai abandonné la grille des contraintes ou peu importe comment on l'appelle. Ma façon de faire les appels récursifs fait que je ne peux pas effacer une case initialisée au départ. Le fondement d'un algorithme récursif (je dis des conneries?) est de savoir quand s'arrêter. Il semble que tu as fini par le comprendre. On n'a pas besoin de backtracking explicite. C'est l'empilage et le dépilage de la récursivité qui le fait. Regardes comment est faite ma fonction placer().
Ça pourrait ressembler à ceci: bool placer(grille, position) { si je suis rendu au bout, je retourne true Je fais la liste des chiffres que je peux placer dans cette position (ligne, colonne, carré) pour chiffre dans la liste { je met le chiffre dans position si placer(grille, position suivante) je retourne true // je me suis rendu au bout au cours d'un appel ultérieur } // je suis passé par toutes les possibilités de la liste sans succès j'efface le chiffre pour cette position je retourne false // essai suivant à la position précédente (backtracking) } Le truc est de retourner à ses appelants le fait qu'on s'est rendu au bout (true) ou pas (false) Comme je l'ai indiqué selon les conseils d'autres personnes, on peut faire beaucoup plus rapide.
Tu as un vector de vector. Je ne suis pas un expert en performances en C++, mais c'est sûrement plus lent qu'un simple array malgré mes calculs d'indices.
- Edité par PierrotLeFou 29 septembre 2021 à 3:43:07
Le Tout est souvent plus grand que la somme de ses parties.
Pour ma preuve de concept, j'avais utilisé un mdarray (C++23), mais un std::array ça sera bien aussi. Le gain ne sera pas visible à l'initialisation du programme.
Si en revanche tu recherches une solution par récursion, là cela pourra etre bien plus sensible.
PS: on avait eu un fil sur le sujet de de défi de solveur de sudoku il y a quelques mois.
Oui. Je trouve la syntaxe du quintuple std::array bien lourde (et celle du double aussi...), j'avais déjà été séduit par les mdspan, d'autant qu'ils permettent d'exprimer la notion de groupe ici: tous les algos d'analyses seront strictement les memes entre ligne, colonne ou carré.
EDIT: tentative de contourner l'URLification du forum.
PS: kwk risque d’être ardu pour un débutant d'autant que la doc a l'air d’être bien cachée : il faut lire les tests. A voir quand la présentation de Joel (de lundi) sera mise en ligne histoire de donner quelques points de départ
Voici ma seconde version du solveur de Sudoku avec des bitmap. Il y a un bitmap pour chaque ligne, colonne, carré. Il y a un bit pour chaque chiffre dans un bitmap. Le bit est allumé si je peux placer le chiffre à cet endroit et éteint dans le cas contraire. Je n'ai pas à parcourir chaque ligne, colonne, carré pour savoir si le chiffre s'y trouve déjà. Ça se fait plus rapidement en combinant les 3 bitmap. Par contre, le temps pour allumer les 3 bits pour chaque choix et les éteindre n'est sans doute pas négligeable. J'ai utilisé des macro dans l'espoir que le code sera plus lisible (...). On pourrait gagner en efficacité si on avait un array de 81 structures donnant les bons bitmap pour chaque position. Ils seraient calculés au début lors de l'initialisation. J'ai compilé les deux versions avec l'option -O3 et je suis à la limite de précision de mon ordi. C'est donc difficile de savoir dans quel rapport le second code est plus efficace que le premier. - // Mon solveur de Sudoku - 2.0. #include <iostream> #include <array> #include <string> #include <fstream> #include <chrono> typedef unsigned int bitmap; // Structure associée à la grille. typedef struct Work Work; struct Work { std::array<int, 81> grid; std::array<bitmap, 9> lines; std::array<bitmap, 9> columns; std::array<bitmap, 9> squares; }; // Accès aux bitmap. #define setbit(w,b) ((w)|=1<<(b)) #define offbit(w,b) ((w)&=(~(1<<(b)))) #define getbit(w,b) (((w)>>(b))&1) #define line(l) (l/9) #define column(c) (c%9) #define square(s) ((s)/27*3+(s)%9/3) // Placer un chiffre dans la prochaine position libre. bool placeNumber(Work &work, int pos) { while(pos < 81 && work.grid[pos]) pos++; if(pos >= 81) return true; // Extraire les nombres qu'on peut placer. bitmap mask = work.lines[line(pos)] & work.columns[column(pos)] & work.squares[square(pos)]; for(int bit = 1; bit <= 9; bit++) { if(getbit(mask, bit)) { work.grid[pos] = bit; // Éteindre les 3 bits offbit(work.lines[line(pos)], bit); offbit(work.columns[column(pos)], bit); offbit(work.squares[square(pos)], bit); if(placeNumber(work, pos+1)) return true; // Rallumer les 3 bits setbit(work.lines[line(pos)], bit); setbit(work.columns[column(pos)], bit); setbit(work.squares[square(pos)], bit); } } work.grid[pos] = 0; return false; } // Programme principal. int main() { Work work; const std::string name{ "sudoku.t" }; // Initialiser les bitmap: 1=disponible, 0=dans la case bitmap mask = ((1<<9) - 1) << 1; // bits 1 à 9 allumés. for(int i = 0; i < 9; i++) { work.lines[i] = mask; work.columns[i] = mask; work.squares[i] = mask; } // Lecture de la grille de départ. std::ifstream file(name); if(!file) { std::cerr << "Impossible d'ouvrir le fichier " << name << std::endl; exit(1); } int pos = 0; for(int i = 0; i < 9; i++) { std::string text; std::getline(file, text); for(int c = 0; c < 9; c++) { int tmp; if(text[c]==' ') tmp=0; else tmp=text[c]-'0'; if(tmp) { if(getbit(work.lines[line(pos)], tmp) & getbit(work.columns[column(pos)], tmp) & getbit(work.squares[square(pos)], tmp)) { offbit(work.lines[line(pos)], tmp); offbit(work.columns[column(pos)], tmp); offbit(work.squares[square(pos)], tmp); } else { // erreur std::cerr << "Grille invalide, ligne " << line(pos)+1 << ", colonne " << column(pos)+1 << std::endl; } // erreur } // tmp work.grid[pos++] = tmp; } // c } // i // Résoudre le jeu. auto start = std::chrono::high_resolution_clock::now(); bool solution = placeNumber(work, 0); auto elapsed = std::chrono::high_resolution_clock::now() - start; long long microseconds = std::chrono::duration_cast<std::chrono::microseconds>(elapsed).count(); std::cout << microseconds << " microsecondes" << std::endl; if(solution) { // Afficher la grille. for(int l = 0; l < 81; l+=9) { if(l > 0 && l%27 == 0) std::cout << std::endl; for(int c = 0; c < 9; c++) { if (c > 0 && c%3 == 0) std::cout << " "; std::cout << work.grid[l+c]; } std::cout << std::endl; } } else { std::cerr << "Cette grille n'as pas de solution" << std::endl; } return 0; }
Le Tout est souvent plus grand que la somme de ses parties.
Ça consiste en un ensemble de bits qu'on peut mettre dans un entier par exemple (unsigned int dans mon cas). Dans mon code, le bit 0 de l'entier ne sert à rien. Le bit N correspondant au chiffre N me dit si le chiffre peut être placé dans ma grille. Par exemple, si le bit 1 est allumé, ça veut dire que je peux placer le chiffre 1. J'ai besoin de le savoir pour la ligne, la colonne et le carré où se trouve la case que je suis en train d'examiner. J'avais jeté un coup d'oeil sur l'idée des cases nues et cachées (singleton). Je n'ai pas encore examiné cela en profondeur. Si ça fait passer le nombre d'appels récursifs de 81 à 9 ou 10, ça peut valoir la peine si le temps de calcul n'est pas trop long. En fait, je n'ai pas tout à fait 81 appels. Je dois soustraire le nombre de cases déjà présentes au début. Le singleton a peut-être le même effet.
edit: Voici un extrait d'un lien fourni par lmghs: «Singles: Any cells which have only one candidate can safely be assigned that value. It is very important whenever a value is assigned to a cell, that this value is also excluded as a candidate from all other blank cells sharing the same row, column and box.» Que se passe-t-il si par la suite ça ne marche pas? Qu'est-ce qu'on a réellement sauvé? Cet extrait laisse supposer que quelqu'un serait tenté d'essayer tous les chiffres à une position donnée. Ce n'est pas ce que je fais, je choisis les candidats vraisemblables. Si le candidat est uniqque à un endroit donné à un moment donné, c'est parce que d'autres chiffres ont été placés avant celui-ci. Ces choix n'étaient pas nécessairement corrects ou souhaitables.
- Edité par PierrotLeFou 1 octobre 2021 à 3:17:29
Le Tout est souvent plus grand que la somme de ses parties.
Si je lance le processus au début, il y a peu de chance que je trouve des cases uniques. À partir de quel moment cela en vaudra-t-il la peine? Et si je ne me rend pas au bout, je fais quoi avec ces cases? Je les laisse là ou je les enlève?
Le Tout est souvent plus grand que la somme de ses parties.
Si je lance la recherche au début, la probabilité d'avoir des singleton est très faible. Sauf si le nombre de contraintes est très élevé (comme dans le lien que tu mentionnes) Et précisément dans ce cas, plus le nombre de contraintes sera élevé, plus j'irai rapidement. Je vais essayer d'en tester quelques uns.
edit: j'en ai testé un et c'est très rapide.
Je pense m'écrire une fonction qui vérifie si la solution est bien correcte.
Ça devrait être assez facile avec mes bitmap.
edit2:
J'ai écrit la fonction. Ou bien je n'ai pas d'erreur ... ou bien la fonction est buggée ...
Ça fait une grosse différence de compiler avec l'optiion -O3
Je suis sur Windows 10 et mon compilateur C++ est le suivant: g++ (MinGW-W64 x86_64-posix-seh, built by Brecht Sanders) 9.3.1 20200703 Copyright (C) 2019 Free Software Foundation, Inc.
- Edité par PierrotLeFou 1 octobre 2021 à 19:38:14
Le Tout est souvent plus grand que la somme de ses parties.
Je viens de compiler avec le switch O3 , je ne vois pas de différence. D'habitude je suis avec O2
Ma version du compilateur est la dernière proposée
$ g++ --version
g++ (Ubuntu 11.2.0-7ubuntu2) 11.2.0
Copyright (C) 2021 Free Software Foundation, Inc.
This is free software; see the source for copying conditions. There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE
Je ne compile jamais avec -O2 donc je ne sais pas. J'avais fait mes tests sans l'option -O* C'est possible que la différence entre -oO2 et -O3 soit minime.
Quand on y pense, c'est peut-être idiot de choisir -O1, -O2, -O3. Je dis à mon compilateur «optimise un peu, mais pas trop ...»
edit: Si je regarde les alternatives pour restreindre les candidats, je me refère au lien suivant donné par lmghs sur l'autre post: http://www.angusj.com/sudoku/hints.php Avec les bitmap, il n'est pas trop difficile de placer des chiffres dans les cases appropriées. Mais si on ne trouve pas la solution, qu'est ce qu'on enlève? J'ai juste essayé de placer tous les single à chaque niveau sans les enlever et je me retrouve dans une boucle infinie.
- Edité par PierrotLeFou 2 octobre 2021 à 7:38:35
Le Tout est souvent plus grand que la somme de ses parties.
Pour chaque carré 3x3 si la case est vide je passe en revu les nombres de 1 à 9 en vérifiant qu'il n'est pas déjà dans une autre case dans le carré, la ligne ou la colonne.
Si pour la case je ne trouve qu'une seule possibilité je lui affecte le nombre trouvé.
Puis je fais de même pour chaque ligne colonne.
Reste plus qu'à programmer ça correctement.
Edit: j'essaie de m'informer sur l'utilisation des bitmap. il y a la librairie bitset. si tu as de la lecture à me conseiller.
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.
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.
Le Tout est souvent plus grand que la somme de ses parties.
Le Tout est souvent plus grand que la somme de ses parties.