1
00:00:00,480 --> 00:00:07,110
In the previous video, we have discussed the approach that we can take to solve the N-queens problem.

2
00:00:07,110 --> 00:00:13,770
We have also discussed what are the various criterias to be checked when placing a queen at a particular

3
00:00:13,770 --> 00:00:14,370
position.

4
00:00:14,370 --> 00:00:19,860
For example, to check whether we can place a queen over here, we would have to do the column, check

5
00:00:19,860 --> 00:00:25,230
the top left diagonal check and the top right diagonal check.

6
00:00:25,230 --> 00:00:31,530
Now in this video, let's proceed and write the pseudocode of the approach that we have discussed.

7
00:00:31,530 --> 00:00:37,020
And over here I've also placed the backtracking blueprint that we had previously discussed.

8
00:00:37,020 --> 00:00:38,310
So let's get started.

9
00:00:38,310 --> 00:00:41,550
Let's say we will have to write a recursive function.

10
00:00:41,550 --> 00:00:44,340
And let's just call that recursive function backtrack.

11
00:00:44,340 --> 00:00:50,010
And to that function we will be passing how the board looks at that particular point.

12
00:00:50,010 --> 00:00:52,560
And we will also be passing the row.

13
00:00:52,560 --> 00:00:57,060
So initially we pass the board and we pass row0 to it.

14
00:00:57,060 --> 00:01:01,860
And once we are inside the function let's first write the base case.

15
00:01:01,860 --> 00:01:07,320
The base case would be if row is equal to four let's say n is equal to four.

16
00:01:07,320 --> 00:01:12,390
So notice that the valid row values are zero, one, two and three.

17
00:01:12,390 --> 00:01:16,440
So the first invalid value would be four right.

18
00:01:16,440 --> 00:01:21,480
So when we encounter the first invalid case we would have hit the base case.

19
00:01:21,480 --> 00:01:30,030
So we can say if row is equal to n or in this example if row is equal to four, we will just append

20
00:01:30,030 --> 00:01:33,420
that particular board to the results array and return.

21
00:01:33,420 --> 00:01:35,340
So this is our base case.

22
00:01:36,450 --> 00:01:42,900
Now let's proceed and write the for loop for the various choices that we can make over here.

23
00:01:42,930 --> 00:01:50,490
Now in this case, for a particular row, the choices that we have are column zero, column one, column

24
00:01:50,490 --> 00:01:55,620
two, and column three, because we know that we will fill only one queen in one row.

25
00:01:55,620 --> 00:01:59,730
But then we can do it either here or here or here or here.

26
00:01:59,730 --> 00:02:04,710
So the choices are for column in zero, one, two and three.

27
00:02:04,710 --> 00:02:06,930
So these are the choices that we have.

28
00:02:06,930 --> 00:02:12,990
And before making the choice we need to check whether that particular choice is valid or not.

29
00:02:12,990 --> 00:02:19,440
And that's where we will use the is valid function that we are discussed where we will do the column

30
00:02:19,440 --> 00:02:24,180
check top left diagonal check, and top right diagonal check.

31
00:02:24,690 --> 00:02:26,010
So let's write that over here.

32
00:02:26,010 --> 00:02:27,660
So if is valid.

33
00:02:27,660 --> 00:02:35,310
So if it's valid to place a queen at that particular position then we will go ahead with the choose

34
00:02:35,310 --> 00:02:38,310
help and the recursive call and the revert choice.

35
00:02:38,310 --> 00:02:39,690
So these three steps.

36
00:02:39,840 --> 00:02:41,610
So let's proceed with that.

37
00:02:42,060 --> 00:02:48,930
So first we will fill the Queen in that particular position which is the choose step.

38
00:02:49,560 --> 00:02:53,490
And then we will recursively call the same function again.

39
00:02:53,490 --> 00:02:56,250
So over here we have named the function itself backtrack.

40
00:02:56,250 --> 00:02:58,740
So we will recursively call the function again.

41
00:02:58,740 --> 00:03:00,420
And we will pass the board.

42
00:03:00,420 --> 00:03:03,120
And we will pass rho plus one to it.

43
00:03:03,120 --> 00:03:03,840
Right.

44
00:03:04,020 --> 00:03:06,810
So the board and rho plus one will be passed to it.

45
00:03:06,810 --> 00:03:15,840
And then we have the revert choice step which is removing this queen and placing a dot at that position.

46
00:03:15,840 --> 00:03:20,490
Because in the question it's given that an empty place is indicated by a dot.

47
00:03:21,030 --> 00:03:24,930
So this is the pseudo code of the approach that we have discussed.

48
00:03:24,930 --> 00:03:30,120
And notice that it is in line with the backtracking blueprint that we had previously discussed.

49
00:03:30,120 --> 00:03:37,170
Now do remember the backtracking step is this step over here where we revert the choice that we had

50
00:03:37,170 --> 00:03:38,100
previously made.

51
00:03:38,100 --> 00:03:43,770
And this is especially important because we want all the possible solutions.

52
00:03:43,770 --> 00:03:49,980
So once we get a solution, we backtrack to identify other possible solutions.