1
00:00:00,410 --> 00:00:01,520
Welcome back.

2
00:00:01,700 --> 00:00:04,460
So how does backtracking work?

3
00:00:04,490 --> 00:00:10,550
Now, the way that backtracking works is that first it will explore one option.

4
00:00:10,550 --> 00:00:15,410
Like we've seen the case where we filled three on the Sudoku board.

5
00:00:15,440 --> 00:00:21,590
After we are done with this, it will keep building the solution using recursion.

6
00:00:21,680 --> 00:00:29,810
And as we go on, if we identify that the condition which is required is violated, then we backtrack

7
00:00:29,810 --> 00:00:32,270
and we explore different paths.

8
00:00:32,450 --> 00:00:39,290
On the other hand, if we see that the condition is not violated, if we see that we have identified

9
00:00:39,290 --> 00:00:46,040
a valid solution, we either make a copy of it or we return it as the question requires.

10
00:00:46,070 --> 00:00:50,930
Now, how is backtracking different from plain brute force?

11
00:00:50,960 --> 00:00:58,130
Remember, backtracking algorithms are a type of brute force algorithms because they are especially

12
00:00:58,130 --> 00:01:04,040
useful when we want to explore all the paths and find all the possible solutions.

13
00:01:04,040 --> 00:01:08,570
But then they are different from a simple brute force solution.

14
00:01:08,570 --> 00:01:15,650
In a simple brute force solution, what we would do is we would generate all the possible solutions,

15
00:01:15,650 --> 00:01:23,150
and then probably we would try to evaluate whether the solutions that we have generated satisfies the

16
00:01:23,150 --> 00:01:24,620
criteria as given.

17
00:01:24,620 --> 00:01:33,020
But on the other hand, when it comes to backtracking, we only proceed to build a particular solution

18
00:01:33,020 --> 00:01:35,690
if the conditions are favorable.

19
00:01:35,720 --> 00:01:37,430
Now, what do I mean with this?

20
00:01:37,430 --> 00:01:40,850
Let's take the example of the Sudoku board.

21
00:01:40,880 --> 00:01:48,410
Now, in pure recursion or a pure brute force solution, what would happen is we would let's say we

22
00:01:48,410 --> 00:01:51,290
have x number of empty cells.

23
00:01:51,290 --> 00:01:58,460
So that would imply that we could generate nine to the power X solutions, because every empty cell

24
00:01:58,460 --> 00:02:03,650
theoretically could be filled in nine ways, which is one, two, three, etc. up to nine.

25
00:02:03,650 --> 00:02:10,310
Now, it's not necessary that all these solutions are valid, but we could generate nine to the power

26
00:02:10,310 --> 00:02:12,650
empty cell solutions again, why is that?

27
00:02:12,650 --> 00:02:14,960
So imagine that you have two empty cells.

28
00:02:14,960 --> 00:02:18,050
So you could fill the first empty cell in nine ways.

29
00:02:18,050 --> 00:02:21,140
And you could fill the second empty cell in nine ways.

30
00:02:21,140 --> 00:02:27,710
So the total number of solutions that we have generated over here is nine into 9 or 9 to the power two,

31
00:02:27,740 --> 00:02:29,870
where we had two empty cells.

32
00:02:29,870 --> 00:02:35,210
So in this way we can generate nine to the power empty cell solutions.

33
00:02:35,210 --> 00:02:42,590
And then we would need another function to go through these solutions and check whether the solution

34
00:02:42,590 --> 00:02:49,940
identified is a working solution or not, based on the criterias or constraints that are involved in

35
00:02:49,940 --> 00:02:50,600
the question.

36
00:02:50,600 --> 00:02:53,990
And again, we have discussed the constraints for the Sudoku board.

37
00:02:53,990 --> 00:02:59,690
Things like you should have a number only one time in a box in a row and in a column.

38
00:02:59,690 --> 00:03:07,370
So how is backtracking different from this approach, or the simple brute force approach which we have

39
00:03:07,370 --> 00:03:08,300
discussed over here?

40
00:03:08,300 --> 00:03:16,280
So the difference is that in backtracking we don't go ahead with a particular solution if we know that

41
00:03:16,280 --> 00:03:19,160
it's not leading to a valid solution.

42
00:03:19,160 --> 00:03:25,220
So we prune that path and we only explore paths that lead to a solution.

43
00:03:25,220 --> 00:03:27,770
So this is how backtracking works.

44
00:03:27,770 --> 00:03:34,880
And this is what makes backtracking more efficient than a simple recursive solution.