1
00:00:00,360 --> 00:00:05,940
In the previous video, we have discussed the problem statement and we have got a good understanding

2
00:00:05,940 --> 00:00:08,940
of what is asked of us in this video.

3
00:00:08,940 --> 00:00:14,580
Let's try to solve this question, and let's think about what approach to take to efficiently solve

4
00:00:14,580 --> 00:00:14,970
it.

5
00:00:14,970 --> 00:00:22,320
Now, first, let's take an example and make a few observations to develop the intuition required to

6
00:00:22,320 --> 00:00:23,340
solve this question.

7
00:00:23,340 --> 00:00:25,920
Let's say n is equal to four.

8
00:00:25,920 --> 00:00:30,300
Now if n is equal to four we have a 4x4 chessboard.

9
00:00:30,510 --> 00:00:34,260
Now over here let's make a few observations.

10
00:00:34,470 --> 00:00:40,260
The first observation is that let's say we are filling the board row by row.

11
00:00:41,240 --> 00:00:45,620
If we are doing that, notice that we will be filling a queen.

12
00:00:45,620 --> 00:00:52,820
Only one queen in a row, because you can't place two queens in the same row because they would be attacking

13
00:00:52,820 --> 00:00:53,510
each other.

14
00:00:53,510 --> 00:00:57,410
So in one row there will be only one queen.

15
00:00:57,410 --> 00:00:59,330
So this is an interesting observation.

16
00:00:59,810 --> 00:01:07,190
Let's now say that we want to evaluate whether we can keep a queen at this position over here.

17
00:01:07,860 --> 00:01:12,540
Now to know whether this is a valid way of placing a queen.

18
00:01:12,540 --> 00:01:15,180
What all checks would be required.

19
00:01:15,180 --> 00:01:23,190
The first check that would be required is the column check, or we would need to check the cells in

20
00:01:23,190 --> 00:01:26,520
this particular column which comes before this.

21
00:01:26,520 --> 00:01:28,740
Now let me just put indices over here.

22
00:01:28,740 --> 00:01:31,680
So we have 0123.

23
00:01:31,680 --> 00:01:35,730
These are the indices of the rows and 012 and three.

24
00:01:35,730 --> 00:01:37,710
These are the indices of the columns.

25
00:01:37,710 --> 00:01:42,540
Now we are trying to place a queen at column with index one.

26
00:01:42,540 --> 00:01:45,510
And again the row is one.

27
00:01:45,510 --> 00:01:49,050
So we would need to check every row before this.

28
00:01:49,050 --> 00:01:52,470
And we would need to check the column at index one.

29
00:01:52,470 --> 00:01:57,210
So basically if we were trying to fill something like this.

30
00:01:57,990 --> 00:02:02,850
If you were trying to fill this position, we would have to check all of these places.

31
00:02:02,850 --> 00:02:08,730
Because if there is a queen over here, it could move in this manner and it would attack this queen.

32
00:02:08,730 --> 00:02:12,330
So that's why we would first need to do a column check.

33
00:02:12,780 --> 00:02:15,810
What would be the next check that is required.

34
00:02:15,900 --> 00:02:23,790
The next check that's required is to check the top left diagonal and the top right diagonal.

35
00:02:23,790 --> 00:02:27,570
Now the top left diagonal is this part over here.

36
00:02:27,570 --> 00:02:30,870
And the top right diagonal is this part over here.

37
00:02:30,870 --> 00:02:33,600
Because a queen can move diagonally as well.

38
00:02:33,600 --> 00:02:37,710
Now we are only checking the top part because we are filling from the top.

39
00:02:37,710 --> 00:02:44,280
We would have filled this row before we come to this row, but we have not yet filled anything in these

40
00:02:44,280 --> 00:02:51,330
rows, so that's why it's sufficient to check the top left diagonal and the top right diagonal.

41
00:02:51,990 --> 00:02:56,490
Now let's take a look at how the algorithm would play out.

42
00:02:56,520 --> 00:03:02,070
Now we have understood what checks are needed, and we have also made some interesting observations,

43
00:03:02,070 --> 00:03:05,490
such as that we will be filling only one queen per row.

44
00:03:05,490 --> 00:03:09,180
And let's say we are filling the queens row by row.

45
00:03:09,180 --> 00:03:12,300
And let's say we are starting at row with index zero.

46
00:03:12,300 --> 00:03:14,400
Now let's see how this plays out.

47
00:03:14,400 --> 00:03:17,790
So initially we have row with index zero.

48
00:03:17,790 --> 00:03:20,280
And we are trying to fill a queen in this row.

49
00:03:20,280 --> 00:03:22,530
And we start with the first column.

