Aller au contenu

TP — Tour de cavaliers

Travaux pratiques · MP2I · 2021-2022 · OCaml

Cours : Recherche par retour sur trace

Attention ce qu'on va faire ici n'est pas facile. Je vous demande d'abord de reprendre les deux exemples des huit reines puis du Sudoku du chapitre sur la force brute et de faire marcher le code ici dans un autre notebook. C'est en comprenant bien les exemples du cours qu'on peut construire la suite dessus.

On rappelle qu'un cavalier, aux échecs, se déplace en L : une case dans une direction, horizontale ou verticale, deux cases dans l'autre.

Dans ce TP on va résoudre le problème du cavalier d'Euler : étant donné un échiquier rectangulaire \(n \times m\) et une position initiale d'un cavalier en \((x_0, y_0)\) :

  • existe-t-il une succession de mouvements du cavalier permettant de visiter chaque case de l'échiquier une fois et une seule ? On parle de tour du cavalier.
  • existe-t-il un tour du cavalier qui permette avec un mouvement supplémentaire de revenir au point de départ \((x_0, y_0)\) ? On parle de tour fermé du cavalier.

On va représenter un échiquier par le type OCaml :

type echiquier = int option array array
  • L'idée est qu'une valeur None signifie que la case n'a pas été visitée.
  • Une valeur Some k signifie que le cavalier a visité cette case en \(k\)-ème position dans son tour, en commençant à numéroter à 1 pour la case initiale.

Exemple de numérotation finale d'un tour fermé d'un échiquier 6x6 :

 1| 6|15|18|35|26|
 8|19|36|25|14|17|
 5| 2| 7|16|27|34|
20| 9| 4|31|24|13|
 3|30|11|22|33|28|
10|21|32|29|12|23|

On va faire le choix d'énumérer par colonnes, ce qui permet d'écrire e.(x).(y) pour avoir le point de coordonnées (x,y). Ainsi, l'échiquier

  |  |  |
 1| 2| 3|

sera représenté par la valeur

[| [| None; Some 1 |]; [| None; Some 2 |]; [| None; Some 3 |] |]

On donne les fonctions suivantes :

let libre (e:echiquier) (x,y) : bool =
    (* vérifie si on peut se déplacer en (x,y) *)
    e.(x).(y) = None

let dans_echiquier (e:echiquier) (x,y) : bool =
    (* vérifie que les coordonnées (x,y) sont valides pour cet échiquier *)
    let w = Array.length e in
    let h = Array.length e.(0) in
    0 <= x && x < w && 0 <= y && y < h

let valide (e:echiquier) (x,y) : bool =
    (* vérifie que (x,y) est une coordonnée valide et que la case est libre *)
    dans_echiquier e (x,y) && libre e (x,y)

let deplacements (x,y) : (int * int) list =
    (* renvoie les 8 déplacements possibles d'un cavalier en (x,y)
       quitte à avoir des coordonnées invalides *)
    [ (x-2,y-1); (x-2,y+1);
      (x-1,y-2); (x-1,y+2);
      (x+1,y-2); (x+1,y+2);
      (x+2,y-1); (x+2,y+1) ]

Rappel List.filter permet de ne sélectionner dans une 'a list que les éléments vérifiant un prédicat 'a -> bool. Plus d'info ici : https://ocaml.org/api/List.html#1_Listsearching

List.filter (fun x -> x mod 2 = 1) [0;1;2;3;4;5]

- : int list = [1; 3; 5]

Question 1

Compléter la fonction deplacements_valides :

let deplacements_valides (e:echiquier) (x,y) : (int * int) list =
    (* renvoie les déplacements valides depuis (x,y) dans e *)
    (* on pourra utiliser List.filter *)
Corrigé 
let deplacements_valides (e:echiquier) (x,y) : (int * int) list =
    List.filter (fun (x,y) -> valide e (x,y))
        (deplacements (x,y))

Pour la fonction suivante, on aura besoin de s'assurer que les nombres sont affichés avec deux chiffres. Pour cela, on peut écrire %2d dans le format de Printf.printf.

