Stack overflow on an OCaml recursive solution to the knight's shortest path on chess board puzzle

Question

The question is as described here: Knight's Shortest Path Chess Question. I tried to solve it using an intuitive recursive method, as follows:

let is_in_list x s = 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 x s
      else loop result s in
  loop (List.hd s) s;;

let rec find_shortest_path n m =
  if is_in_list m (next_step n) then 1
  else
    1 + min (List.map (fun x -> find_shortest_path x m) (find_next_step n)) ;;

This causes a “stack overflow” issue. Why is that? Is my program creating too many layers of recursive call in the stack? Or something is terribly wrong with my code.

Answer 1

You have to understand that when you write

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

You will literally compute all "shortest path from here" from all possible neighbors -- then compute the minimum of all those results.

So there is an infinite loop in your code: if you start from position A and try to compute the shortest path from one of its neighbors B, then find_shortest_path called from B will inevitably try to see how long the path would be if his first move was to go back to A. So, among all other possible moves that will also be tried, you will compute the "length" of the loop A-B-A-B-A-B..., that is, loop endlessly.

There are several ways to avoid that issue (that is not related to OCaml programming per se, it's an error in your program logic that would be manifest in any language):

• use a breadth-first search instead of a depth-first-search, so that you incrementally explore all paths of a given length, stopping at the smallest winning path you find; if you want, this corresponds to explore all paths in parallel, so it's not an issue to have infinite paths as long as you stop (because you have found another solution) before trying to search the whole infinite path

• mark the places you've already visited, so as to not "go back" (this will never be the shortest way to reach your destination)

  • if you use depth-first search this is delicate because those marks must be local to a search (you cannot simply mutate a matrix of booleans); for example, you could add an int list parameter to your find_shortest_path functions, that would be the list of places that are part of the currently explored path; before trying to compute the shortest path from a possible neighbors, check that it is not in this list. For something more efficient, you can use a set (module IntSet = Set.Make(struct type t = int let compare = Pervasives.compare)) (logarithmic, instead of linear, membership test), or use a mutable boolean matrix where you are careful to backtrack state changes when you choose a different path.

  • if you use breadth-first search, you can use a global boolean matrix of "places you've already visited", because you simultaneously explore all paths upto a given length; so if you encounter a place that is already marked as visited, you know that another path visited it in an earlier time, so it is already ahead of you and there is no point trying to get a shortest path from there.

So the short answer is: you should learn about breadth-first search.

Answer 2

Well, the next legal move calculation looks wrong to me. If I'm at lower right (square 7, say), I can't move to square 1. This shouldn't cause looping, however, it should just get the wrong answer.

My guess is that you're just following some very long, failing paths. I think you need to do a breadth-first search rather than depth first. In essence, you keep a set of reachable squares, advance each currently reachable spot by one move at each step. Your code always tries to reach the destination from each new spot, and hence (possibly) follows many long paths.