理解回溯（网格上的机器人）

Question

下面是在网格上移动的机器人的代码，假设它从左上角移动到右下角并找到到达右下角的独特方式：

public static int findNumPath(int row, int col){
int total = 0;

//if grid[2][2] is reached, 1 path is found
if(row == 2 && col == 2){
    return 1;
}
grid[row][col] = true;
print();

if(col < 2 && grid[row][col+1] == false){
    System.out.println("inside 1st if" + " ,total= " + total);
    total = total + findNumPath(row, col+1);
}
if(col > 0 && grid[row][col-1] == false){
    System.out.println("inside 2nd if" + " ,total= " + total);
    total = total + findNumPath(row, col-1);
}
if(row < 2 && grid[row+1][col] == false){
    System.out.println("inside 3rd if" + " ,total= " + total);
    total = total + findNumPath(row+1, col);
}
if(row > 0 && grid[row-1][col] == false ){
    System.out.println("inside 4th if"+ " ,total= " + total);
    total = total + findNumPath(row-1, col);
}

grid[row][col] = false;
System.out.println("after making false" + " total=" + total);
return total;
}

这是输出：

true false false 
false false false 
false false false 

inside 1st if ,total= 0
true true false 
false false false 
false false false 

inside 1st if ,total= 0
true true true 
false false false 
false false false 

inside 3rd if ,total= 0
true true true 
false false true 
false false false 

inside 2nd if ,total= 0
true true true 
false true true 
false false false 

inside 2nd if ,total= 0
true true true 
true true true 
false false false 

inside 3rd if ,total= 0
true true true 
true true true 
true false false 

inside 1st if ,total= 0
true true true 
true true true 
true true false 

inside 1st if ,total= 0
after making false total=1
after making false total=1
after making false total=1
inside 3rd if ,total= 1
true true true 
false true true 
false true false 

inside 1st if ,total= 0
inside 2nd if ,total= 1
true true true 
false true true 
true true false 

inside 4th if ,total= 0
true true true 
true true true 
true true false 

after making false total=0
after making false total=0
after making false total=1
after making false total=2
inside 3rd if ,total= 2
after making false total=3
after making false total=3
inside 3rd if ,total= 3
true true false 
false true false 
false false false 

inside 1st if ,total= 0
true true false 
false true true 
false false false 

inside 3rd if ,total= 0
inside 4th if ,total= 1
true true true 
false true true 
false false false 

after making false total=0
after making false total=1
inside 2nd if ,total= 1
true true false 
true true false 
false false false 

inside 3rd if ,total= 0
true true false 
true true false 
true false false 

inside 1st if ,total= 0
true true false 
true true false 
true true false 

inside 1st if ,total= 0
after making false total=1
after making false total=1
after making false total=1
inside 3rd if ,total= 2
true true false 
false true false 
false true false 

inside 1st if ,total= 0
inside 2nd if ,total= 1
true true false 
false true false 
true true false 

inside 4th if ,total= 0
true true false 
true true false 
true true false 

after making false total=0
after making false total=0
after making false total=1
after making false total=3
after making false total=6
inside 3rd if ,total= 6
true false false 
true false false 
false false false 

inside 1st if ,total= 0
true false false 
true true false 
false false false 

inside 1st if ,total= 0
true false false 
true true true 
false false false 

inside 3rd if ,total= 0
inside 4th if ,total= 1
true false true 
true true true 
false false false 

inside 2nd if ,total= 0
true true true 
true true true 
false false false 

after making false total=0
after making false total=0
after making false total=1
inside 3rd if ,total= 1
true false false 
true true false 
false true false 

inside 1st if ,total= 0
inside 2nd if ,total= 1
true false false 
true true false 
true true false 

after making false total=0
after making false total=1
inside 4th if ,total= 2
true true false 
true true false 
false false false 

inside 1st if ,total= 0
true true true 
true true false 
false false false 

inside 3rd if ,total= 0
true true true 
true true true 
false false false 

inside 3rd if ,total= 0
after making false total=1
after making false total=1
after making false total=1
after making false total=3
inside 3rd if ,total= 3
true false false 
true false false 
true false false 

inside 1st if ,total= 0
true false false 
true false false 
true true false 

inside 1st if ,total= 0
inside 4th if ,total= 1
true false false 
true true false 
true true false 

inside 1st if ,total= 0
true false false 
true true true 
true true false 

inside 3rd if ,total= 0
inside 4th if ,total= 1
true false true 
true true true 
true true false 

inside 2nd if ,total= 0
true true true 
true true true 
true true false 

after making false total=0
after making false total=0
after making false total=1
inside 4th if ,total= 1
true true false 
true true false 
true true false 

inside 1st if ,total= 0
true true true 
true true false 
true true false 

inside 3rd if ,total= 0
true true true 
true true true 
true true false 

inside 3rd if ,total= 0
after making false total=1
after making false total=1
after making false total=1
after making false total=2
after making false total=3
after making false total=3
after making false total=6
after making false total=12
12

我最近学习了回溯，我试图理解回溯如何运行的这段代码，但是我不明白我们找到第一条路径后发生了什么，程序如何知道返回并进行一些从 TRUE 到 FALSE：

inside 1st if ,total= 0
after making false total=1
after making false total=1
after making false total=1
inside 3rd if ,total= 1
true true true 
false true true 
false true false

非常感谢能帮助我理解的解释。

Answer 1

以上代码并不是真正的回溯，而是一种递归搜索算法。它递归地搜索您的网格，按深度优先、左、右、下、上的顺序移动。

它在一个字段上移动时用 true 标记它，当它从那个位置用尽所有可能性时用 false 标记它（对于当前访问的字段）。它标记字段，因为它不会重访一个字段两次，所以它搜索最多访问每个字段一次的路径。

请注意，它确实会针对通向该字段的每条路径再次评估该字段。

理解回溯（网格上的机器人）

understanding backtracking (robot on the grid)

java

backtracking