Stack overflow on OCaml recursive solution for knight's shortest path on a chessboard puzzle

Question

The question is as described here: The shortest path of a knight's chess path . I tried to solve this problem using an intuitive recursive method:

let is_in_list xs = List.exists (fun y -> if y = x then true else false) s;; (* find out if an element belongs to a list *) let next_step n = [n+10;n-6;n+6;n-10;n+17;n-17;n+15;n-15];; let rec legal_next_step = function |[]->[] |x::s-> if x<0 or x>63 then legal_next_step s else x::legal_next_step s;; let find_next_step n = legal_next_step (next_step n);; (* here is to find all the valid next moves and put them into a list*) let rec min s = let rec loop result = function |[]->result; |x::s-> if x < result then loop xs else loop result s in loop (List.hd s) s;; let rec find_shortest_path nm = if is_in_list m (next_step n) then 1 else 1 + min (List.map (fun x -> find_shortest_path xm) (find_next_step n)) ;; 

This causes a stack overflow problem. Why is this? Does my program create too many recursive call levels on the stack? Or something is terribly wrong with my code.

Answer 1

You must understand that when you write

 List.map (fun x -> find_shortest_path xm) (find_next_step n)) 

You literally calculate the entire “shortest path from here” from all possible neighbors - then calculate the minimum of all these results.

So, there is an infinite loop in your code: if you start at position A and try to calculate the shortest path from one of your neighbors B , then find_shortest_path called from B will inevitably try to see how long the path will be if its first step was to return to A Thus, among all the possible steps that will also be checked, you will calculate the "length" of the ABABAB... cycle, that is, the cycle is infinite.

There are several ways to avoid this problem (which is not related to OCaml programming per se, this is a mistake in your program logic that will appear in any language):

• use the width search instead of the depth search, so that you gradually study all the paths of a given length, stopping at the smallest winning path that you find; if you want, this is consistent with exploring all paths in parallel, so you don't have to have infinite paths until you stop (because you found another solution) before trying to search for the entire infinite path.

• mark the places that you have already visited so as not to “return” (this will never be the shortest way to achieve the goal)

  • If you use a depth search, this is delicate because these labels must be local to the search (you cannot just mutate the matrix of logical elements); for example, you can add an int list parameter to your find_shortest_path functions, which will be a list of places that are part of the path being examined; Before trying to calculate the shortest path from possible neighbors, check to see if there is any in this list. For something more efficient, you can use the set ( module IntSet = Set.Make(struct type t = int let compare = Pervasives.compare) ) (logarithmic, not linear, membership criteria) or use a mutable logical matrix, where you careful to change the return status when you choose a different path.

  • If you use a breadth-first search, you can use the global logic matrix from the “places you've already visited”, since you simultaneously study all the paths to a certain length; therefore, if you come across a place that is already marked as visited, you know that the other path visited it at an earlier time, so that it is already ahead of you, and there is no point in trying to get the shortest path from there.

So, the short answer is: you should find out about the search in the first place.

Answer 2

Well, the next legitimate calculation seems wrong for me. If I’m lower right (square 7, say), I cannot go to square 1. This should not cause a loop, but it should just get the wrong answer.

I assume that you are simply following very long, unfortunate paths. I think you first need to do a breadth first search, not depth. In fact, you keep a set of reachable squares, advance each currently achievable place in one move at each step. Your code always tries to get to its destination from every new location and therefore (possibly) follows many long tracks.