The uHunt Chapter 1 starred problems contain three examples of chess problems. In Chapter 3, we get back to chess with a variation on the classic eight queens puzzle. UVa 11085 is used to illustrate the algorithmic technique known as recursive backtracking.
The Problem
The original eight queens puzzle asks you to find all of the ways eight queens can be placed on a standard chessboard such that no two queens attack each other.
UVa 11085 makes a minor addition to the problem: given a starting placement of one queen per column, find the eight-queens solution you can get to in the fewest number of moves. Since a queen can move to any position in its column in one move, eight moves are sufficient to get from any such initial configuration to an eight-queens solution. However, some initial configurations require fewer than eight moves.
CP3 Chapter 3, Section 3.2.2 contains a recursive backtracking solution to UVa 750, another eight-queens variation. With a minor addition, the same solution can be used for UVa 11085. The book contains a brief description of the solution. I’ll go into more detail here.
Counting Positions
As CP3 points out, making this problem tractable requires cutting down on the number of chess positions your program considers. Here’s how that looks for a few approaches:
- Option 1: Place queens on every possible set of eight unique squares out of the sixty-four squares on a chessboard, and check whether each one is a solution. This requires considering $ {64 \choose 8} \approx 4.4 \times 10^9$ positions.
- Option 2: Two queens can’t occupy the same column, so you can optimize option 1 by placing only one queen per column. Eight possible choices for each of eight columns requires considering $8^8 \approx 1.7 \times 10^7$ positions.
- Option 3: Two queens also can’t occupy the same row. Option 2 generates some invalid positions because it doesn’t respect this rule. To reduce the possibilities further, you can generate all permutations of the numbers 1 through 8, which avoids any row number duplicates. If you read last week’s editorial on UVa 11553, you may remember that there are $8!=40320$ such permutations, which your program can search in well under a second.
- Option 4: Since queens can capture along diagonals, placing two queens on the same diagonal also leads to an invalid eight-queens solution. The recursive backtracking solution to the eight-queens problem checks this constraint as it builds valid positions. Wikipedia claims that this requires checking only 15720 possibilities. Proving this result is left as an exercise for the reader, but I did verify that my solution uses exactly that many iterations.
The Recursive Backtracking Algorithm
The recursive backtracking algorithm for this problem works by considering the eight columns from left to right, and finding a valid row position for each one. A row is valid if it meets the following criteria:
- No previous column has a queen in the same row.
- No previous column has a queen on the same diagonal. To determine if two queens are on the same diagonal, check if the distance between their row positions is the same as the distance between their column positions. For example, queens at $(2, 1)$ and $(6, 5)$ are on the same diagonal, since $|2-6|=4$ and $|1-5=4$. Here’s a board showing that position:
Note: This problem uses non-standard row and column identifiers. Rather than standard algebraic notation, it numbers the rows and columns from 1 to 8, starting at $(1,1)$ in the top left and ending at $(8,8)$ in the bottom right. I’ll also follow that convention.
To check if a queen can be placed at a particular row and column, we’ll use a function called place. This function returns true if (row, col) is a valid position for the current board, and false otherwise. To do this, it considers all of the columns that already have queens, and only returns true if the queen at the candidate position is on a different row and diagonal from any previous queen.
place(newRow, newCol)
for each prevCol from 1 to newCol-1
prevRow = row position of queen at column prevCol
if prevRow == newRow, return false
rowDist = distance from prevRow to newRow
colDist = distance from prevCol to newCol
if rowDist == colDist, return false
if we made it through the loop, return true
The distance between positions in the same row or column is just the absolute value of the difference in row or column numbers.
Now that we have a way to detect an invalid queen position, we can write our recursive backtracking function. Given a column, this function uses place to check each row until it finds a valid (row, col) position. If it finds one, it places the queen there. Then if there are any columns left to check, it recursively calls itself on the next column to the right. If it successfully places queens in all eight columns, then that board position is a valid solution.
backtrack(col)
for each row from 1 to 8
if place(row, col) is true
rowPosition[col] = row
if col < 8, backtrack(col+1)
otherwise, do something with the solution
“Do something with the solution” just means using this valid board to solve a particular variation of the eight queens puzzle. If you want to record all of the valid eight queens positions, you could print the board. For UVa 11085, the goal is to find the minimum number of moves to get from a starting position to a valid position. Therefore, we need to calculate the move count from the starting position and update the minimum if necessary:
for each col from 1 to 8
calculate distance from rowPosition[col] to startPosition[col]
if distance > 0, increment move counter
update minimum move counter
With these functions in place, we can solve UVa 11085 by initializing startPosition from the problem input, and kicking off the recursion by calling backtrack on column 1.
Visualizing the Recursion
You should now have everything you need to solve UVa 11085 and other eight-queens variations. But recursive solutions aren’t always as intuitive as their iterative counterparts. To help understand this solution better, I’ll show how the backtrack function finds its first solution.
For UVa 11085, the chessboard can be represented as a linear array of eight integers. In backtrack, that array is called rowPosition. If we initialize an array of nine integers and ignore position zero, then the row position of the queen in column i is stored in rowPosition[i], where i is an integer from 1 to 8. For example, here is the first valid solution that backtrack finds:
This board is a 90-degree rotation of fundamental solution 3 in the Wikipedia description of the puzzle.
rowPosition represents this board as [1 5 8 6 3 7 2 4]: starting with the first column, the queens are in rows 1, 5, 8, 6, 3, 7, 2, and 4.
I instrumented my solution code to help show what is going on in the backtrack method. Here’s how things start:
placed queen at (row 1, col 1)
1 0 0 0 0 0 0 0
The process always starts at position (1, 1), which is a valid position on an empty board. The zeros in rowPosition elements 2 through 8 mean that those columns are empty.
Now that we have successfully placed a queen in column 1, we can consider column 2:
(row 1, col 2) is not a valid placement
(row 2, col 2) is not a valid placement
placed queen at (row 3, col 2)
1 3 0 0 0 0 0 0
With a queen in (1, 1), positions (1, 2) and (2, 2) are not available, since a queen there would be taken by a horizontal and diagonal capture, respectively. But (3, 2) is valid, so we end up with board [1 3 0 0 0 0 0 0].
A few more recursive calls get us to column five, ending with board position [1 3 5 2 4 0 0 0]:
(row 1, col 3) is not a valid placement
(row 2, col 3) is not a valid placement
(row 3, col 3) is not a valid placement
(row 4, col 3) is not a valid placement
placed queen at (row 5, col 3)
1 3 5 0 0 0 0 0
(row 1, col 4) is not a valid placement
placed queen at (row 2, col 4)
1 3 5 2 0 0 0 0
(row 1, col 5) is not a valid placement
(row 2, col 5) is not a valid placement
(row 3, col 5) is not a valid placement
placed queen at (row 4, col 5)
1 3 5 2 4 0 0 0
But column six gives us our first backtrack:
(row 1, col 6) is not a valid placement
(row 2, col 6) is not a valid placement
(row 3, col 6) is not a valid placement
(row 4, col 6) is not a valid placement
(row 5, col 6) is not a valid placement
(row 6, col 6) is not a valid placement
(row 7, col 6) is not a valid placement
(row 8, col 6) is not a valid placement
No valid position found in column 6; backtracking
At column six, we check all eight rows without finding a valid placement. So the current recursive call completes, and we backtrack to our most recent successful placement, which was (row 4, col 5). That position met all of our placement requirements at the time, but it wasn’t possible to complete column six with that configuration. So we continue where we left off in column five:
(row 5, col 5) is not a valid placement
(row 6, col 5) is not a valid placement
(row 7, col 5) is not a valid placement
placed queen at (row 8, col 5)
1 3 5 2 8 0 0 0
backtrack has now decided that row eight is a valid queen position for column five, so the previous selection is overwritten.
This process of placement and backtracking continues until we find a valid placement for column eight, which means the board is complete. Here are the last few steps:
...
placed queen at (row 6, col 4)
1 5 8 6 7 3 6 0
(row 1, col 5) is not a valid placement
(row 2, col 5) is not a valid placement
placed queen at (row 3, col 5)
1 5 8 6 3 3 6 0
(row 1, col 6) is not a valid placement
(row 2, col 6) is not a valid placement
(row 3, col 6) is not a valid placement
(row 4, col 6) is not a valid placement
(row 5, col 6) is not a valid placement
(row 6, col 6) is not a valid placement
placed queen at (row 7, col 6)
1 5 8 6 3 7 6 0
(row 1, col 7) is not a valid placement
placed queen at (row 2, col 7)
1 5 8 6 3 7 2 0
(row 1, col 8) is not a valid placement
(row 2, col 8) is not a valid placement
(row 3, col 8) is not a valid placement
placed queen at (row 4, col 8)
1 5 8 6 3 7 2 4
*** Found a valid board ***
Notice that we had to backtrack all the way to column two to find a valid board: we now have a queen in row five of that column. Fortunately, this work isn’t wasted. Once we record our solution, we can keep right on backtracking on our way to the next valid board (which is [1 6 8 3 7 4 2 5]). After placing the last queen at (row 4, col 8) to come up with our first solution, we immediately check if there’s another valid position in column eight (nope). Then we backtrack to column seven (nope), column six (nope), and finally to column five, where a queen can sit at (4, 5) without being attacked by any of the queens in columns one through four:
(row 5, col 8) is not a valid placement
(row 6, col 8) is not a valid placement
(row 7, col 8) is not a valid placement
(row 8, col 8) is not a valid placement
(row 3, col 7) is not a valid placement
(row 4, col 7) is not a valid placement
(row 5, col 7) is not a valid placement
(row 6, col 7) is not a valid placement
(row 7, col 7) is not a valid placement
(row 8, col 7) is not a valid placement
(row 8, col 6) is not a valid placement
placed queen at (row 4, col 5)
The final recursive backtrack call doesn’t return until it has considered all valid paths in the board search tree. There are 92 valid eight-queens boards. The 92nd board found by this algorithm is [8 4 1 3 6 2 7 5].
Thoughts on Recursive Backtracking
Three of the Chapter 3 uHunt starred problems are in the category Recursive Backtracking (Easy). I found this eight queens problem to be the best of the three for learning the recursive backtracking technique. UVa 11085 has a short solution, but it takes some thinking to understand how the recursive backtrack function manages to check all of the important boards while skipping more than half of the permutations of eight row positions. With a solid understanding of this canonical problem, you can move on to the other recursive backtracking problems in Chapter 3.
(Image credit: Bill Brooks, previously at https://www.flickr.com/photos/8011986@N02/7037261775)
Chessboard images by Pedro Wave’s Chess Diagram Generator.