Title: Solve the eight queens problem in Python, Part 3

[A solution to the 20 queens problem found with Python]

My post Solve the eight queens problem in Python, Part 1 shows how to use the itertools library's combinations function to search for solutions to the eight queens problem.

The next post Solve the eight queens problem in Python, Part 2 solves the same problem using a slightly different approach.

Instead of generating every possible placement for the queens and then seeing which ones work, this version used recursion to generate solutions. Then, when a partial solution was found to be illegal, the program stops examining solutions that begin with that solution. This lets the program quickly ignore a huge number arrangements without generating them so it makes the program much faster.

This example looks at the problem in another way to find solutions even more quickly.

(For more information on this problem and other interesting algorithms, see my book Essential Algorithms: A Practical Approach to Computer Algorithms Using Python and C#.)

Examining Rows

One way to think of arranging the queens is to look at all possible arrangements. That's the approach taken by the first two posts.

Another way to think of the problem is to think about placing a queen on each of the board's rows. No two queens can be placed on the same row, so the problem then becomes one of finding the square on each row that should hold a queen.

The number of possible arrangements of N queens on an N×N board is given by:

[There are N squared choose N possible arrangements of N queens on an N-by-N board]

There are N ways to position a queen on each row, so the number of ways you can position queens is N×N×N×…N = N^N. The value N^N grows quickly as N grows, but it grows much slower than the previous value.

The reason this method is so much faster is that it avoids looking at any arrangement where two or more queens are on the same row. The first post in this series generated all such solutions.

The second approach tried putting queens on each of the squares in a row. It abandoned an arrangement after the second queen was positioned, but it still tried placing that second queen. Each row has N positions for the first queen and, assuming that wasn't already illegal given previous assignments, there are N - 1 positions for the second queen. That means the second approach wasted N × (N - 1) steps every time it examined a row and all those steps add up.

The new approach only needs to consider one queen on each row so it avoids all those extra tests.

The following graph shows the two functions plotted for N between 4 and 20. Both functions grow so abruptly that you can't see much on a linear graph, so this is a log graph.

[This graph compares the function N squared choose N with function N to the Nth power]

Both functions grow extremely quickly. When N is 20, the first approach gives around 1.99e31 arrangements and the second gives "only" about 1.99e24. The first function is about 10 milion times larger.

Either way that's a lot of arrangements, so the new program uses the technique used by the previous on to check partial arrangements and abandon any that is illegal.

Examining the Python Code

The new program is very similar to the previous one. The only changes are in the place_queen function and even there the differences are surprisingly small. The previous program examined all possible squares for the next queen. The new version only examines the next row.

def place_queen(num_rows, num_cols, num_queens, board, row=0): ''' Explore this test solution. Return True if we find a solution. Also return the number of test placements we make. ''' # See if the test solution is already illegal. if not board_is_legal(num_rows, num_cols, board): return False, 0 # If we have positioned all of the queens, this is a solution. if row == num_queens: return True, 0 # Extend the partial solution. Try all positions for the next queen. num_attempts = 0 for col in range(num_cols): if not board[row][col]: # Make sure this spot is empty. num_attempts += 1 board[row][col] = True # Recursively see if this leads to a solution. success, new_num_attempts = place_queen( num_rows, num_cols, num_queens, board, row + 1) num_attempts += new_num_attempts if success: return True, num_attempts # The extension did not lead to a solution. Undo the change. board[row][col] = False # If we get here, we could not find a solution from this partial solution. return False, num_attempts

This code first calls board_is_legal to see if the current board is legal and returns False if it is not.

Next, if the we have assigned queens to all of the board's rows, then this is a complete solution so the function returns True.

The code then loops through the columns in the current row. It tries placing a queen on a column and calls itself recursively to see if the partial solution can be extended to a full solution. If the recursive call finds a solution, the function returns True. If the recursive call does not find a solution, the function removes the latest queen from the test column and moves on to try the next column.

If the function cannot find a solution by placing a queen in any column, it returns False.

Comparing Times

The following table shows the times and numbers of tests used by all three algorithms.

Board Size	Enumerate All Time (sec)	Enumerate Some Time (sec)	Enumerate Rows Time (sec)	Enumerate All # Tests	Enumerate Some # Tests	Enumerate Rows # Tests
4×4	0.00	0.00	0.00	741	231	26
5×5	0.02	0.00	0.00	8,097	55	15
6×6	1.79	0.21	0.00	533,331	45,542	171
7×7	34.05	0.00	0.00	8,859,383	331	42
8×8	2388.63	9.30	0.01	433,354,409	1,502,345	876
9×9		3.42	0.00		470,048	333
10×10		98.04	0.00		11,524,035	975
11×11			0.01			517
12×12			0.03			3,066
13×13			0.02			1,365
14×14			0.31			26,495
15×15			0.28			20,280
16×16			2.49			160,712
17×17			1.54			91,222
18×18			14.63			743,229
19×19			1.04			48,184
20×20			140.97			3,992,510

The newest algorithm blows the other away! The times are not completely predictable, though, and they occasionally jump up or down as the board size increases.

The following graphs show the three algorithms' times and number of tests. It's easy to see that the later algorithms do much better than the earlier ones, but they all start to slow down for larger boards. N^N may be smaller than N² choose N, but it still grows very quickly.

[Number of arrangements checked while finding eight queens solutions]

Conclusion

The moral of the story is that the way you look at a problem can sometimes make a big difference. Examining every possible solution is much faster if you abandon solutions as soon as you can tell they won't work. In this problem, thinking about placing queens on rows is much faster than considering every possible arrangement because it lets you quickly skip all of the arrangements that hold multiple queens on the same row. This particular solution may not apply to many other problems (does it apply to any others?), but the idea that you should consider different approaches to a problem does.

Download the examples to experiment with them and to see additional details.