1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
|
let tour_cavalier (n,p) =
let rec appartient a = function
|[]->false
|h::q-> if h=a then true else appartient a q
in
(*debut de l'initialisation de matrice_cases_voisines_restantes *)
let cases_voisines_restantes (x,y) =
let add_couple (x,y) (x',y')= (x+x', y+y') in
let knight_moves = [(2,1);(1,2);(-1,2);(-2,1);(-2,-1);(-1,-2);(1,-2);(2,-1)] in
let position_valide (x,y) = 0<=x && x<n && 0<=y && y<p in
let rec aux = function
|[]->[]
|h::q->let case_a_tester = add_couple (x,y) h in
if position_valide case_a_tester then case_a_tester ::(aux q) else aux q
in
aux knight_moves
in
let matrice_cases_voisines_restantes =
let res=make_matrix n p [] in (*matrice n*p avec la liste des cases_voisines_restantes*)
for i=0 to n-1 do
for j=0 to p-1 do
res.(i).(j)<- cases_voisines_restantes (i,j)
done done;
res
in
(* fin de l'initialisation de matrice_cases_voisines_restantes *)
let rec solution cases_parcourues matrice_cases_voisines_restantes =
if list_length cases_parcourues = n*p then cases_parcourues (*cas d'arret*) else
let (x,y)= hd cases_parcourues in
match matrice_cases_voisines_restantes.(x).(y) with
|h::q-> matrice_cases_voisines_restantes.(x).(y) <- q (* on enleve la case que l'on va tester*) ;
if (appartient h cases_parcourues) then solution cases_parcourues matrice_cases_voisines_restantes (*si la case à tester a déjà été parcourue, ne pas la tester*)
else solution (h::cases_parcourues) matrice_cases_voisines_restantes
|[]-> (* s'il n'y a plus de cases à tester, alors (pour peu que ce soit possible), on enleve la derniere case parcourue, et on recommence (backtracking) ; on ne repassera pas par cette case là car elle a été supprimée des cases_voisines_restantes quand on est passé dessus la premiere fois *)
(match cases_parcourues with
|_::tl -> solution tl matrice_cases_voisines_restantes
|[] -> failwith "pas de solution")
in
solution [(0,0)] matrice_cases_voisines_restantes ;; |
Partager