Eight Queens Problem
excerpt: This covers backtracking algorithm in the context of eight queens problem. tags: backtracking
In the eight queens problem, the goal is to place the eight queens on a chessboard so that none of them can attack any of the other queens. This means, no two queens can be in the same row, column or diagonal. The diagram shows one solution to the eight queens problem.
One way to solve this problem is to try every possible arrangement of eight queens on a chessboard. A queen can be placed in any of the 64 squares. The number of possible arrangments is the same as the number of ways you can pick 8 squares of the the possible 64. So 64 choose 8 possible arrangements are possible, that is 4,426,165,368 possibilities. Enumerating all the possibilities would be time-consuming.
Backtracking works well for this problem because it eliminates certain possibilities from consideration. For example, you can start with a partial solution that places a queen on the board’s upper left corner. Placing two queens on the same row is not allowed. This means you can eliminate every possible solution that has the first two queens next to each other in the upper left corner. The program can backtrack to the point before it added the second queen and search for more promising solutions.
One backtracking step saves you the effort of examining more than 61 million possibilities. If the first queen is placed in the upper left corner, no other queen can be placed in the same row, column or diagonal. That means there are total of 21 places where the second queen cannot be placed. Eliminating all those infeasible solutions removes almost 1.3 billion possible arrangements from consideration.
Later checks remove other infeasible solutions from consideration. For example, after you place the second queen somewhere legal, it restricts where the third queen can be placed further.
|
|
The method takes a two-dimentional array of booleans named taken_square. The entry taken_square[row][col]
is true if there is a queen in that row and column. The second parameter queens_positioned specifies how many queens have been placed in the candidate solution. The algorithm starts by checking if the solution is feasible. The not_safe method checks if the given square is not legal. This method loops through the taken_square array to see if there are two queens in the same row, column or diagonal.
Next check if the queens_positioned is equal to 8. If all the queens have been positioned, the candidate solution is a final solution, so we return true. The taken_square array holds the solution. If this is not a full solution, the algorithm loops over all the rows and columns. For each row/column pair, it checks taken_square to see if that spot already contains a queen. If the spot does not hold a queen, the algorithm places the next queen there and calls itself recursively to see if the extended solution leads to a full solution.
If the recursive call returns true, it found a full solution, so this call also returns true. If the recursive call returns false, the extended solution does not lead to a solution, so the algorithm removes the queen from its new position and tries the next possible position.
If the algorithm tries all possible locations for the next queen and none of them work, this candidate solution cannot lead to a full solution, so the algorithm returns false.