{"cells":[{"metadata":{"trusted":false},"cell_type":"code","source":"let pb_n_reines n =\n   let t=Array.make n (-1) (* positions des reines : t.(i) est la position de la reine de la ligne i *)\n       and solution = ref false in\n   let placement_possible i j = (* vérifie si, à la vue des lignes 0 à i-1,\n                               on peut mettre la reine numéro i en colonne j l'on peut*)\n      let b= ref true in\n      for k=0 to i-1 do\n         b:=(!b)&&(t.(k)<>j);\n         if j-i+k>=0 then b:=(!b)&&(t.(k)<>j-i+k);\n         if i+j-k<=n-1 then b:=(!b)&&(t.(k)<>j+i-k)\n       done;\n       !b in\n   let rec aux i = \n      if (i=n)||(!solution) then solution:=true\n      else \n         for j=0 to n-1 do \n            if not(!solution) && placement_possible i j then begin t.(i) <- j; aux (i+1) end\n            done;\n    in aux 0;\n    if not(!solution) then failwith \"pas de solution\";\n    t;;","execution_count":33,"outputs":[{"output_type":"execute_result","execution_count":33,"data":{"text/plain":"\nval pb_n_reines : int -> int array = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"pb_n_reines 5;;","execution_count":35,"outputs":[{"output_type":"execute_result","execution_count":35,"data":{"text/plain":"\n- : int array = [|0; 2; 4; 1; 3|]"},"metadata":{}}]},{"metadata":{"trusted":true},"cell_type":"code","source":"let possible_ligne g i k = \n   let b=ref true in\n   for j=0 to 8 do\n      if g.(i).(j)=k then b:=false\n    done;\n    !b;;","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"let possible_colonne g j k =\n   let b = ref true in\n   for i=0 to 8 do\n      if g.(i).(j)=k then b:=false\n    done;\n    !b;;","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"let possible_bloc g i j k =\n   let b = ref true and i0=i/3 and j0=j/3 in\n   for r0=0 to 2 do\n      for r1=0 to 2 do\n         if g.(3*i0+r0).(3*j0+r1)=k then b:=false\n        done;\n    done;\n    !b;;","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"let possible g i j k =\n   (possible_ligne g i k) && (possible_colonne g j k) && (possible_bloc g i j k);;","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"let completer g =\n   let solution = ref false in\n   let rec aux i j = \n      if not(!solution) then\n         if i=9 then solution := true\n         else \n            if j=9 then (aux (i+1) 0)\n            else\n               if (g.(i).(j))>0 then (aux i (j+1))\n               else\n                  for k=1 to 9 do\n                     if possible g i j k then begin\n                        g.(i).(j) <- k;\n                        aux i (j+1);\n                        if not(!solution) then g.(i).(j) <- 0\n                       end\n                   done\n    in aux 0 0;\n    if not(!solution) then failwith \"pas de solution\";\n    g;;","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"let \ng1=[| [| 5; 0; 0; 0; 0; 0; 0; 0; 4|] ; [| 3; 2; 0; 6; 0; 0; 0; 0; 9|] ; [| 0; 0; 0; 2; 0; 0; 8; 3;\n0|] ; [| 2; 0; 0; 0; 8; 0; 0; 4; 0|] ; [| 0; 4; 0; 0; 2; 0; 9; 0; 5|] ; [| 0; 0; 8; 0; 0; 7; 0; 2;\n1|] ; [| 0; 0; 0; 0; 5; 0; 7; 1; 0|] ; [| 0; 0; 0; 0; 6; 0; 0; 9; 0|] ; [| 0; 0; 0; 8; 0; 9; 0; 0;\n2|] |];;","execution_count":null,"outputs":[]},{"metadata":{"trusted":true},"cell_type":"code","source":"completer g1;;","execution_count":null,"outputs":[]},{"metadata":{"trusted":false},"cell_type":"code","source":"type echiquier = { damier : (int*int) array array ; mutable nbre_cases_vides : int };;","execution_count":2,"outputs":[{"output_type":"execute_result","execution_count":2,"data":{"text/plain":"\ntype echiquier = {\n  damier : (int * int) array array;\n  mutable nbre_cases_vides : int;\n}"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let deplacements = [(2,1); (2,-1); (-2,1); (-2,-1); (1,2); (-1,2); (1,-2); (-1,-2)];;","execution_count":3,"outputs":[{"output_type":"execute_result","execution_count":3,"data":{"text/plain":"\nval deplacements : (int * int) list =\n  [(2, 1); (2, -1); (-2, 1); (-2, -1); (1, 2); (-1, 2); (1, -2); (-1, -2)]"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let possible e (i,j) (a,b) = \n   let d=e.damier in let n=Array.length d in\n   (i+a>=0)&&(i+a<n)&&(j+b>=0)&&(j+b<n)&&((d.(i+a).(j+b)=(-1,-1)));;","execution_count":4,"outputs":[{"output_type":"execute_result","execution_count":4,"data":{"text/plain":"\nval possible : echiquier -> int * int -> int * int -> bool = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let cases_atteignables e (i,j) = \n   let rec aux l d = match l with\n      | [] -> d\n      | (a,b)::suite -> aux suite (if possible e (i,j) (a,b) then (i+a,j+b)::d else d)\n    in aux deplacements [];;","execution_count":5,"outputs":[{"output_type":"execute_result","execution_count":5,"data":{"text/plain":"\nval cases_atteignables : echiquier -> int * int -> (int * int) list = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"type solution = None | Solution of (int*int) array array;;","execution_count":6,"outputs":[{"output_type":"execute_result","execution_count":6,"data":{"text/plain":"\ntype solution = None | Solution of (int * int) array array"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let rec retour_sur_trace e (i,j) l = \n   if e.nbre_cases_vides <=1 then Solution(e.damier)\n   else match l with \n      |[]-> None\n      | (a,b)::q -> \n         e.damier.(i).(j) <- (a,b); e.nbre_cases_vides <- e.nbre_cases_vides-1;\n         let r=retour_sur_trace e (a,b) (cases_atteignables e (a,b)) in \n            if r=None then \n               begin \n               e.damier.(i).(j)<-(-1,-1); \n               e.nbre_cases_vides <- e.nbre_cases_vides+1;\n               retour_sur_trace e (i,j) q\n               end\n            else r;;","execution_count":7,"outputs":[{"output_type":"execute_result","execution_count":7,"data":{"text/plain":"\nval retour_sur_trace : echiquier -> int * int -> (int * int) list -> solution =\n  <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"let cavalier n = let echiquier = {damier = Array.make_matrix n n (-1,-1); nbre_cases_vides = n*n} in\n   retour_sur_trace echiquier (0,0) (cases_atteignables echiquier (0,0));;","execution_count":8,"outputs":[{"output_type":"execute_result","execution_count":8,"data":{"text/plain":"\nval cavalier : int -> solution = <fun>"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"cavalier 5;;","execution_count":9,"outputs":[{"output_type":"execute_result","execution_count":9,"data":{"text/plain":"\n- : solution =\nSolution\n [|[|(1, 2); (1, 3); (1, 0); (1, 1); (-1, -1)|];\n   [|(3, 1); (3, 0); (2, 0); (3, 4); (0, 2)|];\n   [|(0, 1); (4, 0); (4, 1); (0, 4); (0, 3)|];\n   [|(4, 2); (4, 3); (4, 4); (1, 4); (2, 2)|];\n   [|(3, 2); (3, 3); (2, 1); (2, 4); (2, 3)|]|]"},"metadata":{}}]},{"metadata":{"trusted":false},"cell_type":"code","source":"","execution_count":null,"outputs":[]}],"metadata":{"kernelspec":{"name":"ocaml","display_name":"OCaml","language":"ocaml"}},"nbformat":4,"nbformat_minor":2}