The eight queens puzzle in Python
Posted on November 20, 2017 by Paul
The eight queens puzzle, or the eight queens problem, asks how to place eight queens on a chessboard without attacking each other. If you never played chess before, a queen can move in any direction (horizontally, vertically and diagonally) any number of places. In the next figure, you can see two queens with their attack patterns:
At the end of the article we present a Python 3 solution to the eight queens puzzle.
We can generate a solution to the problem by scanning each row of the board and placing one queen per column, while checking at every step, that no two queens are in the line of attack of the other. A brute force approach to the problem will be to generate all possible combinations of the eight queens on the chessboard and reject the invalid states. How many combinations of 8 queens on a 64 cells chessboard are possible ?
The combinations formula is
which, for our particular case is:
Clearly, the brute force approach is not practical!
We can further reduce the number of potential solutions if we observe that a valid solution can have only one queen per row, which means that we can represent the board as an array of eight elements, where each entry represents the column position of the queen from a particular row. Take as an example the next solution of the problem:
The queens positions on the above board, can be represented as the occupied positions of a two dimensional 8x8 array: [0, 6], [1, 2], [2, 7], [3, 1], [4, 4], [5, 0], [6, 5], [7, 3]. Or, as described above, we can use a one dimensional 8 elements array: [6, 2, 7, 1, 4, 0, 5, 3].
If we look closely at the example solution [6, 2, 7, 1, 4, 0, 5, 3], we note that a potential solution to the eight queens puzzle can be constructed by generating all possible permutations of an array of eight numbers, [0, 1, 2, 3, 4, 5, 6, 7], and rejecting the invalid states (the ones in which any two queens can attack each other). The number of all permutations of n unique objects is n!, which for our particular case is:
which is more reasonable than the previous 4,426,165,368 situations to analyze for the brute force approach.
A slightly more efficient solution to the puzzle uses a recursive approach: assume that we’ve already generated all possible ways to place k queens on the first k rows. In order to generate the valid positions for the k+1 queen we place a queen on all columns of row k+1 and we reject the invalid states. We do the above steps until all eight queens are placed on the board. This approach will generate all 92 distinct solutions for the eight queens puzzle.
Next, we present a recursive solution to the eight queens problem in Python 3. You can find the complete code on the GitHub repository for this article https://github.com/sol-prog/N-Queens-Puzzle.
Here is the result of running the above code in a Python REPL for a 4x4 board:
You can further enhance the implementation by adding a GUI that will let you better visualize the solutions. A possible approach is to use the tkinter module which is already included with your Python installation.
If you want to learn more about Python, I recommend reading Python Crash Course by Eric Matthes: