Casse-tête

Messages postés
1100
Date d'inscription
jeudi 24 avril 2003
Statut
Membre
Dernière intervention
17 octobre 2012
- - Dernière réponse : cptpingu
Messages postés
3801
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
15 novembre 2019
- 28 déc. 2010 à 15:37
Bonjour,

Sur mon site personnel, j'ai un jeu de casse-tête avec des cases à cocher : http://victorc.olympe-network.com/casse-tete.html

Je voudrais en faire un petit logiciel que je publierai peut-être ici mais avec la solution pour le résoudre.
C'est à dire que l'utilisateur peut choisir de le résoudre à la main, ou de demander à l'ordinateur de le résoudre à sa place.
Le problème c'est que je ne trouve pas l'algorithme adéquat, ni même le nom exact de ce jeu.

Si vous avez des informations, je suis preneur.

Merci et bonne prog,
@++

Victor
Afficher la suite 

6 réponses

Messages postés
3801
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
15 novembre 2019
90
0
Merci
Utilise un algorithme de backtracking. Ça devrait fonctionner :)

________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question
Commenter la réponse de cptpingu
Messages postés
3801
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
15 novembre 2019
90
0
Merci
(Problème de js, soi dit en passant. Le script est introuvable/indisponible au moment ou j'écris ces lignes).

________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question
Commenter la réponse de cptpingu
Messages postés
1100
Date d'inscription
jeudi 24 avril 2003
Statut
Membre
Dernière intervention
17 octobre 2012
3
0
Merci
Bonjour,

C'est bisard chez moi j'ai essayé avec FF4 64 bits et IE9 64 bits à l'instant et ça fonctionne.

Merci pour la piste, je vais chercher de ce côté.

Merci et bonne prog,
@++

Victor
Commenter la réponse de victorcoasne
Messages postés
3801
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
15 novembre 2019
90
0
Merci
Pas de problème avec ton script finalement. J'ai simplement plusieurs ip (via tunnel ssh) et l'une d'elle déconnait. En changeant de connexion pas de soucis (FF3.6 Linux).
Backtracking théoriquement viable. Techniquement, ça peut être très lent (en tout cas plus lent qu'une méthode non généraliste).

________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question
Commenter la réponse de cptpingu
Messages postés
1100
Date d'inscription
jeudi 24 avril 2003
Statut
Membre
Dernière intervention
17 octobre 2012
3
0
Merci
Bonjour,

Je me dis qu'avant d'essayer de la résoudre, il faut p'tet que je fasse un générateur de grille, et m'assurer que la grille peut être résolue.

Qu'en penses-tu ?

J'ai regardé le backtracking mais j'ai un peu de mal dans ce cas, pour un sudoku ça a l'air plus simple, mais c'est pas mon but.
Si j'ai bien compris en backtracking, il faut que je mémorise une grille à chaque fois que j'essaye un truc pour revenir en arrière.
Et donc après je pars d'une case coché pour inverser le tout, puis j'applique ça sur chacune des cases noires adjacentes jusqu'à avoir une grille vide.
Le problème c'est qu'il faut éviter de refaire 5000 fois la grille en partant de la même case.

Merci et bonne prog,
@++

Victor
Commenter la réponse de victorcoasne
Messages postés
3801
Date d'inscription
dimanche 12 décembre 2004
Statut
Modérateur
Dernière intervention
15 novembre 2019
90
0
Merci
Je me dis qu'avant d'essayer de la résoudre, il faut p'tet que je fasse un générateur de grille, et m'assurer que la grille peut être résolue.

Ce n'est pas nécessaire. Si tu as parcouru tous les cas possibles sans trouver de réponse, la grille est impossible. Ça ne gêne pas l'algorithme.

Si j'ai bien compris en backtracking, il faut que je mémorise une grille à chaque fois que j'essaye un truc pour revenir en arrière.

Oui et c'est gourmand en mémoire puisque tu conserves tous les états (Tu as autant de grille que de disposition possibles).
On peut bien sur améliorer le tout avec un "élagage alpha-béta" (nom barbare pour dire: si un cas vas mener vers des cas pourri, autant ne pas aller dans la branche).

________________________________________________________________________
Historique de mes créations, et quelques articles:
[ http://0217021.free.fr/portfolio http://0217021.free.fr/portfolio]
Merci d'utiliser Réponse acceptée si un post répond à votre question
Commenter la réponse de cptpingu