Bonjour,  
Je recherche un programmeur qui pourrait m’aider a faire tourner un ptit programme au sujet d’un jeu.  
Ce jeu se nomme KHALOU et est disponible gratuitement sur Itunes pour Iphone et Ipad.  
https://itunes.apple.com/fr/app/khalou/id589404904?mt=8
Je vous laisse en lire les règles. Voici mes requêtes :  
Il existe pour ce jeu 2^16 = 65536 positions différentes.  
Les jetons de ce jeu peuvent se retourner de différentes façons. Je cherche un petit script a faire tourner qui pourrait me donner :  
*Pour chacune des positions : le nombre de retournement minimum pour rendre le damier du jeu tout blanc (le but du jeu). Cela est toujours faisable en 5 retournements minimum (démontré via théorie des groupes).
*Trouver ainsi le nombre totale de positions résolvables en : 1, 2, 3, 4 et 5 retournements minimum.
 
Qui pourrait m’aider pour cette programmation ?  
 
Merci  
 
Dan
 

C'est pas clair,  
 
Tu dis :

 
puis :

Je souhaite connaitre pour chacune des 64000 positions le nombre minimum de retournements necessaires. Je pense qu'il faut lire la regle du jeu

Pour info j'ai pas trouvé la règle du jeu.

Le Khalou est un jeu de plateau 4X4 comportant des jetons bifaces (noires et blanches).
 
Le principe du jeu est le suivant :  
 
 *Le jeu débute par une répartition aléatoire des jetons (et de leurs faces visibles) sur le plateau
 *Le but est de parvenir en une succession de mouvements différents à un plateau de jeu tout blanc (tous les jetons avec leurs faces visibles blanches).
 
 *2 Types de mouvements principaux sont autorisés :  
 
  *Retournement des faces visibles sur une ligne, colonne, ou grande diagonale. Dans ce cas chacun des 4 jetons sur toute la ligne, colonne ou diagonale sélectionnée voit sa face visible changer de couleur.
 
 
 
 
  *Retournement des faces visibles sur « un coude » : le coude est une position en « L » impactant 3 jetons dans n’importe quelle direction. Chacun des 3 jetons sélectionnés par ce retournement voit ainsi sa face visible changer de couleur.
 
 
Le but du jeu du Khalou est donc de rendre blancs tous les jetons uniquement grâce à ces types de retournements. Cela est toujours possible en 5 retournements maximum.

pour moi il y a 46 mouvements possibles dont 36 mouvements en coudes.

J'avais mal lu les règles sur les coudes (en forme de L, j'étais parti sur des coudes de 4 cases, et toujours en coin).
Il y a 36 coudes (1 coude par coin, 2 coudes par case du bord qui n'est pas un coin, et 4 coudes par case centrale) 1*4 + 2*8 + 4*4 = 36
On voit a la base que il y a 4 + 4 + 2 + 34 = 46 mouvements distincts donc peut procéder en partant d'un damier blanc et en effectuant les 44 mouvements pour les solutions en 1 coup, puis partant des solutions en un coup, les 45 mouvements (on ne fait pas deux fois de suite le même mouvement, car cela s'annule) pour les solutions en deux coups (pas déjà trouvées dans les solutions en un coup) etc.  
A+,

46 positions resolvables en 1 coup
46*45/2 positions resolvables en 2 coups

Oui, 36, pas 34 pour les coudes, si j'arrive plus à faire une addition correctement...
au plus 188628750 opérations de transformation à effectuer, ça doit être possible dans un temps correct.
Je regarderais si ça prends pas trop de temps en perl ce soir, parce que je suis offline d'ici la.
A+,

Pour moi le plus simple et rapide serait de representer chaque position par un nombre de 16 chiffres composé de 0 ou de 1 (0 = blanc et 1 = noir) et de faire tourner toutes les  posibilités

Genial Gilou, merci  