50
00:03:22,530 --> 00:03:28,020
And we see that yes it can be filled because there is no other queen on this board at this point.

51
00:03:28,020 --> 00:03:32,460
Now we proceed and recursively we move to the second row.

52
00:03:32,820 --> 00:03:39,450
Now, when we are trying to fill a queen in the second row, we notice that we can't place a queen over

53
00:03:39,450 --> 00:03:43,560
here and over here because this queen would attack it, right?

54
00:03:43,560 --> 00:03:46,770
Because it can move in this way and it can move diagonally as well.

55
00:03:46,770 --> 00:03:52,710
So therefore the next position that we find is over here and we can place a queen over here.

56
00:03:52,710 --> 00:03:58,050
And again we would recursively call the function to place a queen in the next row.

57
00:03:58,050 --> 00:04:03,510
Now when we are trying to place a queen in this row, notice that you can't place a queen over here

58
00:04:03,510 --> 00:04:05,220
because this queen would attack it.

59
00:04:05,220 --> 00:04:08,550
You can't place a queen over here because this one would attack it.

60
00:04:08,550 --> 00:04:13,770
Similarly, you can't place one over here again, this one would attack it, and you can't place a queen

61
00:04:13,770 --> 00:04:16,530
over here as well, because this queen would attack it.

62
00:04:16,530 --> 00:04:24,300
So we find that there is no place available for placing a queen over here, so we can't fill it.

63
00:04:24,300 --> 00:04:28,590
And therefore this is actually not a valid solution.

64
00:04:28,590 --> 00:04:34,860
And again, this scenario has occurred because of the way that we filled queens in these two rows.

65
00:04:34,860 --> 00:04:40,860
So as this is not a valid solution, there is no point in proceeding with this branch.

66
00:04:40,860 --> 00:04:48,630
Therefore we prune this branch and we backtrack, which means that we come back to the previous case

67
00:04:49,110 --> 00:04:51,840
and we remove what we had filled over here.

68
00:04:51,840 --> 00:04:56,250
And we tried to place a queen in a different position.

69
00:04:56,250 --> 00:05:00,720
So let's say we try to put a queen over here and we see that that's valid.

70
00:05:00,720 --> 00:05:05,700
And again, we make a recursive call to fill a queen in the next row.

71
00:05:05,700 --> 00:05:10,740
Now over here we see that we can't place a queen over here because this one would attack it.

72
00:05:10,740 --> 00:05:12,930
But we can place a queen over here.

73
00:05:12,930 --> 00:05:19,260
And in this way it would again recursively call the same function to place a queen in the next row.

74
00:05:19,260 --> 00:05:23,340
So this is how the backtracking algorithm would solve this.

75
00:05:23,340 --> 00:05:26,340
And it would give us all the possible solutions.

76
00:05:26,340 --> 00:05:31,860
Because once we get a solution again, it would come back to the previous call and we would see whether

77
00:05:31,860 --> 00:05:34,680
we can place a queen in another position.

78
00:05:34,680 --> 00:05:41,370
So in a similar manner, finally, we would again come back to this place which is at row index zero,

79
00:05:41,370 --> 00:05:46,860
and we would remove this in the backtracking step, and we would place a queen in the next column.

80
00:05:46,860 --> 00:05:52,740
And again it would recursively call the same function to try whether we can place a queen in the next

81
00:05:52,740 --> 00:05:53,040
row.

82
00:05:53,040 --> 00:06:00,420
So in this way we will be able to get all the possible valid ways of placing queens n queens on an n

83
00:06:00,420 --> 00:06:01,530
by n chessboard.

84
00:06:01,530 --> 00:06:10,050
And once we get a solution, we would just append that particular way of filling queens on the n by

85
00:06:10,050 --> 00:06:16,440
n board to a results array, so that finally we can just return that results array.

86
00:06:16,440 --> 00:06:21,900
When we trace the algorithm, we also saw how the backtracking step would work.

87
00:06:21,900 --> 00:06:26,400
Now again, let's just quickly see what would happen in case we get a solution.

88
00:06:26,400 --> 00:06:33,270
So let's say we have filled three rows and we are trying to fill a queen in the fourth row over here.

89
00:06:33,270 --> 00:06:36,480
And we see that we can actually place it over here.

90
00:06:36,480 --> 00:06:38,100
And we have got a valid solution.

91
00:06:38,100 --> 00:06:42,810
So this solution over here would just be appended to the results array.

92
00:06:42,810 --> 00:06:48,060
And finally when we have found all the solutions we will return this results array.

93
00:06:48,060 --> 00:06:54,330
So this is the approach the backtracking approach that we can use to solve the n queens problem.