1
00:00:00,140 --> 00:00:03,770
Let's now get into the code for solving the N-queens question.

2
00:00:03,770 --> 00:00:09,740
Now over here, notice that we are given n and n could be 4 or 3 a number, right.

3
00:00:09,740 --> 00:00:11,360
So we are not given the board.

4
00:00:11,360 --> 00:00:13,520
So we have to go ahead and create the board.

5
00:00:13,520 --> 00:00:14,810
So that's what we're doing over here.

6
00:00:14,810 --> 00:00:19,730
And then before we get into the details of the code, let me quickly walk you through the skeleton of

7
00:00:19,730 --> 00:00:21,290
the approach that we have over here.

8
00:00:21,290 --> 00:00:28,310
So notice that we have the position next queen function, which is the function that we will be recursively

9
00:00:28,310 --> 00:00:33,620
calling to position the different queens in different rows of the board that we create.

10
00:00:33,620 --> 00:00:33,980
Okay.

11
00:00:33,980 --> 00:00:37,040
So notice that we do call it recursively over here.

12
00:00:37,040 --> 00:00:39,230
But again we'll come to the detail soon.

13
00:00:39,230 --> 00:00:42,320
And this is where we call this function for the first time.

14
00:00:42,320 --> 00:00:48,020
And again we are passing the first row which is the row with index zero when we call it for the first

15
00:00:48,020 --> 00:00:48,770
time okay.

16
00:00:48,770 --> 00:00:52,070
So that's the position next queen function over here.

17
00:00:52,070 --> 00:00:55,430
And we also have a few more other functions.

18
00:00:55,430 --> 00:00:56,780
Let's take a look at them.

19
00:00:56,780 --> 00:01:01,190
So notice that over here we have the is valid function.

20
00:01:01,190 --> 00:01:07,280
Now we will be using this function to check whether we can place a queen at a particular cell in the

21
00:01:07,280 --> 00:01:07,760
board.

22
00:01:07,760 --> 00:01:11,000
And we also have a convert board function over here.

23
00:01:11,000 --> 00:01:16,040
So let's get started with the details and we'll get to understand why we need this function over here.

24
00:01:16,040 --> 00:01:20,960
So again as we've discussed initially we are given n and we are not given the board.

25
00:01:20,960 --> 00:01:23,510
So we go ahead and create the board over here.

26
00:01:23,510 --> 00:01:28,040
So notice that the board over here is an array of arrays okay.

27
00:01:28,040 --> 00:01:34,160
And as per the requirement of the question, whenever we add a board to the results array, which is

28
00:01:34,160 --> 00:01:35,330
what we have declared over here.

29
00:01:35,330 --> 00:01:41,390
And finally we would be returning this when we fill every board to the results array that fits the requirement

30
00:01:41,390 --> 00:01:41,720
okay.

31
00:01:41,720 --> 00:01:48,380
So when we do that we'll have to fill to the results array an array of strings okay.

32
00:01:48,380 --> 00:01:54,800
So to convert an array of array into an array of strings we will be using the convert board function

33
00:01:54,800 --> 00:01:55,220
over here.

34
00:01:55,220 --> 00:01:59,300
So we are just passing the board to it which at this point would be an array of arrays.

35
00:01:59,300 --> 00:02:05,060
And then we will join the elements in a particular row together to form a string.

36
00:02:05,060 --> 00:02:08,360
And in this way we will convert the board into an array of strings.

37
00:02:08,360 --> 00:02:10,550
So that's what we're doing over here okay.

38
00:02:10,550 --> 00:02:13,940
So this much over here should be pretty straightforward.

39
00:02:14,060 --> 00:02:20,150
So let's now get into the details of the code which is pretty much analyzing the position.

40
00:02:20,150 --> 00:02:23,540
Next queen function and the is valid function.

41
00:02:23,540 --> 00:02:27,050
So first let's get started with the position next queen function.

42
00:02:27,050 --> 00:02:32,390
So over here notice that this is a function that we will be calling recursively okay.

