Bonsoir à tous,  
 
Je dois créer un programme en python, capable trouver un solution (ou alors la solution la plus proche) du jeu "Le compte tes bon" ("des chiffres" de des chiffres et des lettres), en lui donnant une liste de 6 nombre (appartenant  l'ensemble 1,2,3,4,5,6,7,8,9,10,25,50,75,100) et un nombre à trouver (entre 100 et 999).  
Petit rappel sur le "compte est bon" : on peut utiliser autant de fois les opérateurs +,-,*,/ mais on ne peut utiliser qu'une seule fois les chiffres de la liste de départ.  
 
J'ai recherché longuement sur internet une idée d'algorithme.. il a des choses intéressante mais je n'arrive pas a les appliquer avec python
 
Je veux appliquer l'algorithme "simple" mais "lourd" qui consiste à calculer toutes les solutions possible avec la liste donnée, et de s'arrêter si on trouve la réponse.  
 
En gros en le schématisant par un arbre, voilà ce que ça donne :  
 

 
Quelqu'un pourrait-il me guider pour écrire l'algorithme (en Python) capable de faire TOUTES les solutions de l'arbre ??
 
Merci d'avance.. je suis perdu

 
Une fonction récursive qui reçoit
- le chiffre en cours de traitement
- la liste des chiffres dispo
- le nombre à atteindre
La fonction prend le chiffre en cours, lui applique un opérateur parmi les 4 dispo pour opérer avec le premier chiffre de la liste. Cela donne un certain résultat. Si le résultat correspond au nombre à atteindre alors ok, sinon appel récursif en lui passant
- le résultat courant
- la liste des chiffres dispo (àa laquelle on a enlevé le nombre déjà utilisé)
- le nombre à atteindre
 
Au retour de l'appel récursif, la fonction utilise l'opateur sur le second chiffre puis le 3° etc. Puis une fois que tous les chiffres ont été traités, elle recommence avec l'opérateur suivant etc.

Ca va certainement faire un paquet de possibilité. Mieux vaut partir sur un A*.

Sinon, si tu veux être exhaustif, il faut faire un algo avec du backtracking. Voire utiliser un système expert pour pas tout recoder.

Boaf, il y a 6 chiffres à examiner dans toutes les configurations ce qui donne 6! = 720 configurations
Chaque configuration aura 5 opérations à faire avec 4 opérandes par opération soit 4^5 = 1024 possibilités.
Donc un total de 720 * 1024 = 737280 cas à examiner. C'est pas insurmontable. D'ailleurs j'ai codé l'algo cet aprem et il fonctionne assez rapidement (si la solution est possible il la sort en moins de 2 sec). S'il t'intéresse je te le passe par MP...

737280 ne sont pas toute les solutions
car dans ton raisonnement tu fait l'enchainement d'opération a la suite.
donc par exempl e
( (chifre1 operandes1 chifre2) operandes2 chifre3) operandes3 chifre4) operandes4 chifre5) operandes5 chifre6
par exemple (1*4)+3)*12)-5)*4=316
mais tu as le cas ((1*4)+(3*12)-5)*4=140  
j'espere que tu comprends ce que je veut dire, il y en a largement plus de test à faire, sauf erreur de ma part
 
et pourtant j'utilise les 6 chiffres, mais tu peut faire des combinaisons de calcul de chiffre, pas obligatoirement a la suite

1 + 4 = 5
5 - 3 = 2
2 * 12 = 24
24 + 4 = 28
28 * 5 = 140
 
3 + 1 = 4
4 * 4 = 16
16 + 12 = 28
28 * 5 = 140
 
12 + 1 = 13
13 - 3 = 10
10 * 4 = 40
40 - 5 = 35
35 * 4 = 140
 
5 + 1 = 6
6 - 3 = 3
3 * 4 = 12
12 * 12 = 144
144 - 4 = 140
 
(merci à mon programme   )
 

Oui je vois bien ce que tu veux dire et t'as eu raison de me le faire remarquer (désolé si j'ai eu l'air de me moquer de ton exemple précédent). Effectivement si je fais [(19 + 17) * (23 + 29) - 2] * 31 ça donne 57970 mais si je passe ces chiffres à mon algo, il ne trouve pas. Son plus proche résultat est 57942
23 * 2 = 46
46 + 19 = 65
65 * 31 = 2015
2015 - 17 = 1998
1998 * 29 = 57942
 
Ouaip...  je ne vois pas trop comment résoudre le problème...

Regarde par ici :  
http://eternitygames.free.fr/LeCompteEstBon.html

c'est vrai que la ca complique enormement l'algo,
 
meme avec l'algo donner par guybrush bonne chance pour le coder,  
ca va pas etre marrant je pense.

 
YES !!!
 

Ben si justement, c'est ce genre d'algo qui est marrant à coder
 
D'ailleurs en ce moment je suis sur l'énigme 5 6 de Python Challenge => http://forum.hardware.fr/hfr/Progr [...] 0007_1.htm

Merci à tous pour vos réponses !
 

 
Dommage, je devrais faire ce programme pour.. hier.. mais je n'ai pas réussi, tant pis.  
Par contre je veux bien que tu m'envoie ton algo par MP aussi, si tu le veux bien ?
 
Merci encore !

 
ben t'es pas allé voir le lien de guybrush02 ? Tout est expliqué. il y a même un programme MsDOS et un code source en C dispo !!!
 
J'ai déjà expliqué mon algo (qui d'ailleurs n'est pas parfait). Voici le schéma de la fonction de recherche

 
Ensuite, plus qu'à faire une fonction de base qui va appeler cette recherche pour chaque nombre de la liste et c'est fini