Algorithm using DFS

Question

im trying to solve this, its stuck in a loop but i cant understand why. I think i might need to add some more conditions and i have looked others people's code but they seem too complicated.

    function solve(m, s, x, y) {        
        if (x == 9 && m[x][y] == "1") 
        {return;} //if last row, found door
    
    
        if (m[x+1][y] == "1") { //down
            s.push([x+1] + ", " + [y]);
            solve(m, s, x+1, y);
        }
    
        if (m[x][y+1] == "1") { //left
            s.push([x] + ", " + [y+1]);
            solve(m, s, x, y+1);
        }
    
        if (m[x][y-1] == "1") { //right
            s.push([x] + ", " + [y-1]);
            solve(m, s, x, y-1);
        }
    
        if (matrix[x-1][y] == "1") {  //up
            s.push([x-1] + ", " + [y]);
            solve(m, s, x-1, y);
        }
        s.pop(); //if bad path with no end
    }

Answer 1

The problem is that you don't mark which cells you have visited, and so you will revisit the same cell again, leading to a non-ending back-and-forth moment between coordinates 4,8 and 4,9.

One way to solve that, is to leave a trace in the matrix with another value, like value 2:

    // ...
    if (x == 9 && matrix[x][y] == "1") {    
        { return; } //if last row, found door

    matrix[x][y] = 2; // mark as visited <-- add this
    // ...

Some other issues:

• You should implement backtracking in way that the caller knows whether the recursive search was successful or not. So let your function return something that indicates this, like a boolean. Only when that return value is true, exit. Otherwise, the alternative directions should still be tried, and if no alternatives exist, the pop should happen with a return of false. Also the base cases should return true or false.

• The range checks should not be done with literals like 9, but be dynamic, so they check the actual size of the input array.

let stack = [];
let matrix = [  
                [0, 1, 0, 0, 0, 0],
                [0, 1, 0, 0, 0, 0],
                [0, 1, 0, 1, 0, 0],
                [1, 1, 1, 1, 0, 0],
                [1, 0, 0, 0, 0, 0],
                [1, 0, 0, 0, 0, 0],        
             ];

function solve(matrix, stack, x, y) {
    if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length) {
        return false;
    }

    if (x == matrix.length - 1 && matrix[x][y] == "1") {    
        return true; //if last row, found door
    }
    matrix[x][y] = 2; // mark as visited

    if (matrix[x+1][y] == "1") { //down
        stack.push([x+1] + ", " + [y]);
        if (solve(matrix, stack, x+1, y)) return true;
    }

    if (matrix[x][y+1] == "1") { //left
        stack.push([x] + ", " + [y+1]);
        if (solve(matrix, stack, x, y+1)) return true;
    }

    if (matrix[x][y-1] == "1") { //right
        stack.push([x] + ", " + [y-1]);
        if (solve(matrix, stack, x, y-1)) return true;
    }

    if (matrix[x-1][y] == "1") {  //up
        stack.push([x-1] + ", " + [y]);
        if (solve(matrix, stack, x-1, y)) return true;
    }
    stack.pop(); //if bad path with no end
    return false;
}


function detectStart(matrix, stack) {
    for (let y = 0; y < matrix.length; y++) {
        if (matrix[0][y] === 1) {
            stack.push([0] + ", " + [y]);
            solve(matrix, stack, 0, y);
            console.log(stack);
            return;
        }
    }
}

detectStart(matrix, stack);

Some other remarks:

• it is a bit strange that you compare matrix values with strings, while you initialise the matrix with numeric values.

• You could avoid some code repetition and do the check for 1 in the cell and the subsequent push at the start of the function, instead of doing that before the (recursive) call.