43
00:02:32,390 --> 00:02:35,210
And over here first we have the base case.

44
00:02:35,210 --> 00:02:37,310
And again we are given n.

45
00:02:37,310 --> 00:02:38,960
Let's say n is equal to four.

46
00:02:38,960 --> 00:02:40,910
Then the board would look like this right.

47
00:02:40,910 --> 00:02:46,640
We'll have four rows and we will have four columns okay.

48
00:02:46,640 --> 00:02:53,060
And the indices for example for the rows go from zero up to three where this three over here is n minus

49
00:02:53,060 --> 00:02:53,810
one okay.

50
00:02:53,810 --> 00:02:57,380
Now we will make use of this information to write the base case.

51
00:02:57,380 --> 00:03:03,890
Notice that the base case over here is if the value of the row which is passed to the position x queen

52
00:03:03,890 --> 00:03:05,930
function is equal to n.

53
00:03:05,930 --> 00:03:13,130
Now if row is equal to n, we would have hit the first invalid input okay.

54
00:03:13,130 --> 00:03:15,320
And you have discussed that you can write the base case.

55
00:03:15,320 --> 00:03:20,510
Or you can think of the base case as the first invalid input or the last valid input.

56
00:03:20,510 --> 00:03:23,270
So over here we have the first invalid input.

57
00:03:23,270 --> 00:03:29,060
So when row is equal to n the value of row is out of bounds okay.

58
00:03:29,060 --> 00:03:36,290
And at that point it would indicate that we have actually identified a board where we were able to place

59
00:03:36,290 --> 00:03:38,270
a queen in every row.

60
00:03:38,270 --> 00:03:44,630
And therefore we will just pass that particular board to the convert board function so that we get an

61
00:03:44,630 --> 00:03:45,530
array of strings.

62
00:03:45,530 --> 00:03:47,570
And then we will push it to the results array.

63
00:03:47,570 --> 00:03:50,600
And the results array is what we finally return.

64
00:03:50,600 --> 00:03:51,080
Okay.

65
00:03:51,080 --> 00:03:54,170
So that's the base case of the position x queen function.

66
00:03:54,170 --> 00:03:59,120
And again notice that to this function we have to pass the board and the row that we are dealing with.

67
00:03:59,120 --> 00:04:01,700
So initially when we call this the row is equal to zero.

68
00:04:01,700 --> 00:04:06,650
So after we fill a queen in this row we would be calling this function recursively.

69
00:04:06,650 --> 00:04:10,340
And we will pass the next row which is the row with index one.

70
00:04:10,340 --> 00:04:12,050
And it goes on in this manner.

71
00:04:12,050 --> 00:04:17,510
Now let's take a look at the recursive case for the position x queen function, which is what we're

72
00:04:17,510 --> 00:04:18,620
doing over here okay.

73
00:04:18,620 --> 00:04:24,590
So basically what we're trying to do over here is for the row at hand, we will be trying to place a

74
00:04:24,590 --> 00:04:27,380
queen at every column in the row okay.

75
00:04:27,380 --> 00:04:30,680
So column goes from zero up to n minus one.

76
00:04:30,680 --> 00:04:37,550
Because again notice over here if n is equal to four then the valid columns go from zero up to three

77
00:04:37,550 --> 00:04:39,680
and three is n minus one okay.

78
00:04:39,680 --> 00:04:46,400
So for the values from zero up to n minus one, we will check whether we can place a queen at each of

79
00:04:46,400 --> 00:04:49,280
these positions using the is valid function.

80
00:04:49,280 --> 00:04:54,590
So to the is valid function we will be passing the row, the column and the board, and this function

81
00:04:54,590 --> 00:04:56,630
will either return true or false.

82
00:04:56,630 --> 00:04:59,750
So if it returns true, we will fill a queen.

83
00:04:59,980 --> 00:05:03,880
Over there at that particular column and row, which is done over here.

84
00:05:03,880 --> 00:05:05,980
Board row column is equal to Q.

85
00:05:05,980 --> 00:05:11,440
And then we recursively call the position x queen function with the next row okay.

