For many problems, we have to search through a set of possibilities in order to find the solution. So there is no clear solution that we can directly reach. So we have to systematically search for it. So we keep building candidate solutions one step at a time.
Now it might be that the solution that we are trying to get doesn't work. So we hit a dead end and then we undo the last step and try the next option. Imagine for instance if you are solving a Sudoku.
So you have a grid. and then you start filling up things and then at some point you realize that there's nothing you can put here so then you go back and you have to change something you did before so we have to backtrack we have to go forwards trying to solve the problem and at some point when we realize that we are stuck we cannot solve the problem again we have to go back and change something we have done before and try something else so one of the classic problems of this coin is called the eight queens problem so the problem is to place eight queens on a chess board so that none of them attack each other. Now if you have ever played chess, you would know that a queen is a very special piece. It can move any number of squares along a row, column or diagonal.
So for instance if you place a queen here in the third row on the third column, then it could move anywhere up or down the third column, anywhere left or right on the third row and along the two diagonals on which the square 3, 3 lies. Now since it can move along these columns, it can also capture any piece that lies along these rows. So the queen is set to attack all these squares.
So the squares to which the queen can move are said to be attacked by the queen. So our goal is to place queens so that they do not attack each other. So if we have a queen here, then we cannot put another queen in any of the red squares. We have to put it somewhere else.
So for instance, we could put a new queen, say for instance, here. This would be okay or here, right. and then it if i put a queen here in turn it will attack more pieces like it will attack these squares and it will rule out some more options so i will not be able to place queens there and so on okay so we want to see if we can place eight queens now we can't place more than eight queens because there are only eight rows if you place nine queens two will be on the same row or the same and the same column so they will have to attack each other so eight is clearly the limit the question is whether we can actually put it So, we can generalize this question and ask not for 8, but n.
Supposing I have a chess board in which there are n rows and n columns, can I place n queens on such a chess board? Now, for n equal to 1, the question is trivial because you only have to put one queen on one square. Now, it is easy to see that n equal to 2 is impossible because if I have two squares and wherever I put a queen, say here, it will attack all the remaining squares.
So, no matter where I put the queen. Every other square will be on the row column or diagonal of that queen and so there is no possibility of putting a second queen. It turns out that 3 is also impossible.
So supposing we start by putting a queen on the top left corner. Then we will see that it blocks out the first column, the first row and the main diagonal. This leaves two slots open for the second queen. But wherever we put, whichever of the two we put, it will block the other one. So once we put a queen in one of those slots, the other one is on the same diagonal and there is no free slot for the third queen.
So, just by exhaustive analysis we can show that n equal to 3 is actually impossible. For n equal to 4, for a 4 by 4 board it does turn out to be possible. We should not start at the corner but one of the corners.
So, supposing we put it in the second column then we get this pattern of blocked squares. Then we can find an empty slot on the second row right at the end. So, we put a queen there.
It blocks off certain or some more squares in the last column and in that diagonal. but this still leaves one slot in the third row. Unfortunately, the third queen doesn't block the last slot on the fourth row and we have this kind of symmetric pattern where everything is one off the corner in which none of the queens attack each other. Now it turns out that once we cross n equal to 4 for 5, 6, 7, 8 you can show that there is always a solution possible. Our task is to find such a solution.
How do we find a solution for n greater than or equal to 4? So as we observed, the first thing we know is that there can be exactly one queen in each row and in each column because queens attack the column and row on which they lie. So if we have two queens in the same row or the same column, they will necessarily attack each other. Since 8 is the classical size of a chessboard, let us do specifically an example for 8 queens. So we want to place the queens now row by row.
We know that there is exactly one queen in each row. So let us first put a queen in the first row. Then based on that put a queen in the second row and so on exactly as we did for the 4 by 4 case that we saw in the previous slide. So in each row we would place a queen in the first available column given the queens that have already been placed so far. By available we mean a square which is not attacked so far.
So we start with an 8x8 board and in the first row now everything is available so by our analysis we are going to put a queen in the first available column maybe the top left. Once we do this it blocks out the first row and column and the main diagonal so all the shaded squares are now under attack. We move to the second row and we try to put a queen in the first available column. This is the third one and this in turn will attack another set of rows columns and diagonal squares.
Now we move to the third row and in the fifth column we can place a queen and this one again attacks some squares. So we have added some colors to indicate as each new queen is placed which squares are newly under attack by the new queen. Some of them are attacked by multiple queens.
For instance the yellow queen Attacks the blue square on the diagonal which was already attacked by the first queen So we leave it blue for now in this way we can proceed so we put a fourth queen on the fourth row Okay, and then this is a mistake This should be already attacked by this queen and then we place a fifth queen and then a sixth one and then a seventh one And now we find that all the squares in the eighth row are actually blocked So there is no way to extend the solution to put the 8th queen. So we have to do something about this. We can't place a queen in the 8th row. So since we can't put a place a queen in the 8th row, we have to go back and change something we did before.
Now the last thing we did was to put a 7th queen. So we do that and we find that unfortunately for the 7th queen we had only one choice. So we have no other choice for the 7th queen. So though the 7th queen could not lead to a solution.
It was not the choice of the 7th queen which actually made a problem, but it was something earlier. So then we go back and try to move the 6th queen. So once again if we remove the 6th queen, then this unblocks a few squares, but at the same time there was no other place to place the 6th queen on the 6th row. So again, this was a unique choice that we had made.
Now if we go back to the 5th queen, then we find that there is a way to place the 5th queen in a different place, namely to move it to this slot. So we can move this. fifth queen to one slot to the right and try again.
So having gone back from the eighth square which was eighth row which is completely blocked to the seventh row which had only one choice to the sixth row which had only one choice we come back to the fifth row and now we try the next choice for the fifth row. So we try the next choice for the fifth row then we get this pattern of squares and now we see for example that we can't put a sixth thing so both the choices for the fifth row actually turn out to be bad. So we would now have to go back and try a different choice for the fourth row and so on. So this is what backtracking is all about.
We keep trying to extend the solution to the next step. If we cannot, we undo the previous move and try again. And in this way, we exhaustively search through all the possible solutions. But we do it in a systematic way. We don't go back and randomly reshuffle some of the choices we made before.
We go back precisely one step and undo the previous step. So at each step, we have a number of choices. We go through them systematically. For each choice, we try to extend the solution. If the solution does not get extended, we come back, we try the next choice and when we exhaust all choices this level, we report back to the previous level that we have failed, then they will try their next choice and so on.
So the key to backtracking is to do a systematic search through all the possibilities by going forwards and backwards one level at a time. So how would we actually encode this kind of an approach? Specifically for the eight queens problem. So our first Question is how to represent the board because the board is what keeps changing as we make moves and undo them. So the most obvious way for an n-queen solution is to represent the board literally as an n by n grid.
And since Python numbers list position from 0 onwards, we have an n by n grid and we number the columns not 1 to n but 0 to n minus 1. So we will have rows 0 to n minus 1 and columns 0 to n minus 1. And we can now put a value 1 or 0 or true or false to indicate whether or not there is a queen at the square i, j. i is the row, j is the column. So we can have a two-dimensional list bold, a list of lists which has n-1 by n-1, 0 to n-1 and 0 to n-1 is the valid indices. And we say that bold i, j is 1 to indicate that the queen is at i, j.
and therefore if it is 0 it indicates there is no queen. So, there are two possible values for every square. Of course, we also know that there is only one queen per row. So, this particular thing though it has n minus n into n, n squared entries it will only have actually n ones at any given time.
So, we can optimize this likely by just having a single list with entries 0 to n minus 1 where we say that the ith entry corresponds to the ith row and we record the column number. So, if board of i is equal to j it means that in row i the queen is at column j. So, the queen is at position i comma j. So, with such a data structure this is the outline of how our strategy works. So, what we have to do is place each queen one at a time.
So, we are just writing a function which tries to place a queen in row i given the current state of the board. So, we pass it the current state of the board as one argument and we pass it the row number i that we are going to. So, we would initially start it with an empty board and with row 0. Now, we run through each column and check whether the row column position that is the square i comma c is available. If it is available, we then put a queen there and we of course have to update the board. So, we will come back in a minute, but in our case the updating board just means setting board i equal to c if we have the one dimensional representation.
Now, if we have actually put the last queen, if i was n minus 1, then this is the last queen, right. So, if it is an 8 queen problem, then when we have put queen number 7 starting from 0, then we are done. So, we can return true.
However, if this is not the last queen, then we have to continue. So, what we need to do is now with the new board, we have to place one more queen. So, we recursively call this function incrementing the row to i plus 1 with the updated board which we have just put.
and this will return true or false depending on whether it succeeds or not. So we record its return value in the name extend solution. So depending on whether this succeeds or not we check if extend solution is true that is the current position reach the end.
Now when would it be true if it succeeded in going all the way to level n minus 1 and n minus 1 returns true. So when n minus 1 returns true then n minus 2 will return true and so on and then our level i will also get the value true so then we can also return true. So if extend solution returns true we also return true saying that so far I am good.
On the other hand if extend solution returns false it means that given the current position that I chose for row i nothing more could be done to extend this to a full solution. So this position must be undone. So we have to undo this move.
So we have to whatever we did earlier to update the board. So this update has to be reversed at this point. So, we have to reverse the effect of putting it at IC ok and then when we do this it will go back and it will try the next C and now if we have actually run through all the C's and we have not returned true at any point then python has this else which says that the for loop terminated without coming out in between ok.
So the for loop terminates normally it means we have run through every possible c that was available and for none of them did we return true. That means that there is no way to currently put a queen on row i given the board that we have. So we should return false saying that the board that we got is not a good one. Then the previous row will now get a false and retry the next position and so on. So this is the recursive solution that we get.
We will see an actual python implementation but we have to do a little bit more work to figure out how to actually implement this. So, the crucial thing in the implementation that we saw the previous one is that we have to update the board when we place the queen and update the board when we undo it and we also have to check whether IC is available. So, we had two representations, a two-dimensional representation with zeros and ones and a one-dimensional representation which gives us the column position for each row to keep track of the queens in the board.
So, in order to determine whether a square is free or not. We need to have a better way to compute how the squares are attacked by queens. So, a simple way would be to just say that along with a two-dimensional representation of the board, we denote like we had done pictorially in the example we worked out. We denote by what we had called as kind of colored square whether or not an attack a square is attacked.
So, we say attack i j is 1 if it is attacked by a queen otherwise it is 0. Now, the problem with this is that a given square i j could be attacked by more than one queen right. So, when we undo a queen it will obviously attack many squares but not all those squares become free by removing that queen because some of those squares are also attacked by other queens which we had placed earlier. So we need to be careful when we remove a queen in order to mark squares which were attacked as being free. Well one way to do this okay is to actually number the queens and record the earliest queen that attacks each square.
So, we say attack ij is k if ij was first attacked by queen k and attack ij is minus 1 if ij is 3. So, when we remove queen k we reset attack ij with value k to minus 1 and all other squares are still attacked by earlier queens. So, we can explain this very easily with the picture that we had before. So here is how we had represented our boat. When we put the blue queen, we marked all squares of the blue queen attacked with blue as blue solid squares. Then when we put the red queen, we only attacked, we only marked with red those squares, new squares which are attacked.
For example, this particular square, which is attacked by both red and blue, was already attacked by blue, so we did not mark it. So in this way, with each new queen, queen i that we put, we only mark the squares which are attacked by queen i. So, the colors here represent the queen numbers. So, the blue squares are queen 0, the red squares are queen 1, the yellow squares are queen 2 and so on.
So, when it comes to undoing for instance now we want to undo this particular thing. Now this when we put it had only one white square there was no free squares other than this. So, we did not add any new attack. So removing it does not actually change anything regarding the attack position only makes that particular square itself free does not un-attack any of the other squares. Now when we remove this orange queen then we have to remove all the orange squares which were placed under attack only after adding the screen and that turns out to be these two on the bottom row.
So when we undo this one we will find those two get under. Similarly when we undo the purple okay so what we had done actually was precisely this more efficient implementation of how to keep things how to record what is under attack. So we are going to now keep an attack array which says that attack ij is k if it is first attacked by queen k and when we remove queen k we reset to minus 1 saying that that square is free precisely if the value is currently k.
Now this would work the only difficulty is that it requires n squared space. We saw that we could replace the board by a linear thing from a n by n array with zeros and ones. We could replace it by a single array which had board i equal to j.
So, the question is can we replace attack by a linear array. Now, one thing to remember is that though attack itself is an n squared array, attack undoing the attack does not require us to actually look at all n squared entries. Once we fix the queen to undo, we only have to look along its row column and diagonal and remove all entries with the value equal to that queen on that row column and diagonal. So, the updates are not a problem. The updates are linear.
Adding and removing a queen only requires us to look at a linear number of cells in this array, but the array itself is quadratic. So can we improve our representation to use only order n space? So to do this we just have to look a little closer at the problem.
So how many queens attack row i? Now if you look at the row as a whole, remember we place only one queen in each row and in each column. So, only the queen on rho i actually attacks rho i.
Similarly, only one queen is in column j. So, therefore, there is only the queen in column j which attacks that column. So, if we look at an individual square, then if we are in the center of this for instance, then this particular square can be attacked from four directions.
It can be attacked from column j. the column in which it is or the row in which it is or it can be attacked from this main diagonal or the off diagonal. The main diagonal is the one from top left which I could call northwest and the one off diagonal is the one from the southwest. So, there are four possible queens that could be attacking the square.
So, there are four directions in which a square could be under attack. So, it might be better to represent these four directions rather than the squares itself. The representation we have now is to say that this particular square is attacked by queen k but it doesn't tell us from which direction queen k is attacking. It doesn't tell us whether pink is attacking it from the row or the column or the data So rows and columns are naturally numbered from 0 to 7 But how about diamonds now if you look at a diagonal from the northwest? Okay, so let us call these directions northwest southwest northeast and southeast If you look at a decreasing diagonal a diagonal that goes from top to bottom like this, okay?
Then what we find is that this difference the column minus the row is something that will be the same along every square on that diagonal. For instance look at this diagonal it starts here, here the column number is 2 and the row is 0. So, 2 minus 0 is 2. If we go to the next item of the diagonal it is 3 minus 1 which is again 2 then 4 minus 2 is again 2 and so on. So, if we go along this diagonal for all these squares c minus r where c is the column number and r is the row number. The difference is exactly 2 and you can check that nowhere else on this square on this grid is this true.
As another example if you look at this particular thing we have 0 minus 4. So, this difference is minus 4 and similarly 3 minus 7 is also minus 4. So, everything along this particular diagonal has a difference minus 4. Now if you look at the diagonals going the other way then we will find that the sum is an invariant. Here for instance we have either 6 plus 0 or 5 plus 1 or 4 plus 2. 2 plus 3, 3 plus 3 and so on. So, along this purple diagonal c plus r is equal to 6 everywhere and along this green diagonal we have 7 plus 5, 6 plus 6 and 5 plus 7. So, c plus r is equal to 12. So, we can now conclude that a square at position i j is attacked. If it is attacked by queen in row i or in column j or if it is along the diagonal whose difference is j minus i or if it is along the diagonal whose difference is j plus i whose sum is j plus i.
So, we can now come up with a representation which only keeps track of rows, columns and diagonals which are under attack and from that we can deduce whether a square is under attack. So, we say that rho i is 1 if rho i is under attack where i ranges from 0 to n minus 1. Similarly, we can have an array which says Column i is attacked and then column i is set to 1 provided column i is attacked for again i between 0 and n minus 1. Now when we look at the diagonals we have these two types of diagonals. So the northwest to southeast diagonal is the one where the difference is the same.
And if you look at the differences if you go back then you see the differences at this diagonal here the difference is 7 minus 0 is 7. And here the difference is 0 minus 7 is minus 7. So it goes from plus n minus 1 to. minus n minus 1. On the other hand if you go the other way then the sum at this point is 0 plus 0 is 0 and the sum over here is 7 plus 7 is 14. So, the sums along these diagonals are 0, 1, 2, 3, 4 and so on. So, this is 1, this is 2, this is 3 and so on right.
So, we have these northwest to southeast diagonals running from minus n minus 1 to n minus 1. This gives me the number effect. So, this is the difference. If the difference is say 6 I know which squares are there, the difference is minus 3 I know which squares are there and the possible range of values is from minus 7 plus 7, minus n minus 1 to plus n minus 1 and for the other direction it is from 0 to 2 times n minus 1. In our case 2 times n minus 1 is 2 times 7 which is 14, so 0 to 14 but if we have an n by n thing we have 2 times n minus 1. So, this gives us an order n representation of the squares under attack.
So, therefore, We look for if we want to see if an i j square is under attack, we check whether it is rho i is 1 or column j is 1 or j minus 1 diagonal is 1 or i plus j diagonal is 1. If any of these is 1, then it is under attack. If all of these are 0, then it is not under attack, right. So, i j is free provided rho i column j, the northwest to southeast diagonal j minus i and the southwest to northeast diagonal j plus i are all equal to 0. When we add a queen at i, j, first we update the board representation to tell us that there is now the ith row is set to the jth column and for the appropriate row, column and diagonal corresponding to this square, we have to set all of them to be under attack.
So, row i becomes under attack, column j becomes under attack, the j minus 1 diagonal on the decreasing diagonal and j plus ith diagonal on the increasing diagonal all get set to 1. And undo is similarly easy, we have to first reset the board value to say that the i-th queen is not placed. So, we could use say minus 1. This is not a valid value because the values are 0 to n minus 1. So, minus 1 indicates that the i-th queen is not placed at this moment. And we reset this row and this column to be equal to 0 because this row and this column are attacked only by this queen. Remember, we cannot have two queens on the same diagonal because they would attack each other.
So, at any given point, each one of these rows, columns and diagonals is attacked by a single queen and it must be attacked by the queen at i, j. So, only the queen at i, j can attack all of these because if it were under attack by another queen, we could not have placed a queen at i, j. So, the fact that it was free before. indicates that all of these got attacked only by the current queen.
So when we remove the current queen we must reset them back to zero. So one implementation detail for python is that instead of keeping these five different data structures we have a board and a row and a column and all that we can keep it as a single nested dictionary. So it's convenient to call it board and we'll have at the top five key values indicating the five sub dictionaries. So the queen position we will call the key queen. So, instead of saying board i is j we will say board with queen as the key at position i is j.
Then we will say instead of row i is 1 or minus 1, we will say that the board at key row is 1, similarly board at key column, board at north west to south east and board at south west to north east. So, we have just converted it so we do not have to pass around 5 different parts to each function, we just have to pass a single board. which is a dictionary which contains everything of interest.
So, remember that this is how we tried to give our solution. So, we wanted to place a queen in row i and for each column that is available we would try to update the board and so on. So, now we have now better ways to do these things right. So, we have shown that using this dictionary or these five different representations we can check whether a row and column is available how to update the board when we place a queen and we undo the queen.
So, here we have an actual python implementation of what we discussed. So, we have this function here which is called place queen ok. So, place queen we said takes the row i and the board and the first thing it does it has to determine what is the value of n. So, we just take So, remember that board is now dictionary.
So, board of queen will tell us how many rows there are in the thing. So, if we take the length of the keys of board of queen we get n. So, this is just a way of recovering n without passing it around.
So, now what we do is for every possible value from 0 to n minus 1 that is for j for all column values we check if i j is free in the current board. If it is free then we add a queen. This is exactly the code that pseudocode we had. If i is n minus 1 we return true otherwise we try to extend the solution by placing a queen at the i plus 1th row. If the solution does extend we return true otherwise we undo the queen.
So, undoing the queen will remove this queen and also update the code and finally if this loop goes all the way through for every possible column and does not return true then we means it means we cannot place a queen on the i th rows we will return false. Now, the main function that we have the main code will start off by initializing board to be an empty dictionary it will ask the user how many queens what kind of board we have n by n so remember we take the input it will be a string we convert it using int and we record this as n right so it asks for a number converts it to an int and passes it as n then we will initialize the board with the number n we need n because we need to know how to set up that remember that the indices run from 0 to n minus 1 or from n minus n minus 1 So, n is required in order to initialize the dictionary. And finally, we try to place a queen. So, initialization will set up an empty board where nothing is under attack.
Then we try to place a queen in the 0th row on this board. If it succeeds, then we have a function that prints the board. So, let us see how these other functions work.
So, let us first look at the function which initializes the board. So, initializing the board says, First of all for every key for each each of these sub dictionaries queen row column northwest southeast southwest or northeast we first set up a dictionary with that key. So this is create an empty dictionary.
Now for three of these things for queen row and column right the indices are 0 to n minus 1. So for i in range we just set up the key value i to point to minus 1 in case of queen that says that the queen and row i has not been placed. And for row and column these are the attack ones which says they are 0 if they are under not under attack and 1 if they are under attack. So, the initial thing is to say 0. Now, similarly for the northwest to southeast the range goes from minus n minus minus n minus 1 to plus n minus 1. So, if in the range function since we give the upper bound as n we set set every key in this to 0. Similarly for 0 to 2 n 2 into n minus 1 we want to set the southwest to northeast diagonals to be 0. This is one reason here why we are using a dictionary because for the other things of course we could use a list right 0 to n minus 1 is the natural list index.
But here we have these strange indices which go from minus n minus 1 to plus n minus 1 or so on. So that is why we use a two level nested dictionary. So this initializes the board. How do we print a board? Well for every row we sort the rows.
So we take board dot queen dot keys will give us 0 1 up to n minus 1 in some random order. We sort them and for each such row we print the row and the column number for that row. So this happens when we have a successful solution. When is a position free well we check whether board the row entry is 0, the column entry is 0, the diagonal entry j minus i is 0 and the diagonal entry j plus i is 0. This is exactly as you said before and finally what happens when we add a queen right when we add a queen we have to place it. So, we set the queen entry for row i to j and then we mark the corresponding row column and diagonal to be 1 and when we undo a queen we set the queen entry to be minus 1 and the row column and diagonal entries to be 0. These are all exactly what we wrote in the pseudo code they just been formalized in python code.
Now we can run this code and verify that it works ok. So, for this so here we have this code 8 queens dot pi ok which is the code that we just saw in the editor. So, now if I run this code as python 3.58 queens.py so this is by the way if you have a python program you can run it directly without first Invoking it and then importing it if you do this it will ask us how many queens you want so for instance if we give It the number 4 then we will get the solution that we saw in the earlier example.
Okay. It's not very Printed out very neatly. Okay, so if we give the number 8 then we'll get one solution like this It turns out that you can actually change that print board function. I won't show you the code but to print it out in a more user friendly way.
So I have another function which is called pretty. So if I do this then it shows me the four queen solution in a more readable form. So you see exactly the kind of off diagonal positions. and if I do for 8 queens then you see there is an extra column so there is some mistake in that but there is an extra column but basically you can see that if you ignore the last column this is showing you the position of the queens in the first 8 queen solution right. So, it is very straightforward once we have got the representation worked out and the structure of the code worked out it is very easy to transform it into actual python code.
So as a final step suppose we want not one solution but all solutions. So we don't want the previous thing the moment you find a solution then it turns true and then every previous level also returns true and eventually we print out the code. So supposing we don't want to stop at the first solution but keep printing out it's actually much easier.
Then what we do is we just keep going through all possible positions and whenever we reach the final step if we actually a solution reaches the final step then we record it in our case you might print it okay otherwise we extend it and go to the next one right So actually it's much simpler to print all solutions than it is to print a single solution because we don't have to remember whether our solution extends or not. It's really running through every possible solution. The only thing is that it will not run through every solution to the very end and then decide it doesn't work.
It's not like we are putting all possible queen positions and then trying it out. We are trying it out for smaller things because once we get stuck at say position 5 then it won't try to extend this. It will come back and so on.
But this is just a much simpler loop which just prints all solutions. So, here is the code it is exactly the same code otherwise the only thing is the place queen function is much simpler now we just try for every j in range 1 to 0 to n minus 1 if it is free we add the queen if we have reached the last row we print the code otherwise we extend the solution and then we undo the queen and try the next one right. So, for every j so for every j we are going to first add the queen.
If it managed to place it, extend the solution and finally we are going to undo it and try the next j. So we are just going to blindly try every possible j and we are not going to ever come out complaining that we have not succeeded. The rest is pretty much the same. The print board has been changed slightly and slight change in the print board is just that we have changed it so that it will print the entire thing in a single row.
So we have added this. thing which says n equal to space. So, we print the positions in a single row rather than row by row so that we can see them all.
So, now if you look at the function now and we try to print it for say for 4 queens then it prints 2 solutions these are essentially 2 rotated solutions in the same thing ok. If you do it for 8 queens for instance. then it will actually produce a large number of solutions. It turns out there are actually 92 solutions, but even these 92 solutions if you look at rotations and reflections, they come out to be much less.
But if you just look at the position of the square as it is given to you, then there are 92 different solutions that it prints out. So, this concludes our discussion of backtracking with respect to the 8 queens problem.