Recherche aléatoire de solutions

Il existe certains jeux pour lesquels il n'est pas possible d'utiliser une stratégie. Le jeu du "Compte est bon" en est une bonne illustration.

Il n'existe pas, (du moins je ne connais pas) d'algorithme permettant de trouver rapidement une solution. De plus, comme il existe quelques millions de possibilités, il n'est pas possible de les examiner toutes exhaustivement.

Pour résoudre ce problème, le plus simple est de rechercher aléatoirement des solutions et de ne garder que celle qui se rapproche le plus du résutat demandé. L'applet suivante est une implémentation du jeu du "Compte est bon" :

L'essentiel du programme est constitué par la recherche aléatoire de solutions. Cette recherche s'effectue par un objet "Solution" décrit ci-dessous :

class Solution {
	int sol = 0;
	int valeur = 0;
	int[] chif_trav = new int[26];
	int[] utilise = new int[26];
	int nb_resultats_indermediaires = 0;
	String[] etapes = new String[20];
	int nb_etapes = 0;

	Solution(int [] chiffres, int s) {
	  	int temp = 0;
	  	sol = s;
	  	for (int i=0;i<26;i++) {
	  		chif_trav[i] = 0;
	  	}
	  	for (int i=0;i<26;i++) {
	  		utilise[i] = 0;
	  	}
	  	// On réparti les 6 chiffres d'une manière aléatoire
	  	for (int i=0;i<6;i++) {
	  		do {
				temp =(int)Math.round((Math.random()*6));
				if (temp==6) temp=0;
	  		}
	  		while (chif_trav[temp] != 0);
	  		chif_trav[temp] = chiffres[i];
	  	}
	  	calcule();
	  }

	public void calcule() {

	int n1 = 0; int n2 = 0;
	int nb1 = 0; int nb2 = 0;
	int res = 0;int cpt = 0;
	int op = 0;boolean ok = true;
	int j=0;
	while ((res != sol) && (cpt < 20) && (ok)) {
		ok = false;
		while (! ok) {
			ok = true;
			n1 = (int)Math.round((Math.random()*(6+ nb_resultats_indermediaires)));
			if (n1>=6+nb_resultats_indermediaires) ok=false;
			if (utilise[n1]==1) ok = false;
		}
		if (ok) utilise[n1]=1;
		ok = false;
		while (! ok) {
			ok = true;
			n2 = (int)Math.round((Math.random()*(6+ nb_resultats_indermediaires)));
			if (n2>=6+nb_resultats_indermediaires) ok=false;
			if (utilise[n2]==1) ok = false;
		}
		if (ok) utilise[n2]=1;
		op = 0;
		while (op == 0) {
			nb1 = chif_trav[n1];
			nb2 = chif_trav[n2];
			op = (int)Math.round((Math.random()*4));
			op = op + 1; // 1 = +, 2 = -, 3 = *, 4 = /

			if (op>4) op=0; else
			if ((op==4) && (nb2>nb1)) op=0; else
			if ((op == 4) && ((nb1 % nb2) != 0)) op=0; else
			if ( ((nb1==1) || (nb2==1)) && ((op==3) || (op==4))) op=0; else
			if ( (nb2>=nb1) && (op==2)) op=0;

			if (op != 0) {
				String s = " "+nb1;
				switch (op) {
					case 1 : res = nb1 + nb2;s=s+" + ";break;
					case 2 : res = nb1 - nb2;s=s+" - ";break;
					case 3 : res = nb1 * nb2;s=s+" * ";break;
					case 4 : res = nb1 / nb2;s=s+" / ";
				}
				if (res > 0) {
					s=s+nb2+" = "+res;
					etapes[cpt]=s;
					cpt++;
					chif_trav[6+nb_resultats_indermediaires]=res;
					utilise[6+nb_resultats_indermediaires]=0;
					nb_resultats_indermediaires++;
					if ((valeur==0) || (get_diff() > Math.abs(res-sol))) {
						valeur = res;
						nb_etapes=cpt;
					}
				}
			}
		}
		j=0;
		ok=false;
		for (int i=0;i<6+nb_resultats_indermediaires;i++)
		if (utilise[i]==0) j++;
		if (j>1) ok=true;
	}
	}

	  public int get_valeur() { return valeur;}

	  public int get_diff() { return Math.abs(valeur-sol
	  );}

LOEWENGUTH Pascal - http://lwh.free.fr -