86
00:05:11,440 --> 00:05:13,720
And then this goes deeper and deeper.

87
00:05:13,720 --> 00:05:20,080
And if we were able to place a queen in every row in this particular way of building the board, finally

88
00:05:20,080 --> 00:05:25,870
we would be hitting the base case and we would make a new array, which is an array of strings, and

89
00:05:25,870 --> 00:05:31,420
we would push it to the results array, which ensures that the value being pushed to the results array

90
00:05:31,420 --> 00:05:35,800
is a snapshot of the existing board at that particular instance.

91
00:05:35,800 --> 00:05:43,660
Now also do notice that over here we have the backtracking step which is about reversing the value or

92
00:05:43,660 --> 00:05:45,430
the decision taken over here.

93
00:05:45,550 --> 00:05:45,970
Okay.

94
00:05:45,970 --> 00:05:48,970
So Q was entered at a particular cell over here.

95
00:05:48,970 --> 00:05:52,360
And that's being reversed over here, which is the backtracking step okay.

96
00:05:52,360 --> 00:05:58,420
And the reason for this or why we need this is because the question asks us to find all the possible

97
00:05:58,420 --> 00:06:02,470
ways of filling n queens in an N into n board.

98
00:06:02,470 --> 00:06:02,830
Okay.

99
00:06:02,830 --> 00:06:08,830
And that's why even though probably over here, we may have arrived at a solution where we were able

100
00:06:08,830 --> 00:06:16,060
to fill n queens in n rows, but still over here, after we return from this function, we would have

101
00:06:16,060 --> 00:06:19,480
to backtrack and then we have to try other possible combinations.

102
00:06:19,480 --> 00:06:22,630
Okay, so that's why the backtracking step is very important over here.

103
00:06:22,630 --> 00:06:25,720
So the position x queen function is pretty straightforward.

104
00:06:25,720 --> 00:06:29,860
So we have the base case over here which is checking whether row is equal to n.

105
00:06:29,860 --> 00:06:35,740
And in which case we would form a new array which is an array of strings using the convert board function.

106
00:06:35,740 --> 00:06:42,010
And in this way we would be pushing a snapshot of how the board at that particular instance looks like

107
00:06:42,010 --> 00:06:43,090
into the results array.

108
00:06:43,090 --> 00:06:45,670
And the results array is what we finally return over here.

109
00:06:45,670 --> 00:06:46,120
Okay.

110
00:06:46,120 --> 00:06:52,750
And the recursive case is we try to fill a queen at every column in the row at hand at this particular

111
00:06:52,750 --> 00:06:57,820
instance, and to check whether we can place a queen in that particular cell or not.

112
00:06:57,820 --> 00:06:59,800
We make use of the is valid function.

113
00:06:59,800 --> 00:07:05,650
And we've also discussed why the backtracking step is important, because we need all the possible solutions,

114
00:07:05,650 --> 00:07:10,930
or all the possible ways of placing n queens on an n into n board.

115
00:07:10,930 --> 00:07:13,600
Now let's also take a look at the is valid function.

116
00:07:13,600 --> 00:07:18,940
Now in the is valid function, there are basically three things that we need to check and to discuss

117
00:07:18,940 --> 00:07:23,650
this, let's quickly draw this out so that it becomes visual and easy to relate to.

118
00:07:23,650 --> 00:07:26,230
So let's say n is equal to four okay.

119
00:07:26,230 --> 00:07:31,480
So that would mean we have four rows and we have four columns.

120
00:07:31,480 --> 00:07:38,140
Now if we are trying to place a queen let's say over here, what would be the different checks that

121
00:07:38,140 --> 00:07:39,250
we have to ensure.

122
00:07:39,250 --> 00:07:44,080
First of all we are filling the rows from top to bottom in this solution.

123
00:07:44,080 --> 00:07:48,100
So we do not need to check anything associated with this particular row.

124
00:07:48,100 --> 00:07:48,580
Okay.

125
00:07:48,580 --> 00:07:56,350
And we are also filling one queen only in one row because once we fill a queen in a row, we increment