Printf.printf "|%d|%d|\n|%2d|%2d|\n" 3 64 3 64;
flush stdout (* nécessaire pour être sûr de faire l'affichage *)

|3|64|
| 3|64|

Question 2

On vous demande d'afficher l'échiquier sous la forme suivante :

  | 5|12|17|22|
13|18|23| 6|11|
 4| 1| 8|21|16|
19|14| 3|10| 7|
 2| 9|20|15|  |

avec un alignement des | et des cases vides si on n'est pas passé dessus.

Pour vous simplifier la vie, vous pourrez faire un flush stdout avant la fin de votre fonction. flush c'est la chasse d'eau, ça envoie vraiment tous les print sur l'affichage.

let print_echiquier (e:echiquier) : unit =
    (* Affiche l'échiquier *)
Corrigé 
let print_echiquier (e:echiquier) : unit =
    let w = Array.length e in
    let h = Array.length e.(0) in
    for y = 0 to h-1 do
        for x = 0 to w-1 do
            match e.(x).(y) with
            | None -> Printf.printf "  |"
            | Some k -> Printf.printf "%2d|" k
        done; print_newline ()
    done;
    flush stdout

Pour chercher un tour, on va adapter la méthode du Sudoku : une exception Solution et une fonction auxiliaire qui effectue des essais de déplacement en lançant Solution si on a trouvé un tour.

Le principe va donc être celui-là quand on appelle aux n (x,y) pour dire que (x,y) est le n-ième mouvement du cavalier :

  • On marque Some n dans l'échiquier à cette case.
  • Si n marque le dernier mouvement (facile avec le nombre de cases), on lance Solution.
  • Sinon, on itère aux (n+1) sur tous les déplacements valides.
    • Soit on a une Solution lancée pendant cette itération et donc on sort.
    • Soit c'est que ce déplacement ne permet pas d'aboutir à une solution, donc on repasse à None la case (x,y).

Question 3

Compléter la fonction tour :

exception Solution

let tour w h (x0, y0) : echiquier =
    let e = Array.make_matrix w h None in
    try
        let rec aux n (x,y) =
            failwith "C'est à vous !"
        in
        aux 1 (x0,y0);
        raise Not_found (* pas de solution ! *)
    with Solution -> e (* on renvoie e avec la solution *)

print_echiquier (tour 5 5 (0,0)) (* doit permettre d'afficher le tour *)

Question 4

Compléter la fonction tour_ferme :

let tour_ferme w h (x0,y0) : echiquier =
    (* Cherche un tour fermé *)
    failwith "C'est à vous !"
Corrigé (fichier TP12_cavalier.ml)

Le corrigé de l'auteur est le programme TP12_cavalier.ml. Ses fonctions tour et tour_ferme prennent directement l'échiquier en paramètre et animent la recherche avec la bibliothèque Graphics ; il contient aussi les fonctions tous_tour et tous_tour_ferme qui énumèrent tous les tours (première extension ci-dessous).

open Graphics

type echiquier = int option array array

let libre echiquier (x, y) =
    (* vérifie si on peut se déplacer en (x,y) *)
    echiquier.(x).(y) = None

let dans_echiquier echiquier (x, y) =
    let w = Array.length echiquier in
    let h = Array.length echiquier.(0) in
    0 <= x && x < w && 0 <= y && y < h

let valide echiquier (x, y) =
    dans_echiquier echiquier (x, y)
    && libre echiquier (x, y)

let deplacements (x, y) =
    [ (x-2,y-1);(x-2,y+1);
      (x-1,y-2);(x-1,y+2);
      (x+1,y-2);(x+1,y+2);
      (x+2,y-1);(x+2,y+1) ]

let deplacements_valides echiquier (x, y) =
    List.filter (valide echiquier) (deplacements (x,y))

let rec accumule f l =
    match l with
    | [] -> []
    | t::q -> f t @ accumule f q

let print_echiquier echiquier =
    let w = Array.length echiquier in
    let h = Array.length echiquier.(0) in
    for j = 0 to h-1 do
        for i = 0 to w-1 do
            match echiquier.(i).(j) with
            | None -> print_string "  |"
            | Some d ->  Printf.printf "%2d|" d
        done;
        print_newline ()
    done

exception Trouve of int * int

let cherche echiquier n =
    let w = Array.length echiquier in
    let h = Array.length echiquier.(0) in
    try
        for i = 0 to w - 1 do
            for j = 0 to h - 1 do
                if echiquier.(i).(j) = Some n
                then raise (Trouve (i,j))
            done
        done;
        raise Not_found
    with Trouve (i,j) -> (i,j)

let rec chemin echiquier n =
    let w = Array.length echiquier in
    let h = Array.length echiquier.(0) in
    if n = w * h
    then []
    else cherche echiquier n :: chemin echiquier (n+1)

let z = 50

let affiche_echiquier e =
    let w = Array.length e in
    let h = Array.length e.(0) in
    for i = 0 to h  do
        moveto 0 (z*i);
        lineto (z*w) (z*i)
    done;
    for i = 0 to w  do
        moveto (z*i) 0;
        lineto (z*i) (z*h)
    done;
    set_text_size (20);
    try
        for i = 1 to w*h - 1 do
            let x1, y1 = cherche e i in
            let x2, y2 = cherche e (i+1) in
            moveto (z*x1+z/2) (z*y1+z/2);
            draw_string (Printf.sprintf "%d" i);
            lineto (z*x2+z/2) (z*y2+z/2)
        done
    with Not_found -> ()

exception Solution

let tour echiquier (x0,y0) =
    try
        let w = Array.length echiquier in
        let h = Array.length echiquier.(0) in
        let rec aux n (x,y) =
            echiquier.(x).(y) <- Some n;
            clear_graph ();
            affiche_echiquier echiquier;
            Unix.sleepf 0.1;
            if n = w * h
            then raise Solution;
            List.iter
                (aux (n+1))
                (deplacements_valides echiquier (x,y));
            echiquier.(x).(y) <- None
        in aux 1 (x0,y0)
    with Solution -> ()

let tour_ferme echiquier (x0,y0) =
    try
        let w = Array.length echiquier in
        let h = Array.length echiquier.(0) in
        let rec aux n (x,y) =
            echiquier.(x).(y) <- Some n;
            clear_graph ();
            affiche_echiquier echiquier;
            Unix.sleepf 0.2;
            let ld = deplacements (x,y) in
            if n = w * h && List.mem (x0,y0) ld
            then raise Solution;
            List.iter
                (aux (n+1))
                (deplacements_valides echiquier (x,y));
            echiquier.(x).(y) <- None
        in aux 1 (x0,y0)
    with Solution -> ()

let dup e =
    let w = Array.length e in
    let h = Array.length e.(0) in
    let e' = Array.make_matrix w h None in
    for i = 0 to w - 1 do
        for j = 0 to h - 1 do
            e'.(i).(j) <- e.(i).(j)
        done
    done;
    e'

let tous_tour echiquier (x0,y0) =
        let w = Array.length echiquier in
        let h = Array.length echiquier.(0) in
        let rec aux n (x,y) =
            echiquier.(x).(y) <- Some n;
            let l = if n = w * h
            then [ dup echiquier ]
            else
                List.fold_left (@) [] (List.map
                (aux (n+1))
                (deplacements_valides echiquier (x,y))) in
            echiquier.(x).(y) <- None;
            l
        in aux 1 (x0,y0)

let tous_tour_ferme echiquier (x0,y0) =
        let w = Array.length echiquier in
        let h = Array.length echiquier.(0) in
        let rec aux n (x,y) =
            echiquier.(x).(y) <- Some n;
            let ld = deplacements (x,y) in
            let l = if n = w * h && List.mem (x0,y0) ld
            then [ dup echiquier ]
            else
                List.fold_left (@) [] (List.map
                (aux (n+1))
                (deplacements_valides echiquier (x,y))) in
            echiquier.(x).(y) <- None;
            l
        in aux 1 (x0,y0)

let _ =
    let w = int_of_string Sys.argv.(1) in
    let h = int_of_string Sys.argv.(2) in
    let echiquier = Array.make_matrix w h None in

    (*
    let solutions = tous_tour_ferme echiquier (0,0) in
    List.iter (fun e -> print_echiquier e; print_newline())  solutions;
    Printf.printf "%d\n" (List.length solutions)
    *)

    open_graph " ";
    tour echiquier (0,0);
    (*
    affiche_echiquier echiquier;
    *)
    wait_next_event [Key_pressed]
    (*
    print_echiquier echiquier
    *)

Deux propositions d'extensions :

  • énumérer tous les tours pour un petit nombre de cases ;
  • trouver des parcours qui forment sur l'échiquier des carrés magiques ou pseudo-magiques. Rappel : un carré est pseudo-magique si la somme des valeurs sur les lignes et les colonnes est la même, un carré est magique s'il est pseudo-magique et a la même somme sur les diagonales.

Façon Python avec une liste :

for x in l do
    f x
done

en OCaml :

List.iter f l

List.iter print_int [1;2;3];
print_newline(); flush stdout

123

Sinon on peut la convertir en tableau si elle n'est pas trop grande (ici \(\le 8\) déplacements) :

let a = Array.of_list l in
for i = 0 to Array.length a - 1 do
    (* Ici on a a.(i) c'est le ieme de l *)
done