Casse-tête

Bonjour,

Sur mon site personnel, j'ai un jeu de casse-tête avec des cases à cocher : [ Lien ]

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

Utilise un algorithme de backtracking. Ça devrait fonctionner :)

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

(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
Merci d'utiliser Réponse acceptée si un post répond à votre question

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

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
Merci d'utiliser Réponse acceptée si un post répond à votre question

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

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.


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
Merci d'utiliser Réponse acceptée si un post répond à votre question