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
 }

• Aldert: Have you tried debugging?
• Bryar: @Aldert yes but i am not sure how to fix, am currently looking at an answer here
• Aldert: Handy link: stackoverflow.com/questions/53685952/…
• c0der: Please add a programming-language tag, and post minimal reproducible example, including hard-coded test data. Consider using meaningful parameters names.

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.

• Bryar: i have been all day working with this and one line its all it took, thank you so much. T_T
• Bryar: Hey Im still debugging with that line, and now i realized it will sometimes block access to other cells, and only half the path will be checked. Not sure if u got any suggestions
• trincot: If it would block access to other cells, then you should find the path on backtracking to that cell. Can you give an example grid with this problem?
• trincot: I added some points to my answer.
• Bryar: Thats well thought! i was considering of returning booleans but was unsure if it would make a big difference. Thanks!!

Answer 2

Here is the solution of the current problem, created by Mr. trincot. The implementation is in C++.

#include <iostream>
#include <vector>
#include <tuple>
using namespace std;
const int maximumSize=6;
vector<vector<int>> 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}};
vector<vector<int>> visited(maximumSize, vector<int>(maximumSize, 0));
vector<tuple<int, int>> path;
void showContentVector2D(vector<vector<int>>& input)
{
 for(int i=0; i<input.size(); ++i)
 {
 for(int j=0; j<input[i].size(); ++j)
 {
 cout<<input[i][j]<<", ";
 }
 cout<<endl;
 }
 return;
}
void showContentVectorTuple(vector<tuple<int, int>>& input)
{
 for(int i=0; i<input.size(); ++i)
 {
 cout<<get<0>(input[i])<<" : "<<get<1>(input[i])<<endl;
 }
 return;
}
void dfs(int indexX, int indexY)
{
 if(indexX<0 || indexX==matrix.size() || indexY<0 || indexY==matrix[0].size())
 {
 return;
 }
 if(indexX==(matrix.size()-1) && (matrix[indexX][indexY]==1))
 {
 visited[indexX][indexY]=1;
 auto indices=make_tuple(indexX, indexY);
 path.push_back(indices);
 return;
 }
 visited[indexX][indexY]=1;
 auto indices=make_tuple(indexX, indexY);
 path.push_back(indices);
 if(visited[indexX+1][indexY]==0)
 {
 if(matrix[indexX+1][indexY]==1)
 {
 dfs(indexX+1, indexY);
 if(visited[indexX+1][indexY])
 {
 return;
 }
 }
 }
 if(visited[indexX-1][indexY]==0)
 {
 if(matrix[indexX-1][indexY]==1)
 {
 dfs(indexX-1, indexY);
 if(visited[indexX-1][indexY])
 {
 return;
 }
 }
 }
 if(visited[indexX][indexY-1]==0)
 {
 if(matrix[indexX][indexY-1]==1)
 {
 dfs(indexX, indexY-1);
 if(visited[indexX][indexY-1])
 {
 return;
 }
 }
 }
 if(visited[indexX][indexY+1]==0)
 {
 if(matrix[indexX][indexY+1]==1)
 {
 dfs(indexX, indexY+1);
 if(visited[indexX][indexY+1])
 {
 return;
 }
 }
 }
 return;
}
void solve()
{
 for(int i=0; i<matrix.size(); ++i)
 {
 if(matrix[0][i]==1)
 {
 dfs(0, i);
 }
 }
 cout<<"visited <- "<<endl;
 showContentVector2D(visited);
 cout<<endl<<"matrix <- "<<endl;
 showContentVector2D(matrix);
 cout<<endl<<"path <- "<<endl;
 showContentVectorTuple(path);
 cout<<endl;
 return;
}
int main()
{
 solve();
 return 0;
}

Here is the result:

visited <- 
0, 1, 0, 0, 0, 0, 
0, 1, 0, 0, 0, 0, 
0, 1, 0, 0, 0, 0, 
1, 1, 0, 0, 0, 0, 
1, 0, 0, 0, 0, 0, 
1, 0, 0, 0, 0, 0, 
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, 
path <- 
0 : 1
1 : 1
2 : 1
3 : 1
3 : 0
4 : 0
5 : 0

• Vadim Chernetsov: @trincot, Hello, respected Mr. trincot. Here is the solution, provided by you, with the implementation in C++, if you are interested.