Méthode programmation chiffres/lettres

En énumérant tous les cas possibles voici ce que ça pourrait donner (je me limite à + et -)
On a 1, 3 et 8. On cherche tous les résultats possibles (bête et méchant)

Pas 0 : ("",1,3,8)

Pas 1 : 
("1+3=4",8,4), ("1+8=9",3,9), ("3+1=4",8,4), ("3+8=11",1,11), ("8+1=9",3,9), ("8+3=11",1,11)

("1-3=-2",8,-2), ("1-8=-7",3,-7), ("3-1=2",8,2), ("3-8=-5",1,-5), ("8-1=7",3,7), ("8-3=5",1,5)

Pas 2 
("1+3=4, 8+4=12",12), ("1+8=9, 3+9=12",12), ("3+1=4, 8+4=12",12),
("3+8=11, 1+11=12",12), ("8+1=9, 3+9=12",12), ("8+3=11, 1+11=12",12),
("1-3=-2, 8+(-2)=6",6), ("1-8=-7, 3+(-7)=-4",-4), ("3-1=2, 8+2=10",10),
("3-8=-5, 1+(-5)=-5",-4), ("8-1=7, 3+7=10",10), ("8-3=5, 1+5=6",6),
("1+3=4, 4+8=12",12), ("1+8=9, 9+3=12",12), ("3+1=4, 4+8=12",12),
("3+8=11, 11+1=12",12), ("8+1=9, 9+3=12"), ("8+3=11, 11+1=12",12),
("1-3=-2, (-2)+8=6",6), ("1-8=-7, (-7)+3=-4",-4), ("3-1=2, 2+8=10",10),
("3-8=-5, (-5)+1=-5",-4), ("8-1=7, 7+3=10",10), ("8-3=5, 5+1=6",6), 

("1+3=4, 8-4=4",4), ("1+8=9, 3-9=-6",-6), ("3+1=4, 8-4=4",4),
("3+8=11, 1-11=-10",-10), ("8+1=9, 3-9=-6",-6), ("8+3=11, 1-11=-10",-10),
("1-3=-2, 8-(-2)=10",10), ("1-8=-7, 3-(-7)=10",10), ("3-1=2, 8-2=6",6),
("3-8=-5, 1-(-5)=6",6), ("8-1=7, 3-7=-4",-4), ("8-3=5, 1-5=-4",-4),
("1+3=4, 4-8=-4",-4), ("1+8=9, 9-3=6",6), ("3+1=4, 4-8=-4",-4),
("3+8=11, 11-1=10",10), ("8+1=9, 9-3=6"), ("8+3=11, 11-1=10",10),
("1-3=-2, (-2)-8=-10",-10), ("1-8=-7, (-7)-3=-10",-10), ("3-1=2, 2-8=-6",-6),
("3-8=-5, (-5)-1=-6",-6), ("8-1=7, 7-3=4",4), ("8-3=5, 5-1=4",4)

Remarques :
1) il y a énormément de cas possibles, et ça augmente très vite. Là j'ai 3 chiffres et 2 opérations toi tu veux 8 chiffres et 4 opérations !!

2) il y a beaucoup de doublons, mais ça peut se gérer à différents niveaux :
en amont -> ne pas distinguer les cas a+b et b+a (pareil pour a*b)
en aval -> supprimer les résultats partiels qui sont en double : avec les même chiffres de départs, ou négatifs : c=a-b<0 ne pourra être utilisé qu'avec d-c>0, c'est donc pareil que faire (d-a)+b

Du coup les solutions restantes sont moins nombreuses (je te laisse voir lesquels c'est ^^)

3) ici je n'ai pas précisé la valeur que je cherchais, il est évident que dès qu'on la trouve on s'arrête (du coup il n'est pas nécessaire de se limiter à prendre tous les chiffres). Et si on énumère tout parce qu'on n'a pas trouvé la bonne valeur on peut quand même déterminer la valeur "la plus proche".

4) je ne dis pas que ma méthode est la meilleure, loin de là, mais c'est la seule que j'ai pour l'instant, et à mon avis tu peux t'en sortir comme ça.

