let valid_board n m = (* Determina se un taboleiro dado pode ser válido *)
    n > 0 && m > 0
;;

let  valid_square n m (x, y) = (* Determina se unha casa existe nun taboleiro *)
    x <= n && y <=m && x > 0 && y > 0
;;

let rec fusion l1 l2 = (* Devolve unha lista onde se fusiona cada elemento de l2 con cada elemento de l1 en pares *)
        List.concat (List.map (fun y -> List.map (fun x -> (x,y)) l2 ) l1)
;;

let combinations x y = (* Retorna as combinacións posibles entre todos os elementos de dúas listas dadas, sen repetírense *)
    List.rev_append (fusion x y) (fusion y x)
;;

(* q e w determinan todas as posibilidades do movemento da peza (neste caso o cabalo)
é decir, as posibilidades son as combinacions dos elementos dunha lista cos de outra.

(x +/- r, y +/- s) onde r ou s = 1 ou 2 e r =/=s

 *)

let q = [1;-1];;
let w = [2;-2];;


let theoretical_squares (x,y) = (* Devolve todos os movementos teóricos da peza nunha posición inicial dada*)
    List.map (fun (a,b) -> (a + x, b + y) ) (combinations q w)
;;

let rec one_to_n n = (* Devolve unha lista dende 1 ata n *)
    if n = 0
    then []
    else one_to_n (n-1) @ [n]
;;

let board_squares n m = (* Devolve unha lista con todas as casas do taboleiro *)
    fusion (one_to_n m) (one_to_n n)
;;

let possible_squares n m (x,y) = (* Devolve unha lista cos posibles movementos nun taboleiro dado *)
    if valid_board n m
    then List.filter (fun c -> valid_square n m c) (theoretical_squares (x,y))
    else invalid_arg "possible_squares"
;;

let rec valid_path n m = function
    | [] -> false
    | h::[] -> true
    | h::t -> not (List.mem h t) && List.mem (List.hd t) (possible_squares n m h) && valid_path n m t
;;

let is_final_path n m l (u,v) = (* Determina se unha lista contén un camiño que recorre todo o taboleiro (dado polas súas dimensións) ata a casa dada *)
    List.length l = n*m && valid_path n m l && List.nth l (n*m - 1) = (u,v)
;;

let possible_squares_by_path n m l = match l with
    | [] -> []
    | h::t -> List.filter (fun c -> not (List.mem c l)) (possible_squares n m h)
;;

let rec generate_possible_paths n m l =
    if List.length l = 0
    then []
    else List.map (fun c -> c::l) (possible_squares_by_path n m l)
;;

(* WIP *)

let generate_long_paths n m (x,y) =
    let rec aux l =
            match generate_possible_paths n m l with
                | [] -> []
                | h::t -> aux t @ generate_possible_paths n m h
    in aux [(x,y)]
;;


let knight_tour n m (x,y) (u,v) =
    List.find (fun c -> is_final_path n m (List.rev c) (u,v)) (generate_long_path n m (x,y))
;;