*Il existe 2^16-1 positions = 65.535. En effet on ne compte pas la position avec jetons tout blancs.
*On peut représenter chaque position par un nombre de 16 chiffres composé de 0 ou de 1 (0 = blanc et 1 = noir) et faire tourner toutes les possibilités. En ne comptant pas celle composée de 16 chiffres 0.
*Il existe 46 mouvements possibles.  Chaque mouvement permet de changer 3 ou 4 chiffres du nombre désignant la position initial. Par exemple si les couleurs des 16 jetons sont représentées dans le chiffres de gauche a droite et de haut en bas alors le retournement de la ligne du haut change les 4 premiers chiffres du nombre a 16 chiffres représentant la position d’origine.
Ainsi si la position d’origine est : 1000.1100.0001.1010 retourner la première ligne aboutit à la position notée : 0111.1100.0001.1010
Ou si la position d’origine est : 1000.1100.0001.1010 retourner le premier coude aboutit à la position notée : 0100.0100.0001.1010
Le but étant avec un minimum de retournements d’aboutir au chiffre : 0000.0000.0000.0000
*Il suffit alors de faire tourner les 65.535 positions et pour chacune d’elles de modifier le chiffre de cette position avec les 46 puis 46^2 puis 46^3 puis 46^4 retournements possibles.  
Quand le chiffre 0000.0000.0000.0000 apparait (cela arrivera plusieurs fois souvent) on note le nombre de retournements minimum utilisés. Sinon c’est qu’il eut fallu 5 retournements.  
Ce n’est de loin pas le meilleur algorithme mais selon moi le plus simple.  
 
D’autres idées ????  
 

#!/usr/bin/perl
 
use strict;
use warnings;
 
my @boards;
 
# initialisation des boards
for (my $i = 0; $i < 2**16; ++$i) {
  $boards[$i] = [0, 0, 0];
  # premier champ: nombre de mouvement pour revenir à une solution
  # second champ: mouvement à effectuer
  # troisième champ: résultat après le mouvement
}
 
my @moves = (15, 19, 35, 38, 49, 50, 70, 76, 98, 100, 140, 196, 200, 240, 304, 560, 608, 
         784, 800, 1120, 1216, 1568, 1600, 2240, 3136, 3200, 3840, 4369, 4680, 4864, 
         8738, 8960, 9728, 12544, 12800, 17476, 17920, 19456, 25088, 25600, 33825, 
         34952, 35840, 50176, 51200, 61440);
 
foreach (@moves) {
  $boards[$_]->[0] = 1;
  $boards[$_]->[1] = $_;
}
 
for my $level (1..4) {
  for (my $i = 0; $i < 2**16; ++$i) {
    if ($boards[$i]->[0] == $level) {
      foreach (@moves) {
        my $result = $i^$_;
        unless ($result == 0 or $boards[$result]->[0]) {
          $boards[$result]->[0] = $level+1;
          $boards[$result]->[1] = $_;
          $boards[$result]->[2] = $i;
        }
      }
    }
  }
}
# @boards contient maintenant toute l'information nécessaire
 
my @count = (0, 0, 0, 0, 0, 0);
for (my $i = 0; $i < 2**16; ++$i) {
  ++$count[$boards[$i]->[0]];
}
 
foreach (0..5) {
  print "Nb de positions de depart solvables en un minimum de $_ coups: $count[$_]\n";
}

 
C'est peut être optimisable, mais même sur ma vieille bécane qui n'a que 2 Go de mémoire et un pentium4, ça ne prend que qques secondes, donc ça vaut pas trop la peine de chercher à optimiser cela.
 
A+,

Le truc qui a pris le plus de temps, c'est de déterminer tous les mouvements pour générer @moves.
Je me suis servi de deux fonctions auxiliaires qui me permettent de lire et imprimer un board:
 

# en entrée un nombre, en sortie, le board correspondant
sub printboard {
  print join("\n", (reverse(unpack("B16", pack("n", shift))) =~ m/..../g)), "\n";
}
 
