Discussion :

[getabrainplz]

Bonsoir à tous,

Alors voilà je tente de résoudre un sudoku via la méthode de backtracking en C mais sans la pile système, c'est à dire que c'est moi même qui gère une pile.
Autrement dis, pas d'appels récursifs.

Seulement je ne comprends pas vraiment quand je devrai empiler et dépiler

Pourrez vous m'aider ??

Merci

[pseudocode]

Seulement je ne comprends pas vraiment quand je devrai empiler et dépiler

Tu empiles une valeur dans la pile lorsqu'elle est une solution possible à la case actuelle, et tu passes à la case suivante. Si tu ne trouve pas de solution pour une case, tu dépiles la valeur précédente et tu en testes une autre.

un petit lien pour aider.

[getabrainplz]

Merci de votre réponse.
Alors ok j'ai compris quand dépiler et empiler maintenant.
Par contre lorsque vous me dites de dépiler et d'en tester une autre, je ne comprend pas très bien quoi en faire.
Je fais rien de la valeur dépilée?
Et ma case qui était alors mauvaise précédemment, j'en fais quoi ?

Merci encore de votre réponse.

[Franck Dernoncourt]

As-tu déjà implémenté un algorithme de résolution par backtracking ?

[getabrainplz]

Non c'est la première fois que je m'y attaque ^^

Mon soucis est lorsque je n'ai aucune valeur possible pour une case, je dois donc comme on dit "revenir en arrière" et c'est là que ça coince, je n'arrive pas a cerner le problème.

Lorsque je me rend compte que je n'ai aucune valeur possible ca veut dire que précédemment une case n'est pas "bonne" et là je vois pas comment revenir sur mes pas.

Merci de vos réponse.

[Franck Dernoncourt]

Non c'est la première fois que je m'y attaque ^^

Il vaudrait mieux que d'abord tu t'entraînes en utilisant la récursion classique, comme le montre le code de pseudocode.

Mon soucis est lorsque je n'ai aucune valeur possible pour une case, je dois donc comme on dit "revenir en arrière" et c'est là que ça coince, je n'arrive pas a cerner le problème.

Lorsque je me rend compte que je n'ai aucune valeur possible ca veut dire que précédemment une case n'est pas "bonne" et là je vois pas comment revenir sur mes pas.

pop!

[pseudocode]

Par contre lorsque vous me dites de dépiler et d'en tester une autre, je ne comprend pas très bien quoi en faire.
Je fais rien de la valeur dépilée?
Et ma case qui était alors mauvaise précédemment, j'en fais quoi ?

La valeur que tu as dépilée était par définition la valeur que tu croyais bonne, mais elle t'a menée à une impasse. Tu dois donc la remplacer par une autre valeur possible. Pour un Sudoku, le plus naturel c'est de tester les valeurs dans l'ordre : 1, 2, 3...

Par exemple:
- tu as déjà 4 cases dans ta pile : [1],[5],[2],[6]
- Tu cherches la 5ème case: tu testes 1, 2, 3, ... jusqu'a 9
- Aucune valeur n'est possible pour cette 5ème case: tu es donc dans une impasse => backtracking
- Tu dépiles la 4ème case : [6]. Ta pile contient maintenant [1],[5],[2]
- Tu cherches une autre valeur pour cette 4ème case. Comme tu étais a 6, tu testes 7. Ca ne marche pas. Tu testes 8...
- "8" est possible. Tu empiles 8 dans la pile : [1],[5],[2],[8]
- Tu cherches une valeur pour la 5ème case: tu testes 1, 2, 3, ...
etc.

[getabrainplz]

Merci pour vos réponse, je test ça tout de suite