Java – why is this called backtracking?

I read it on Wikipedia and Google it,

But I can't figure out what "backtracking algorithm" means

I saw this solution in the "crack code interview"

And wonder why this is a backtracking algorithm?

Solution

Backtracking is a term used in enumeration algorithms

You build a "solution" (a structure that assigns values to each variable)

However, during construction, you may realize that the solution is unsuccessful (some constraints are not met), and then you go back: you undo some values of variables in order to reassign them

Example:

According to your example, you want to build a path in a 2D mesh So you start generating paths from (0,0) For example:

(0,0)
(0,0) (1,0) go right
(0,1) go up
(0,1) (0,1) go left
(0,0) go down
Oops,visiting a cell a second time,this is not a path anymore
Backtrack: remove the last cell from the path
(0,1)
(0,1) (1,1) go right
Oops,this is not a path anymore
Backtrack: remove the last cell from the path
....