# en entrée un board, en sortie, le nombre correspondant
sub readboard {
  my $input = shift;
  my $str = reverse($input);
  $str =~ tr/01//cd;
  die "Error: incorrect board:\n  $input" unless (length($str) == 16);
  unpack("n", pack("B16", $str));
}

 
et d'une liste des 64 boards représentant un mouvement:
 

my @boardmoves = (
#lignes
"
1111
0000
0000
0000", #1
"
0000
1111
0000
0000", #2
"
0000
0000
1111
0000", #3
"
0000
0000
0000
1111", #4
#colonnes
"
1000
1000
1000
1000", #5
"
0100
0100
0100
0100", #6
"
0010
0010
0010
0010", #7
...
"
0000
0000
0011
0010", #44
"
0000
0010
0110
0000", #45
"
0000
0000
0110
0010", #46
);

(on peut retrouver cette liste en appliquant printboard aux éléments de @moves)
 
Le seul truc qu'il fallait voir, c'est qu'on pouvait coder tout board initial comme un entier entre 0 et 65535, par sa représentation binaire, tout mouvement comme un entier dans cet intervalle aussi, et que partant d'un board b, l'opération qui consiste à lui appliquer un mouvement m revient a faire le xor de b et m.
 
A+,

A partir du code donné, on peut facilement écrire une routine résolvant n'importe quelle position de départ en un minimum de mouvements:

#!/usr/bin/perl
 
use strict;
use warnings;
 
my @boards;
 
# initialisation des boards
for (my $i = 0; $i < 2**16; ++$i) {
  $boards[$i] = [0, 0, 0];
  # premier champ: nombre de mouvement pour revenir à une solution
  # second champ: mouvement à effectuer
  # troisième champ: résultat après le mouvement
}
 
my @moves = (15, 19, 35, 38, 49, 50, 70, 76, 98, 100, 140, 196, 200, 240, 304, 560, 608, 
         784, 800, 1120, 1216, 1568, 1600, 2240, 3136, 3200, 3840, 4369, 4680, 4864, 
         8738, 8960, 9728, 12544, 12800, 17476, 17920, 19456, 25088, 25600, 33825, 
         34952, 35840, 50176, 51200, 61440);
 
foreach (@moves) {
  $boards[$_]->[0] = 1;
  $boards[$_]->[1] = $_;
}
 
for my $level (1..4) {
  for (my $i = 0; $i < 2**16; ++$i) {
    if ($boards[$i]->[0] == $level) {
      foreach (@moves) {
        my $result = $i^$_;
        unless ($result == 0 or $boards[$result]->[0]) {
          $boards[$result]->[0] = $level+1;
          $boards[$result]->[1] = $_;
          $boards[$result]->[2] = $i;
        }
      }
    }
  }
}
 
# en entrée un nombre, en sortie, le board correspondant
sub printboard {
  print join("\n", (reverse(unpack("B16", pack("n", shift))) =~ m/..../g)), "\n";
}
 
# en entrée un board, en sortie, le nombre correspondant
sub readboard {
  my $input = shift;
  my $str = reverse($input);
  $str =~ tr/01//cd;
  die "Error: incorrect board:\n  $input" unless (length($str) == 16);
  unpack("n", pack("B16", $str));
}
 
sub resoudre {
  my $b = readboard(shift);
  my $mvt = 0;
  print "Depart:\n\n";
  while ($b != 0){
    printboard($b);
    print "\n";
    ++$mvt;
    print "Mouvement $mvt:\n\n";
    printboard($boards[$b]->[1]);
    print "\n";
    $b = $boards[$b]->[2];
    print ($b?"Resultat:\n\n":"Termine\n\n" );
  }
}
 
my $board = "
0101
1010
1100
0011";
 
resoudre($board);

Ce qui donne:

 
 
A+,

Ca semble super, je vais regarder.
 
merci bcp