126
00:07:56,350 --> 00:07:59,980
the value of row and we recursively call the position next queen function.

127
00:07:59,980 --> 00:08:00,310
Okay.

128
00:08:00,310 --> 00:08:05,860
So this would mean that there is nothing to check regarding other cells in this particular row.

129
00:08:05,860 --> 00:08:09,280
So there is nothing to check with respect to this row as well.

130
00:08:09,280 --> 00:08:12,640
Now what are the other things that we would need to check.

131
00:08:12,640 --> 00:08:14,230
Let's try to think about that.

132
00:08:14,230 --> 00:08:21,520
So if we want to place a queen over here, then we should not have a queen anywhere in these two cells,

133
00:08:21,520 --> 00:08:26,410
which is the same column where we are trying to place this queen over here, because otherwise they

134
00:08:26,410 --> 00:08:28,090
would fight against each other, right?

135
00:08:28,090 --> 00:08:29,650
It would violate the condition required.

136
00:08:29,650 --> 00:08:32,740
So we would have to check that there is no queen over here.

137
00:08:32,740 --> 00:08:38,860
And we will also have to ensure that there is no queen over here in any of these two cells.

138
00:08:38,860 --> 00:08:41,890
And there should be no queen over here as well.

139
00:08:41,890 --> 00:08:42,280
Okay.

140
00:08:42,280 --> 00:08:46,570
So this over here is what we call the top left diagonal.

141
00:08:46,570 --> 00:08:49,960
And this over here is the top right diagonal.

142
00:08:49,960 --> 00:08:54,400
Again, we don't need to check anything below because we are filling from the top.

143
00:08:54,400 --> 00:08:56,560
And we would not have filled anything over here.

144
00:08:56,560 --> 00:09:00,670
So that's why we only need to check the top, left and right diagonals.

145
00:09:00,670 --> 00:09:07,300
And we also need to check the columns from the beginning till the cell which is above this particular

146
00:09:07,300 --> 00:09:11,920
cell over here, or the previous row of the row that we are trying to currently fill.

147
00:09:11,920 --> 00:09:16,540
Okay, so these are the three checks that we need to have in the is valid function.

148
00:09:16,540 --> 00:09:20,530
So to the is valid function we will be passing the row, the column and the board.

149
00:09:20,530 --> 00:09:27,130
And to check whether there is any queen in these cells which are the cells above this particular cell

150
00:09:27,250 --> 00:09:28,750
on the same column.

151
00:09:28,750 --> 00:09:30,550
We have this for loop over here.

152
00:09:30,550 --> 00:09:34,090
So for x is equal to zero x less than row okay.

153
00:09:34,090 --> 00:09:38,320
So this would be the row value which for example in this case is equal to two.

154
00:09:38,350 --> 00:09:44,470
So in this case x would take the values from zero up to one which is these two values okay.

155
00:09:44,470 --> 00:09:49,600
And then we are just checking whether board at x at column is equal to q okay.

156
00:09:49,600 --> 00:09:54,130
So board at x would give us the row and column gives us the column.

157
00:09:54,130 --> 00:09:57,940
So we are checking whether these two cells over here have a Q or not.

158
00:09:57,940 --> 00:09:59,410
And if they do have a.

159
00:09:59,860 --> 00:10:05,320
It would mean that we cannot fill a queen over here, and in that case, we would just return false.

160
00:10:05,350 --> 00:10:09,220
Okay, now proceeding to check the top left diagonal.

161
00:10:09,220 --> 00:10:11,200
That's these two cells over here.

162
00:10:11,200 --> 00:10:17,530
Notice that to get from here to here, we just need to decrement the row value and the column value

163
00:10:17,530 --> 00:10:18,040
by one.

164
00:10:18,040 --> 00:10:24,340
And then to get from here to here we would just need to again decrement the row and column values respectively.

165
00:10:24,340 --> 00:10:25,750
So that's what we're doing over here.

166
00:10:25,750 --> 00:10:30,160
So we start with r being equal to row and c being equal to column.

