8 Queen's Problem using Backtracking || Design and analysis of algorithms (DAA) || Solved Example

Ajouté : 2026-05-31

[00:00:00]Now let us discuss about eight queens problem using backtracking.

[00:00:07]So here an 8 by8 chessboard is given.

[00:00:13]We have to place eight queens on the 8x8 chessboard such that no two queens attack each other. So here we have 8 by8 chessboard. We have eight rows as well as eight columns.

[00:00:36]So totally we have 8 into 8 64 cells. So in those 64 cells we have to place eight queens such that no two queens attack each other. Okay. Uh now let us see some uh constraints.

[00:00:58]Here we have two types of constraints in backtracking. So we have to implement this concept using backtracking.

[00:01:07]So eight queens problem comes under queens problem. So we have mainly two examples of the n queens problem. First one is four queens problem. Second one is eight queens problem. So let us see the constraints here. Uh so the first constraint is uh uh implicit constraints.

[00:01:31]Here we have three implicit constraints.

[00:01:35]First one is no two queens are in the same row. So we can't place two queens in the same row.

[00:01:47]Second constraint.

[00:01:49]No two queens are in the same column. So we can't place more than one queen in the same column.

[00:01:59]Next third constraint.

[00:02:02]No two queens are in the same diagonal.

[00:02:06]So we can't place more than one more than one queen in the same diagonal. So these are the implicit constraints. The second one is explicit constraints.

[00:02:20]explicit constraints. Here uh uh in eight queens problem the solution vector is represented by x i. So totally we have to place eight queens here.

[00:02:33]Uh so here the queens are denoted by like this from q1 to q8. So q1, q2, q3, q4, q5, q6, q7, q8. Here the value of this xi. So this x i is nothing but uh the column number.

[00:02:54]x i ranges from uh 1 to 8.

[00:02:58]So x i value may be either greater than 1, greater than or equal to 1 or less than or equal to 8. So this is nothing but uh explicit constraints here. So explicit constraint specifies each row should contain only one queen.

[00:03:16]So if you take this row, so in this row we have to place only one queen. In the first row we have to place only first queen. In the second row we have to place only the second queen. So that is nothing but uh explicit constraints.

[00:03:31]Each row must contain only one queen. So there is only one queen per each row. So here the solution vector is represented by x i. So here in in in the eight rows so totally we have to place eight queens. Okay. So here this xi value may be from either 1 to 8. Okay. Uh now let us see the problem here. Uh uh totally there are 92 valid solutions are there for eight pins problem. So it is extremely difficult to show all the backtrackings. So we know when backtracking is needed. So if there is a mistake, if there is no other path then we have to do the backtracking and uh uh we need to explore some other paths. But here totally there are 92 possible solutions are there. As there are so many cells here so it is difficult to demonstrate uh all those uh solutions.

[00:04:32]Whereas if you take four pins problem we have only two solutions. So it is easy to show all those solutions. But here it is difficult to show all the 92 solutions with the corresponding backtracking. Uh here I'm showing one simple solution. So let us see that solution. Uh let us place the first queen one in the first row. So for that what I'm doing is I'm calculating middle of the middle of the middle of the this first value and the last value.

[00:05:07]So 1 + 8 means 9. So 9 by2 means 4.5.

[00:05:14]So I am placing the first queen in the fourth cell.

[00:05:20]So place queen one in the fourth cell. Fourth column. Fourth column. So we can't place another queen in the same row or we can't place another queen in the same column.

[00:05:38]We can't place another queen in the same diagonal.

[00:05:43]Same diagonal. Okay. So, let us write this dash. So, this dash specifies we can't place another queen in the corresponding cell.

[00:05:54]Now, let us place second queen. So, for second queen, how many possibilities are there? So, 1 2 3 4 5. So, five possibilities are there. So for placing the second queen it is better to use the rightmost cells from the Q1. So this is the rightmost cell from the Q1. So let us place queen two in in this cell. So we can't place another queen in the same row. Next same column.

[00:06:26]Next in the same diagonal also we can't place. In the same diagonal also we can't place. Okay. Next let us place queen three in the third row.

[00:06:40]Third row. So let us take the rightmost cells from queen two. So here we have only one rightmost empty cell from this cell. So let us place here.

[00:06:52]So we can't place another queen in the same row, same column.

[00:06:59]Next same diagonal. Okay, same diagonal.

[00:07:08]Next let us place queen four here. Here the boundary is reached. This rightmost boundary is reached. So it is better to uh set from the leftmost boundary. Here this empty cell is nearer to the boundary. Here we have second empty cell from the leftmost border. Whereas here we have fourth empty cell from the rightmost border. So it is better to choose this one. Why? Because this empty cell is nearer to the leftmost boundary.

[00:07:44]So let us place four here. So we can't place another queen in the same row, same column.

[00:07:54]Next, same diagonal.

[00:07:57]Same diagonal.

[00:08:00]Same diagonal. Okay. Next, let us place uh queen five. Yeah, for queen four, this is also diagonal.

[00:08:12]Next, let us place five. Queen five. So here from the right border. So this cell this empty cell is nearer to this border. So it is better to place queen five in this cell. Okay. So we can't place another queen in the same row.

[00:08:36]Same column.

[00:08:38]Next same diagonal.

[00:08:41]Same diagonal. Okay.

[00:08:44]Same diagonal. Okay. All are empty only.

[00:08:46]Uh next let us place six.

[00:08:51]Queen six. So here this empty cell is nearer to this border. So let us place here queen six. So we can't place another queen in the same row. Same column.

[00:09:06]Yeah. Same diagonal.

[00:09:08]Next let us place queen seven. So in the seventh row we have only one empty cell.

[00:09:15]Let us place queen eight. So here we have only one empty cell. So here the solution is so we have to place the first queen in the fourth row.

[00:09:29]Here we have to mention I'm sorry fourth column here. Here this cell represents the column number. Column number. Next place second pin in the sixth column.

[00:09:42]Next place third queen in the eighth column.

[00:09:47]Next fourth queen in the second column.

[00:09:51]Next fifth queen in seventh column.

[00:09:57]Next sixth queen in first column.

[00:10:02]Seventh king third column. Eighth one fifth column. So this is one possible solution for way eight pins problem.

[00:10:13]Another possible solution is mirror image. So mirror image means reverse the values. So 53 1 7 2 8 6 4 5 3 1 72 864 that mean so here the second solution is mirror image of this one. So queen one is placed in fifth column. Queen two third column. Queen three first column. Queen four seventh column. Queen five second column. Queen 6 eighth column. Queen seven sixth column. and queen eight fourth column.