I129. Les chemins du fou Imprimer
I. Trajets optimaux

calculator_edit.png  

 

I129

 


Trouver le plus court chemin qui permet à un fou de visiter toutes les cases blanches d'un échiquier 8 x 8 dans les trois cas suivants:
Q1 la distance parcourue totale D est la plus courte possible.
Q2 le nombre N de mouvements est le plus petit possible.
Q3 le produit N.D est le plus petit possible.
Nota: un mouvement du fou  est un segment de droite qui lui permet d'aller de la case (i,j) √† la case (i + k,j + k) et de visiter les k cases (i + 1, j + 1), (i + 2, j + 2)...(i + k, j + k).
Dans l'exemple ci-contre, le fou se d√©place en un mouvement de la case (3,2) √† la case (7,6) et visite les quatre cases ('4,3), (5,4), (6,5) et (7,6). La distance parcourue est √©gale √† 4‚ąö2  .

 



 Solution



pdfJean Moreau de Saint Martin a parfaitement ma√ģtris√© les chemins du fou...