Is there an algorithm to find all possible routes in a board game?

Question

I'm trying to write a javascript function that finds all possible routes of length N on a board (a 15x15 grid) where the player cannot move diagonally. I was able to come up with a pretty simple recursive solution but I suspect it is extremely unoptimized.

Here is the code:

search(n, u, v) {

    if (n == 0 || isWall(u, v))
        return;
        
    board[v][u] = 2;
    
    search(n - 1, u, v - 1);
    search(n - 1, u + 1, v);
    search(n - 1, u, v + 1);
    search(n - 1, u - 1, v);
    
    return;
}

board is a 2d array that contains the board's data. Free spaces, walls and reachable spaces are represented by 0s, 1s and 2s respectively.

Here's an example of what is looks like given N=6

EDIT: As mentionned below, I'm trying to find all reachable cells in N or less moves.

Answer 1

Like others wrote, you should use a breadth-first traversal instead of a depth-first traversal.

Secondly, you should not revisit a cell that already has been marked with value 2, so your condition to continue should be that the current cell has value 0.

I would suggest implementing the traversal using two arrays:

function search(board, n, u, v) {
    let count = 0;
    let frontier = [[u, v]];
    
    while (n-- > 0 && frontier.length) {
        let newFrontier = [];
        for (let [u, v] of frontier) {
            if (board[v]?.[u] === 0) {
                board[v][u] = 2;
                count++;
                newFrontier.push([u, v - 1], [u + 1, v], [u, v + 1], [u - 1, v]);
            }
        }
        frontier = newFrontier;
    }
    
    return count;
}

let board = [
    "11111111111111",
    "10000000000001",
    "10000000000001",
    "10011100111001",
    "10010000001001",
    "10010000001001",
    "10000000000001",
    "10000000000001",
    "10000000000001",
    "10010000001001",
    "10010000001001",
    "10011100111001",
    "10000000000001",
    "10000000000001",
    "11111111111111"
].map(row => Array.from(row, Number));

let res = search(board, 6, 2, 2);

console.log("number of cells reached: ", res);

console.log(board.map(row => row.join(" ")).join("\n"));