167
00:10:30,160 --> 00:10:32,770
That's the values of this particular cell.

168
00:10:33,160 --> 00:10:38,050
And notice that this loop will go till r and c are equal to zero.

169
00:10:38,050 --> 00:10:42,790
Because zero is the last valid input for the index of the row and column.

170
00:10:42,790 --> 00:10:43,180
Okay.

171
00:10:43,180 --> 00:10:45,190
Then we keep decrementing the row and column.

172
00:10:45,190 --> 00:10:51,190
And if we find that board at R and C at any of these points are equal to q, we would just return false.

173
00:10:51,190 --> 00:10:55,720
Similarly, we also have checks for the top right diagonal.

174
00:10:55,720 --> 00:11:01,780
And notice that to go this way we would have to decrement the value of row which is what we're doing

175
00:11:01,780 --> 00:11:02,290
over here.

176
00:11:02,290 --> 00:11:05,830
But we would have to increment the value of columns okay.

177
00:11:05,830 --> 00:11:07,360
So that's what we're doing over here.

178
00:11:07,360 --> 00:11:08,620
And again it's the same thing.

179
00:11:08,620 --> 00:11:11,620
We are checking whether board at R and C is equal to q.

180
00:11:11,620 --> 00:11:16,840
And if we see that it's equal to q we would just return false which would indicate that we cannot fill

181
00:11:16,840 --> 00:11:17,890
a queen over here.

182
00:11:17,890 --> 00:11:24,130
And after we are done with these three checks, if we did not return false, we would just return true,

183
00:11:24,130 --> 00:11:29,830
because it would indicate that yes, we can go ahead and fill a queen at this particular cell.

184
00:11:29,830 --> 00:11:30,190
Okay.

185
00:11:30,190 --> 00:11:35,470
So that's how we have implemented the is valid function so quickly to review the solution that we have

186
00:11:35,470 --> 00:11:38,860
written over here we have the position x queen function over here.

187
00:11:38,860 --> 00:11:42,250
And this function takes care of filling a queen in each row.

188
00:11:42,250 --> 00:11:48,640
And to evaluate whether we can fill a queen at a particular cell, we have the is valid function, which

189
00:11:48,640 --> 00:11:50,890
has the three checks that we have discussed in detail.

190
00:11:50,890 --> 00:11:51,340
Okay.

191
00:11:51,340 --> 00:11:56,290
And again, remember initially we had to form the board because we are just given n we are not given

192
00:11:56,290 --> 00:11:56,710
the board.

193
00:11:56,710 --> 00:11:58,960
So board at this point is an array of arrays.

194
00:11:58,960 --> 00:12:04,300
And then we have to convert board function to create a new array which is an array of strings.

195
00:12:04,300 --> 00:12:07,480
And that would be pushed to the results array.

196
00:12:07,480 --> 00:12:09,220
And again that happens over here.

197
00:12:09,220 --> 00:12:14,740
If row is equal to n we would have hit the base case and we would make a new array which is an array

198
00:12:14,740 --> 00:12:15,550
of strings.

199
00:12:15,550 --> 00:12:17,440
And we would push it to the results array.

200
00:12:17,440 --> 00:12:23,500
So this ensures that we are pushing a snapshot of the current instance of how the board looks like to

201
00:12:23,500 --> 00:12:24,280
the results array.

202
00:12:24,280 --> 00:12:30,640
And finally, when we get all the possible ways of filling in queens on a board which is of size n into

203
00:12:30,640 --> 00:12:33,370
n, we will just return the results array.

204
00:12:33,370 --> 00:12:35,410
So this is how we can solve this question.

205
00:12:35,410 --> 00:12:39,280
Now let's go ahead and run this code and see if it's passing all the test cases.

206
00:12:40,450 --> 00:12:43,000
And you can see that it's passing all the test cases.

207
00:12:43,000 --> 00:12:46,270
Now in case you're stuck somewhere do make use of the user logs.

208
00:12:46,270 --> 00:12:47,890
So that will help you debug your code.