Welcome back.
So how does backtracking work?
Now, the way that backtracking works is that first it will explore one option.
Like we've seen the case where we filled three on the Sudoku board.
After we are done with this, it will keep building the solution using recursion.
And as we go on, if we identify that the condition which is required is violated, then we backtrack
and we explore different paths.
On the other hand, if we see that the condition is not violated, if we see that we have identified
a valid solution, we either make a copy of it or we return it as the question requires.
Now, how is backtracking different from plain brute force?
Remember, backtracking algorithms are a type of brute force algorithms because they are especially
useful when we want to explore all the paths and find all the possible solutions.
But then they are different from a simple brute force solution.
In a simple brute force solution, what we would do is we would generate all the possible solutions,
and then probably we would try to evaluate whether the solutions that we have generated satisfies the
criteria as given.
But on the other hand, when it comes to backtracking, we only proceed to build a particular solution
if the conditions are favorable.
Now, what do I mean with this?
Let's take the example of the Sudoku board.
Now, in pure recursion or a pure brute force solution, what would happen is we would let's say we
have x number of empty cells.
So that would imply that we could generate nine to the power X solutions, because every empty cell
theoretically could be filled in nine ways, which is one, two, three, etc. up to nine.
Now, it's not necessary that all these solutions are valid, but we could generate nine to the power
empty cell solutions again, why is that?
So imagine that you have two empty cells.
So you could fill the first empty cell in nine ways.
And you could fill the second empty cell in nine ways.
So the total number of solutions that we have generated over here is nine into 9 or 9 to the power two,
where we had two empty cells.
So in this way we can generate nine to the power empty cell solutions.
And then we would need another function to go through these solutions and check whether the solution
identified is a working solution or not, based on the criterias or constraints that are involved in
the question.
And again, we have discussed the constraints for the Sudoku board.
Things like you should have a number only one time in a box in a row and in a column.
So how is backtracking different from this approach, or the simple brute force approach which we have
discussed over here?
So the difference is that in backtracking we don't go ahead with a particular solution if we know that
it's not leading to a valid solution.
So we prune that path and we only explore paths that lead to a solution.
So this is how backtracking works.
And this is what makes backtracking more efficient than a simple recursive solution.