5) cette méthode fonctionne quel que soit le nombre de chiffres donnés au départ, par contre ne lance pas tout de suite la recherche avec 8 chiffres car ça va surement ramer --'

Mes excuses pour mon temps à répondre.

En effet la programmation s'avère compliquée, néanmoins ta méthode me semble être en effet une des plus efficace !
J'en ai parlé à plusieurs amis étudiants, certains pensaient utiliser le modulo entre chaque nombre ou encore énumérer tous les calculs possible à l'aide de boucle ( comme toi si j'ai bien tout compris...)

Je vais parler a mon prof d'algorithmique sur ce sujet, il travaille justement dans l'intelligence artificielle, voir s'il a une idée sur le sujet :)

Par ailleurs j'ai pu constater ne pas être le seul a vouloir programmer ce genre de chose ( http://j.mochel.free.fr/comptebon.php ; http://mamisab.chez-alice.fr/ ) et je pense que l'exercice bien que complexe sera assez instructif pour moi ! Je vais tenter de coder tout ça prochainement...

Il faudrait regarder en effet l'énumération parce que même si l'explosion combinatoire est très importante, toi a priori tu ne vas vouloir aller que jusqu'à n=8 donc ça peux peut-être se faire en temps raisonnable. Au pire, tu peux te placer dans les même conditions qu'à la télé. Et imposer qu'au bout de 20 ou 30 secondes (je ne sais pas à combien de temps les candidats ont droit) le programme te donne la meilleure qu'il a trouvé. Même s'il n'a pas le bon compte (qui n'est pas toujours possible) il pourrait quand même avoir trouvé une solution approchée pas trop mauvaise.
Côté intelligence artificielle je vois difficilement comment s'en sortir, parce le comportement des opérateurs * et + par exemple conduisent à deux voisins très éloignés dans l'espace de solutions et je ne vois pas comment diriger la recherche judicieusement. De toute façon cela t'amènerai surement à manipuler des connaissances que tu n'ais pas encore prêt à comprendre ^^
Après bien sûr il y en a d'autres qui ont déjà fait ce genre de choses, mais regarder ce qu'ils ont fait est peut-être moins intéressant que trouver une méthode par toi même, moi j'ai donné l'idée sur laquelle d'instinct je partirai en premier, je n'ai jamais dit que c'était la meilleure ;-)

Bonsoir,

J'ai eu un peu de temps cet après-midi et je me suis amusé à faire le code de ton programme.
Alors bonne nouvelle : le temps de calcul est moins important que ce que je pensais, parce qu'en fait il trouve tout le temps une solution. Je mets donc 2 ou 3 secondes maximum avec les 8 chiffres et les 4 opérations. Si vraiment la solution n'existe pas alors dans ce cas ça va ramer et il faut l'arrêter au bout de 45 secondes pour lui demander le mieux qu'il a trouvé...
C'est donc de la force brute avec une méthode d'exploration quasiment identique à celle que j'ai expliqué sur l'exemple. Je n'ai pas mis en place toutes les précautions dont je parlais pour optimiser le programme, ce ne serait vraiment intéressant que lorsque la solution n'existe pas.

Remarque : les calculs de mon programme ne sont pas très humains parce qu'il prend les chiffres de gauche à droite et essaye de faire au mieux comme ça, et puisqu'il trouve le bon compte, il ne cherche pas de solutions plus simples, même si on pourrait l'améliorer dans ce sens ;-)

Exemple : faire 500 avec 100,8,75,3,4,9,6,3.
Humain : 9-4=5, 5*100=500.
Ordinateur : 100+8=108, 108+75=183, 183+3=186, 186*3=558, 558-4=554, 9*6=54, 554-54=500

Ce n'est pas à moi de faire ce code que je sache ! Tous les ans à la même époque les même questions qui reviennent, les profs ne se foulent pas trop, mais de toute évidence les élèves non plus !

En plus je t'ai déjà répondu dans ta discussion (ici) : "depuis le temps je n'ai plus le code sous la main"

merciiii pour votre aide :)