Le solitaire

Le jeu du solitaire est un jeu (de réflexion) qui se joue seul; le but du jeu est de ne rester qu'avec un seul pion sur l'échiquier; chaque pion peut sauter par dessus un autre pion à condition que la case d'arrivée soit vide; dans ce cas le pion par dessus lequel on a sauté disparaît. Voici l'échiquier du jeu :

+-----------+

¦ O ¦ O ¦ O ¦

+---+---+---¦

¦ O ¦ O ¦ O ¦

+-------+---+---+---+-------+

¦ O ¦ O ¦ O ¦ O ¦ O ¦ O ¦ O ¦

+---+---+---+---+---+---+---¦

¦ O ¦ O ¦ O ¦ ¦ O ¦ O ¦ O ¦

+---+---+---+---+---+---+---¦

¦ O ¦ O ¦ O ¦ O ¦ O ¦ O ¦ O ¦

+-------+---+---+---+-------+

¦ O ¦ O ¦ O ¦

+---+---+---¦

¦ O ¦ O ¦ O ¦

+-----------+

Cet échiquier peut se représenter en mémoire par un tableau de 2 dimensions de 7 sur 7; il faut déjà choisir un échiquier de 9 sur 9, pour prévoir une case supplémentaire sur les bords, car si on saute vers l'extérieur, on peut tomber sur n'importe quelle valeur qui se trouve en mémoire; par contre si on a réservé une case, on tombe sur cette case qui aura une valeur indiquant qu'on ne peut pas y sauter. Cette technique sera aussi utilisée dans le jeu d'othello.

Etudions en quelques lignes ce programme :

- on va avoir un échiquier de 9 sur 9, mais en une dimension, donc un tableau linéaire de 81 cases; ceci est fait par souci de rapidité

- pour chaque pion (ou presque) on a quatre directions possibles pour sauter

- on peut sauter si la case jointe est occupée par un pion ET si la case suivante est vide

- une fois qu'on a joué un pion, on fait un appel récursif et on commence la recherche du prochain pion à jouer à partir de la première case

- nous allons créer plusieurs procédures :

- l'initialisation de l'échiquier (procédure init_tab;)

- l'affichage de l'échiquier (procédure aff_tab;)

- une fonction pour déterminer quel est le pion qui doit jouer

- la procédure représentant le coeur du programme, la récursivité

Nous allons étudier en détail deux procédures :

- la fonction pion_qui_doit_jouer : elle a deux paramètres :

- dernier_pion,qui indique quel est le dernier pion qui a sauté

- last_dir, qui indique quelle est la dernière direction dans la quelle le dernier pion a sauté; si le dernier pion peut sauter dans plusieurs directions et il ne les a pas toutes essayées, alors il les essaie jusqu'au bout, sinon un autre pion est choisi

- pour déterminer quel pion doit jouer, un balayage de l'échiquier a lieu et ce jusqu'à le trouver ou jusqu'à la fin de l'échiquier, à savoir la case numéro 68 dans le tableau, qui correspond au dernier pion de l'échiquier pouvant sauter.

- la procédure "joue",qui représente le programme :

- elle n'a pas de paramètres car il faut essayer d'éviter de perdre du temps avec l'empilement et le désempilement de variables pendant l'exécution, vu le nombre élevé de possibilités

- le point d'arrêt est atteint quand on a fait 32 coups, dans ce cas on initialise la variable "trouve" à true et ensuite on ne cherche plus d'autre solution, mais on affiche les sauts et on sort.

- on simule chaque coup par des remplissages du tableau avec des PION et avec des "VIDE", on rappelle la procédure, et ensuite on annule le coup pour essayer une autre possibilité.

Le programme a été testé sur un K6-II 350 et il a calculé 7,4 millions de coups avant de trouver la première solution. Nous avons choisi de l'arrêter délibérément après la première solution, mais vous pouvez le laisser continuer à rechercher d'autres solutions en vous inspirant du programme concernant le saut du cavalier, où les coups sont sauvegardés dans des fichiers distincts.

Voici enfin le programme :

const INCONNU = 5;
 PION = 3;
 VIDE = 0;
 
 d: array[0..3] of integer = (-9, 1, 9, -1);
 
type tab = array[0..80] of byte;
 tab_n = array[1..32] of tab;
 
var t: tab;
 plateaux: tab_n;
 numero_coup: integer;
 nb_coups: longint;
 trouve: boolean;
 
procedure init_tab;
var x, y: integer;
begin
 for x := 0 to 8 do
 for y := 0 to 8 do
 t[x * 9 + y] := INCONNU;
 for y := 1 to 7 do
 for x := 3 to 5 do
 begin
 t[y * 9 + x] := PION;
 t[x * 9 + y] := PION;
 end;
 t[4 * 9 + 4] := VIDE;
end;
 
function pion_qui_doit_jouer(dernier_pion: integer;
 var last_dir: integer): integer;
var i, x, y, k1, k2: integer;
begin
 x := dernier_pion mod 10 - 1;
 y := dernier_pion div 10;
 while (y * 10 + x < 78) do
 begin
 inc(x);
 if (x = 8) then begin x := 0; inc(y); end;
 for i := last_dir to 3 do
 begin
 k1 := y * 9 + x; k2 := d[i];
 if (t[k1] = PION) then
 if (t[k1 + k2] = PION) then
 if (t[k1 + 2 * k2] = VIDE) then
 begin
 last_dir := i;
 pion_qui_doit_jouer := y * 10 + x;
 exit;
 end;
 end;
 last_dir := 0;
 end;
 pion_qui_doit_jouer := 0;
end;
 
procedure joue(numero_coup: integer; var trouve: boolean);
var i, x, y, k1, k2, pion_qui_joue, dernier_pion_qui_a_joue, last_dir, k: integer;
begin
 if (numero_coup = 32) then
 begin
 move(t, plateaux[numero_coup], sizeof(tab));
 trouve := true;
 if Form1.CheckBox1.Checked then Printer.BeginDoc; //Si on veut imprimer
 for k := 1 to 32 do afficher_coup(k);
 if Form1.CheckBox1.Checked then Printer.EndDoc; //Si on veut imprimer
 exit;
 end;
 last_dir := 0;
 dernier_pion_qui_a_joue := 0;
 inc(nb_coups);
 if nb_coups mod 100000 = 0 then
 begin form1.edit1.text := inttostr(nb_coups); form1.edit1.refresh; end;
 repeat
 pion_qui_joue := pion_qui_doit_jouer(dernier_pion_qui_a_joue, last_dir);
 dernier_pion_qui_a_joue := pion_qui_joue;
 if (dernier_pion_qui_a_joue > 0) then
 begin
 move(t, plateaux[numero_coup], sizeof(tab));
 i := last_dir;
 inc(last_dir);
 y := pion_qui_joue div 10;
 x := pion_qui_joue mod 10;
 k1 := y * 9 + x; k2 := d[i];
 t[k1 + 2 * k2] := PION;
 t[k1 + k2] := VIDE;
 t[k1] := VIDE;
 joue(numero_coup + 1, trouve);
 move(plateaux[numero_coup], t, sizeof(tab));
// l'instruction suivante disparaîtra quand on décidera de chercher toutes les solutions
 if trouve then exit;
 end;
 until (pion_qui_joue = 0);
end;

Télécharger le code source Delphi