[Plan du site] Vous êtes ici --- > Le Site du Zéro > Les forums > Concours > Le Sudoku : des nombres en folie ! > Algorithme de résolution par backtracking > Lecture du sujet

Algorithme de résolution par backtracking

Segmentation fault

Vous devez être inscrit pour pouvoir poster des messages

Page : 1

Auteur

Message

1 visiteur sur ce sujet (1 anonyme)

Page : 1

BSoD

# Posté le 29/07/2008 à 10:55:07

Groupe : Membres

Bonjour,

Bien que je ne participe pas au concours, j'essaye d'implémenter un algorithme de résolution de Sudoku par backtracking, mais celle-ci ne marche pas à tout les coups (alors que la grille proposée a bien une solution).

Voici la fonction de backtracking :
Code : C++

void Sudoku::back(int i, int val, Coordonnees tab[]) {

    // i : l'index de la case à tester dans le tableau tab[]
    // val : la valeur à tester dans cette case
    // tab[] : tableau contenant les coordonnées de tous les 0 dans la grille (ce tableau n'est jamais modifié par la fonction)

    if(estValide() && estCompletee())
        return; // la résolution est terminée, je ne fais plus de modification sur la grille

    if(val > 9) {
        set(tab[i], 0); // je remets la case courante à 0
        int newVal = get(tab[i - 1]) + 1; // je récupère la valeur de la case précédente, et je lui ajoute 1
        return back(i - 1, newVal, tab); // je retourne à la case précédente, et j'y teste la valeur suivante
    }

    set(tab[i], val); // je mets la valeur souhaitée dans la case courante...
    if(estValide())
        return back(i + 1, 1, tab); // ... et si la grille toujours est valide, je passe au 0 suivant

    return back(i, val + 1, tab); // ... sinon, j'essaye la valeur suivante
}

Je sais qu'il manque des tests (par exemple si la grille est insoluble, et que je me retrouve dans les indexes négatifs, etc...), mais je ne fais pour l'instant aucun cas tordu, ce qui explique que l'algo est assez sommaire.

Le problème est que parfois je me retrouve (après que l'algo ait mouliné quelques secondes) avec un "segmentation fault", qui, si j'ai bien compris, signifie que le programme écrit à un emplacement de la mémoire qui ne lui ait pas réservé. o_O

Qu'est-ce qui pourrait causer ce genre d'erreur, et comment résoudre le problème ?

Merci d'avance.

Edit : je précise que j'exécute le programme sous Ubuntu 8.04.

Édité le 29/07/2008 à 11:00:11 par BSoD

Natim

# Posté le 29/07/2008 à 11:27:24

Apprendre à coder c'est coder

Groupe : Membres

segfault veut justement dire que tu sors du tableau à cause du fait que tu ne fais pas de tests sur tes index.

Édité le 29/07/2008 à 11:27:49 par Natim

BSoD

# Posté le 29/07/2008 à 11:35:28

Groupe : Membres

Hmm à vrai dire je pense aussi que c'est ça, mais le truc c'est que j'ai fait un mode "verbose" du programme, et lorsque je vois les détails de ce qu'il fait (et notamment, à quelle case il accède à chaque tour), je constate que ne sors jamais du tableau (pour preuve, la case qui pose problème a, dans certains cas, déjà été accédée, donc elle existe bien)... et puis la grille utilisée est valide (c'est celle de Wikipédia, qui a pour but d'être difficile à résoudre par bruteforce), donc je ne suis pas sensé sortir du tableau normalement...

Nanoc

# Posté le 29/07/2008 à 13:48:19

Apprenez à utiliser la STL !!
Avatar

Groupe : Membres

Est-ce que par hasard tu dépasserais la limite du nombre d'appel de fonctions à cause de ta récursion ?

Exercices de C++ pour tous les niveaux !
Mes tutos: Tri de Shell --- [C++] Manipulateurs de flux
--- [C++] Notions avancées (suite du cours de M@teo21)

BSoD

# Posté le 29/07/2008 à 13:51:15

Groupe : Membres

C'est très probable, oui (vu que la grille est faite pour ça).

Quelle est cette limite ? Est-ce qu'on peut la modifier ?

Edit : je viens de faire le test : la fonction a été appelée 131 000 fois avant d'être stopée.

Édité le 29/07/2008 à 13:56:31 par BSoD

Nanoc

# Posté le 29/07/2008 à 14:00:48

Apprenez à utiliser la STL !!
Avatar

Groupe : Membres

je sais pas quelle est la limite. Mais il est bien possible que tu la dépasses avec un nombre pareil (En fait c'est le nombre total de fonction appelée en même temps à un instant donné qui est limité).

Non, tu peux pas modifier cette limite. Mais je pense que tu peux revoir ta fonction.

Exercices de C++ pour tous les niveaux !
Mes tutos: Tri de Shell --- [C++] Manipulateurs de flux
--- [C++] Notions avancées (suite du cours de M@teo21)

BSoD

# Posté le 29/07/2008 à 14:37:59

Groupe : Membres

Citation : Nanoc

(En fait c'est le nombre total de fonction appelée en même temps à un instant donné qui est limité).

Ca veut dire que je peux régler le problème en mettant le programme en pause de temps en temps, non ?

Citation : Nanoc

je pense que tu peux revoir ta fonction.

Ben, c'est un backtracking classique, je ne vois pas trop comment je peux l'optimiser. o_O

Mais bon, puisque le soucis est maintenant précisément localisé, je vais voir ce que je peux faire pour ça.

En tout cas merci à Natim et à toi pour votre aide.

Édité le 29/07/2008 à 14:40:29 par BSoD

Nanoc

# Posté le 29/07/2008 à 15:28:14

Apprenez à utiliser la STL !!
Avatar

Groupe : Membres

1) Non. quand la fonction f() appelle la fonction f(), on a deux appels "l'un dans l'autre". Jusqu'au moment où la deuxième fonction f() se termine. Faire une pause ne changera rien.

C'est pas une question d'optimisation. Le problème est que tu apelle trop de foix cette fonction. Il faudrait en terminer quelques appels en cours de route pour diminuer la taille de la pile d'appel.

Exercices de C++ pour tous les niveaux !
Mes tutos: Tri de Shell --- [C++] Manipulateurs de flux
--- [C++] Notions avancées (suite du cours de M@teo21)

Natim

# Posté le 29/07/2008 à 15:36:23

Apprendre à coder c'est coder

Groupe : Membres

Le backtraking ne devrait jamais faire plus de 5000 boucles sinon c'est que la grille est infaisable.

BSoD

# Posté le 29/07/2008 à 15:39:28

Groupe : Membres

Je suis certain que la grille est faisable, je vais donc revoir mon algo.

Nanoc

# Posté le 29/07/2008 à 15:43:31