Bon, afin d'éviter que mes recherches soient vaines, voilà ce que j'ai pu imaginer.
J'ai scindé le problème en 2 parties.
- le problème d'existence, qui consiste à savoir quelles couleurs sont présentes dans la solution
- le problème de placement, qui lui cherche à placer ces couleurs
L'erreur à ne pas commettre est de résoudre le problème d'existence PUIS celui de placement. Il faut imbriquer les 2 problèmes.
Commençons par le problème d'existence :
Je rappelle que chaque couleur ne peut avoir qu'une seule occurrence.
Il y a 6 couleurs, et 4 emplacements disponibles.
On appelle {A,B,C,D,E,F} les couleurs disponibles, et {a,b,c,d,e,f} leur nombre d'occurrence respectifs.
Or {a,b,c,d,e,f} ont la valeur 0 ou 1, car soit une couleur est dans la solution, soit elle ne l'est pas, et elle ne peut pas apparaître plus d'une fois.
Le problème d'existence consiste donc à trouver la valeur de ces 6 coefficients.
Comment faire ? Prenons un exemple :
On a tenté la combinaison A C F E et après analyse par la machine, il y a 3 pions présents dans la solution finale (ce nombre comprend les indices noirs et blancs)
Puis on fait A F E D -> 2
Eh bien, on peut formaliser le problème par un système d'équations :
a+b+c+d+e+f=4
a+c+e+f=3
a+f+e+d=2
Et on rentre celà dans une matrice en considérant qu'on a :
1a+1b+1c+1d+1e+1f=4
1a+0b+1c+0d+1e+1f=3
1a+0b+0c+1d+1e+1f=2
qui correspond à la matrice :
[[1,1,1,1,1,1,4]
[1,0,1,0,1,1,3]
[1,0,0,1,1,1,2]]
En effet, la première équation correspond au fait qu'il y a 4 pions différents dans la solution.
Et là, à quoi pensent ceux qui connaissent les matrices ? Comment résoudre un système d'équations de sommes ? La méthode de Gauss-Jordan !
Mais là, vous me dites : si on a 6 inconnues, il faut donc nécessairement 6 équations, donc au moins 5 essais.
Mais c'est oublier un caractère essentiel de ce système : toutes les inconnues prennent une valeur binaire, 0 ou 1.
Il faut donc rajouter des contraintes à la méthode de Gauss-Jordan, qui s'applique au moins pour des nombres réels.
Quelles sont ces contraintes ?
- Si une somme est nulle, alors tous les termes sont nuls.
ex : a+b+c+d=0 <=> a=b=c=d=0
- Si une somme de termes est égal au nombre de termes qui la composent, alors tous ces termes valent 1.
ex : a+b+c=3 <=> a=b=c=1
- Les valeurs nulles (les couleurs dont on a trouvé qu'elles n'existent pas) doivent être retenues, bizarrement, si l'on trouve que a=0, la méthode Jordanienne ne le prend pas en compte pour les autres équations.
Je pense que ce sont les seules contraintes.
Si on applique cette méthode, il faut donc faire comme suit :
- Créer une matrice dont le nombre de lignes est le nombre d'équations, avec 7 colonnes, les 6 premières pour chaque inconnue, la dernière pour la somme connue.
- A chaque fois qu'une nouvelle combinaison est tentée et analysée, on l'ajoute à la matrice (avec en dernière colonne la somme du nombre d'indices noirs et blancs)
- A chaque fois, résoudre la matrice grâce à la fonction rref(
- A chaque fois, appliquer les 2 contraintes citées plus haut. La première est simple, l'autre nécessite un comptage.
J'ai fait un prog qui permet de faire tout celà, par contre tout ne se passe pas comme prévu.
En effet, avec la méthode de résolution, on obtient parfois des -1
Que signifient ces -1 ? Comment les manipuler ? Je n'ai pas réussi à trouver.
De plus, pour pouvoir commencer le problème de placement, il ne faut pas attendre de connaître toutes les couleurs présentes dans la solution.
Il faut SUPPOSER.
On crée donc une liste d'existence qui contient les couleurs dont on sait qu'elles existent, mais il faut y rajouter des couleurs supposées.
Mais le problème est qu'il est illogique de mettre des couleurs totalement aléatoires, il faut que les couleurs supposées respectent les contraintes d'existence. Là non plus, je n'ai pas pu trouver.
Essayons d'imaginer le problème de placement, en considérant que tous les problèmes énoncés plus haut ont été résolus (je sais, c'est dur ^^) :
On a donc à l'issu de la résolution partielle du problème d'existence, une liste des 4 couleurs supposées présentes dans la solution.
Essayez d'imaginer une résolution des places en utilisant la méthode jordannienne. Impossible. Il faudrait une matrice 3D.
Voilà, j'imagine qu'il existe bien plus simple que ce que j'ai pu concevoir, mais bon au moins ce que j'ai fait ne tombera pas dans l'inconnu.