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.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

def eight_queens(taken_square, queens_positioned)
  # Check if the solution is feasible
  if not_safe(taken_square)
    return false
  end
  
  # Check if we have positioned all of the queens
  if queens_positioned == 8
    return true
  end
  
  # Extend the partial solution
  for row in (0..7)
    for col in (0..7)
      # Check if the spot is already taken
      if square_available?(row, col)
        # Place a queen in this square
        taken_square[row][col] = true

        # Recursively check to see if this leads to a solution
        if eight_queens(taken_square, queens_positioned + 1)
          return true
        end

        taken_square[row][col] = false
      end
    end
  end
  
  # If we get here, we could not find a valid solution
  return false
end

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.