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]))

CodePudding user response：

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 10⁵¹ distinct move sequences on an 8x8 board. That's more than there are water molecules in the oceans, so 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. There are several ways to optimise your algorithm. The Wikipedia article I referred to above has several successful strategies, but that would go beyond the scope of this question.

CodePudding user response：

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:

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.