1
00:00:00,260 --> 00:00:02,540
Hey there and welcome back!

2
00:00:02,570 --> 00:00:10,190
We have developed a solid understanding of backtracking and we have already solved hard problems, and

3
00:00:10,190 --> 00:00:16,610
I'm sure they must have seemed easy to you in this video, let's start with another hard problem, which

4
00:00:16,610 --> 00:00:18,590
is called the N-queens problem.

5
00:00:18,590 --> 00:00:22,700
And I'm sure that you will be able to solve this one as well.

6
00:00:22,700 --> 00:00:23,420
Easily.

7
00:00:23,420 --> 00:00:28,280
Given that we have already developed a solid understanding of backtracking.

8
00:00:28,280 --> 00:00:29,630
Let's get started.

9
00:00:29,630 --> 00:00:39,560
The N-queens puzzle is the problem of placing n queens on an n into n chessboard, such that no two

10
00:00:39,560 --> 00:00:41,690
queens attack each other.

11
00:00:41,690 --> 00:00:43,100
So this is the criteria.

12
00:00:43,100 --> 00:00:45,320
No two queens attack each other.

13
00:00:45,800 --> 00:00:53,270
Given an integer n, return all distinct solutions to the n queen puzzle over here.

14
00:00:53,270 --> 00:01:00,320
Notice it's asked to return all the possible solutions, and this is a very strong indication that probably

15
00:01:00,380 --> 00:01:03,170
we can use backtracking to solve this question.

16
00:01:03,350 --> 00:01:06,380
You may return the answer in any order.

17
00:01:06,710 --> 00:01:15,890
Each solution contains a distinct board configuration of the n queens placement, where q and dot both

18
00:01:15,890 --> 00:01:19,670
indicate a queen and an empty space, respectively.

19
00:01:19,670 --> 00:01:26,630
Now let's say that n is equal to four, and let's use this to understand this problem thoroughly.

20
00:01:26,630 --> 00:01:32,540
Now, if n is equal to four, then we have a 4x4 chess board.

21
00:01:32,540 --> 00:01:39,920
Now, before we go ahead and see what would be valid solutions for this, let's take a moment to think

22
00:01:39,920 --> 00:01:44,660
about the possible movements of a queen on a chess board.

23
00:01:44,660 --> 00:01:45,530
For this.

24
00:01:45,530 --> 00:01:48,770
Let's say a queen is placed over here.

25
00:01:48,860 --> 00:01:54,050
Now, the queen over here can move horizontally and vertically.

26
00:01:54,050 --> 00:01:56,120
So that's these two directions.

27
00:01:56,420 --> 00:01:59,390
And it can move also diagonally.

28
00:02:00,700 --> 00:02:08,230
So if you place a queen over here and because the criteria in the question says that no two queens should

29
00:02:08,230 --> 00:02:13,000
attack each other, you cannot place any queen in these cells.

30
00:02:15,320 --> 00:02:18,020
Because this queen would be attacking it.

31
00:02:18,020 --> 00:02:25,280
So if you have a queen over here, you will not be able to place any other queen in all these cells.

32
00:02:25,430 --> 00:02:31,370
Now let's take a look at what would be the solution if n is equal to four.

33
00:02:31,400 --> 00:02:35,810
So if n is equal to four we can have these two combinations.

34
00:02:35,810 --> 00:02:40,070
Notice over here this queen does not attack any other queen.

35
00:02:40,070 --> 00:02:42,530
And that's true for all these queens.

36
00:02:42,530 --> 00:02:47,870
So we have four queens in four rows and no queen attacks any other queen.

37
00:02:47,870 --> 00:02:50,840
And then this is another combination which is possible.

38
00:02:50,840 --> 00:02:59,120
And the question asks us to identify all distinct solutions for the given n n is the input parameter.

39
00:02:59,120 --> 00:03:03,140
So if n is equal to four this is the desired output.

40
00:03:03,140 --> 00:03:06,680
So over here we have a dot indicating that this is empty.

41
00:03:06,710 --> 00:03:08,150
Then we have a queen.

42
00:03:08,150 --> 00:03:10,580
Then we have a dot and another dot.

43
00:03:10,580 --> 00:03:12,890
So that's this row over here.

44
00:03:12,890 --> 00:03:14,840
And this is the second row.

45
00:03:14,840 --> 00:03:19,400
We have dot dot dot indicating that these three positions are empty.

46
00:03:19,400 --> 00:03:20,690
And then we have a queen.

47
00:03:20,690 --> 00:03:25,640
So again this over here, this row over here is one solution.

48
00:03:25,640 --> 00:03:29,930
And then this second row over here is this solution over here.

49
00:03:29,930 --> 00:03:33,950
So this is the desired output when n is equal to four.

50
00:03:33,950 --> 00:03:37,340
So we have understood the question in the next video.

51
00:03:37,340 --> 00:03:39,710
Let's think about solving this question.