Stuck in infinite recursive loop (DFS)

Mschreider 0
Viewed 72

I am trying to solve a shortest path algorithm problem using a knight on a chess board. I understand that BFS (breadth first search) is the most efficient approach but I want to try and solve it using DFS (Depth first search) first. Understanding both algorithms will greatly help my knowledge.
Issue/Problem: My nextMove(curRow, curCol, moves) function eventually stack overflows. The base case of my function works because I can see the first stacks return successfully. But as it gets towards the end of possible scenarios it runs infinitely with the same array values. What I expected: I expect the recursive function to exit when there are no more scenarios left
What I've tried: I tried to pop the array when the recursive function returns so it does not keep trying with the same array values.
Code: https://jsfiddle.net/mschreider/jaqL1c5d/ uncomment line 115 to run
I commented out the console.log() function call because of the stack overflow problem. 

function knightMoves(start, finish) {

  let shortestPath = []
  
    function nextMove(curRow, curCol, moves) {
        //console.log(moves)
            if (curRow === finish[0] && curCol === finish[1]) {
            if (shortestPath.length === 0) {
                shortestPath = moves
            }
            else {  
                shortestPath = moves.length < shortestPath.length ? moves : shortestPath
            }

            console.log(shortestPath)
        
            return
        }
    
        // coordinates the knight can move [row, col]
        let options = [[1,2], [1,-2], [-1,2], [-1,-2], [2,1], [2,-1], [-2,1], [-2,-1]]
        for (let i=0; i<options.length; i++) {
            let moveRow = options[i][0]
            let moveCol = options[i][1]

            let newRow = curRow + moveRow
            let newCol = curCol + moveCol
            
            let proceed = validMove(newRow, newCol, moves)
            
            // if there is space to move, move knight
            if (proceed) {
                let arr = [...moves]
                arr.push([newRow, newCol])
                nextMove(newRow, newCol, arr)
                arr.pop()
            }
        }    
        return 
    }   

    nextMove(start[0], start[1], [start])
    return shortestPath
}

function validMove(row, col, moves) {
    // Check if the location has already been seen
  let coordinate = [row, col]
    let newSpot = true
    if (moves.length > 0) {
    for (let i = 0; i <moves.length; i++) {
      let seen = moves[i].length === coordinate.length && moves[i].every((value, index) => value === coordinate[index])
      if (seen) {
        return false
      }
    }
  }
  else {
    newSpot = true
  }
  
  // Check if the knight has space to move
  if (newSpot) {
    if ((row >= 0 && row < 8) && (col >= 0 && col < 8)) {
      return true
    }
    else {
      //debugger;
      return false
    }
  }
}

// console.log(knightMoves([0,0],[3,3]))

depth-first-search shortest-path recursion algorithm javascript
2 Answers

There are two issues here:

  • Your shortestPath array gets mutated by arr.pop(). When the recursive call that found the target returns, arr is the array reference that is now shared with shortestPath. This means that after the depth-first algorithm would complete, you wouldn't have the answer. This can be fixed by not doing the pop (it doesn't serve a purpose as arr is not used after that) or not taking a copy of the array where you do it now, but push/pop with moves, and take a copy at the moment you assign to shortestPath: that way you ensure shortestPath will never be mutated by a push or pop afterwards.

  • The depth-first traversal will visit all possible move sequences (that do not revisit a previous square on the path). This number of sequences is too large for any computer to visit in any reasonable time. Wikipedia gives an estimation of 1051 distinct move sequences on an 8x8 board. That's more than there are water molecules in the oceans. In your algorithm the sequences that run via the target square are not visited, but that still amounts to an astronomical number of sequences to visit. You can safely forget about that traversal completing in your lifetime.

Your algorithm is what is called "brute force". For 5x5 it will work in a reasonable time, but it quickly gets out of control for greater boards. Although there are some ways to optimise your algorithm, depth-first is not the right tool for this.

If you want to consider a better alternative for breadth-first, then look into A*, which is an "informed" search, in the category of best-first search algorithms, based on a heuristic. Except for positions that are nearby, a good heuristic in this case is the Euclidean distance between the two positions divided by √3.

trincot0

If it runs forever, the exit condition must be at fault.

So ... what's supposed to exit the recursion? nextMove recurses while validMove returns true. validMove returns false in two cases:

  1. the knight tries to move outside the board. By itself, this doesn't guarantee termination, because the knight can walk in circles.
  2. the knight visits a coordinate he has already visited in this path

The latter ensures that the path length is at most 64 (because otherwise a square would be visited twice), so we are considering at most 8**64 paths. That's up to 6277101735386680763835789423207666416102355444464034512896 paths. Granted, the vast majority of these will leave the board at some point, but if even a tiny fraction remain inside the boundaries, this might take forever.

To investigate whether this really is the issue, let's restrict path lengths, and output the number of paths considered, by inserting the following into validMove:

  if (moves.length == maxPathLength) {
    visitedPaths++
    return false;
  }

and running this with various values for maxPathLength:

maxPathLength visitedPaths
2 16
4 288
10 2509424
12 42251728
13 161594928
14 648090800
15 2359955136

So even just looking a paths of length 15, we are visiting over a billion paths, and the digits keep piling up! There is no way we'll be able to visit every path of length 64 (and such paths exist!) in our lifetime!

So your algorithm is beyond redemption. You need to find a way to exit early, and focus on the solutions you want rather than trying to iterate through the entire solution space. And since you seek the shortest path, processing shorter paths first rather than going down into the rabbit hole is what you need. In other words: breadth first, rather than depth first traversal.

meriton0
Related