THE 8 QUEENS PUZZLE

In this chapter we will solve the 8 Queens Puzzle.

In the game of chess, the queen can attack across any number of unoccupied squares on the board horizontally, vertically, or diagonally.

The 8 Queens Puzzle involves putting 8 queens on a standard chessboard such that none are under attack.

Take a couple of minutes to try to solve this with something physical like pennies on a paper chessboard to get a feel for how it might work.

It turns out that getting 7 queens into safe positions on a chessboard isn’t too difficult.

Q . . . . . . .
. . . . Q . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .
. . . . . . . Q
. . . . . . . .
. . Q . . . . .

Getting 8 takes a bit more work. According to WikiPedia there are only 92 solutions to this puzzle and once we remove mirrors and rotations there are only 12 unique solutions.

There are 64 x 63 x 62 x 61 x 60 x 59 x 58 x 57 potential locations for the queens assuming we don’t apply some logic to reduce the search space. That’s a very large number, so clearly a straight iterative method is impractical.

This puzzle is like the sorted numbers project in that there are constraints on the genes, but instead of one or two constraints per gene we now have many because of the relationships between the genes that the engine knows nothing about.

Also, in the projects we’ve done so far the genes were the solution, so we were able to display them without transformation and our fitness code could simply compare them to each other or the known answer.

At a high level, the community calls the genetic encoding the genotype and the genes' ultimate form or behavior in the solution the phenotype.

The genotype is the way the parts of the problem are encoded so they can be manipulated by the genetic algorithm and/or engine.

Example: potential genotypes for this project include:

• 64 bits, one for each of the 64 squares on the board
• 48 bits, 6 for each of the queen locations, because we can count to 64 with 6 bits
• 8 integers in the range 0..63 or 1..64
• 16 integers representing the row and column location of each queen

The phenotype is how the decoded genes are used in solving the problem. In each of the examples above the phenotype is locations of 8 queens on the board.

The fitness function then evaluates the phenotype in the context of the problem being solved to return a fitness value to the engine.

Also, like in the sorted numbers project, we have multiple potential solutions, and we’re not going to hard-code them. So, we will have to calculate fitness based on characteristics.

Test class

import unittest
import datetime
import genetic

class EightQueensTests(unittest.TestCase):
    def test(self, size=8):

To start with we need to define the genotype. We will use two genes for the position of each queen – one each for the row and column. The chessboard conveniently has the same number of rows as columns (8) so we’ll use the digits 0-7.

    def test(self, size=8):
        geneset = [i for i in range(size)]

Board

We will use the genes as row and column indexes to plot queen locations on a board.

class Board:
    def __init__(self, genes, size):
        board = [['.'] * size for _ in range(size)]
        for index in range(0, len(genes), 2):
            row = genes[index]
            column = genes[index + 1]
            board[column][row] = 'Q'
        self._board = board

We could have introduced a Location class to convert and encapsulate pairs of genes as Row and Column locations but since there is a direct correlation we don’t need it. If we had chosen one of the other genotypes described above, it would have been an important step.

Display

The display function will let us visualize the queen locations

def display(candidate, startTime, size):
    timeDiff = datetime.datetime.now() - startTime
    board = Board(candidate.Genes, size)
    board.print()
    print("{}\t- {}\t{}".format(
        ' '.join(map(str, candidate.Genes)),
        candidate.Fitness,
        timeDiff))

but first we need to add a print function to Board:

class Board:
...
    def print(self):
        # 0,0 prints in bottom left corner
        for i in reversed(range(len(self._board))):
            print(' '.join(self._board[i]))

This produces output like the following:

Q . . . . . . .
. . . . Q . Q .
. . Q . . . . .
. . . . . . . Q
. . . . . . . .
. Q . . . . . .
. . . Q . . . .
. . . . . . Q .
1 2 7 4 6 6 4 6 3 1 6 0 2 5 0 7	- 3	0:00:00.005012

Printing comma separated values without a format string automatically separates them with a space.

The row of digits under the board is the set of genes that created the board layout. The number to the right is the fitness, and the elapsed time is on the end.

Fitness

To drive improvement we’ll need to increase the fitness value whenever more queens can coexist on the board.

We’ll start with considering the number of columns that do not have a queen.

Here’s a layout that gets an optimal score but is undesirable:

	Q Q Q Q Q Q Q Q
	. . . . . . . .
	. . . . . . . .
	. . . . . . . .
	. . . . . . . .
	. . . . . . . .
	. . . . . . . .
	. . . . . . . .

We’ll also consider the number of rows that do not have queens. Here’s a revised board where both situations are optimal but the layout still allows queens to attack one another:

	Q . . . . . . .
	. Q . . . . . .
	. . Q . . . . .
	. . . Q . . . .
	. . . . Q . . .
	. . . . . Q . .
	. . . . . . Q .
	. . . . . . . Q

To fix this problem we’ll include the number of southeast diagonals that do not have a queen. Again we can find a corner case as follows:

	. . . . . . . Q
	. . . . . . Q .
	. . . . . Q . .
	. . . . Q . . .
	. . . Q . . . .
	. . Q . . . . .
	. Q . . . . . .
	Q . . . . . . .

To resolve this final issue we’ll include the number of northeast diagonals that do not have a queen.

We can calculate indexes for the northeast diagonals in Excel using the formula =$A2+B$1 which results in a grid as follows

	    0   1   2   3   4   5   6   7
	0   0   1   2   3   4   5   6   7
	1   1   2   3   4   5   6   7   8
	2   2   3   4   5   6   7   8   9
	3   3   4   5   6   7   8   9   10
	4   4   5   6   7   8   9   10  11
	5   5   6   7   8   9   10  11  12
	6   6   7   8   9   10  11  12  13
	7   7   8   9   10  11  12  13  14

The indexes of the southeast diagonals can be calculated using =(8-1-$A2)+B$1 which we can visualize as follows:

	    0   1   2   3   4   5   6   7
	0   7   8   9   10  11  12  13  14
	1   6   7   8   9   10  11  12  13
	2   5   6   7   8   9   10  11  12
	3   4   5   6   7   8   9   10  11
	4   3   4   5   6   7   8   9   10
	5   2   3   4   5   6   7   8   9
	6   1   2   3   4   5   6   7   8
	7   0   1   2   3   4   5   6   7

Using the above 2 formulas along with the row and column values we can write a fitness function that touches each board position exactly once, which makes it run fast.

FITNESS RULE

The fitness function should run as fast as possible because we’re going to call it potentially millions of times.

The fitness value will be the sum of those four counts, subtracted from the maximum value (8+8+8+8, or 32). This means the optimal value will be zero and higher values will be worse. In all previous projects, higher fitnesses were better. How do we make this work? The same way we did in the Sorted Numbers problem. We add a problem-specific Fitness class where gt is wired to prefer fewer queens under attack, as follows:

class Fitness:
    def __init__(self, total):
        self.Total = total

    def __gt__(self, other):
        return self.Total < other.Total

    def __str__(self):
        return "{}".format(self.Total)

Then we count the number of rows, columns, and diagonals that have queens to determine how many are under attack:

def get_fitness(genes, size):
    board = Board(genes, size)
    rowsWithQueens = set()
    colsWithQueens = set()
    northEastDiagonalsWithQueens = set()
    southEastDiagonalsWithQueens = set()
    for row in range(size):
        for col in range(size):
            if board.get(row, col) == 'Q':
                rowsWithQueens.add(row)
                colsWithQueens.add(col)
                northEastDiagonalsWithQueens.add(row + col)
                southEastDiagonalsWithQueens.add(size - 1 - row + col)

    total = size - len(rowsWithQueens) \
            + size - len(colsWithQueens) \
            + size - len(northEastDiagonalsWithQueens) \
            + size - len(southEastDiagonalsWithQueens)

    return Fitness(total)

This requires the addition of a get function to Board:

class Board:
...
    def get(self, row, column):
        return self._board[column][row]

Test

Finally our test harness brings all the parts together.

def test(self, size=8):
    geneset = [i for i in range(size)]
    startTime = datetime.datetime.now()

    def fnDisplay(candidate):
        display(candidate, startTime, size)

    def fnGetFitness(genes):
        return get_fitness(genes, size)

    optimalFitness = Fitness(0)
    best = genetic.get_best(fnGetFitness, 2 * size, optimalFitness,
                            geneset, fnDisplay)
    self.assertTrue(not optimalFitness > best.Fitness)

Run

Now we can run the test to see if the engine can find a solution.

. . . . . Q . .
. . . Q Q . . .
. . . . Q . . .
. . . . . . . .
. . . . . . . .
. Q . . . . . .
. . Q . . . . .
. . . Q . . . Q
3 6 7 0 1 2 4 5 4 6 3 0 2 1 5 7	- 9	0:00:00

Q . . . . Q . .
. . Q . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . . . .
. . . . . . Q .
. . Q . . . . .
. . Q . . . . .
0 7 7 4 6 2 4 5 2 6 2 0 2 1 5 7	- 4	0:00:00.001003

. . . . Q . . .
. . Q . . . . .
Q . . . . . . .
. . . . . . Q .
. Q . . . . . .
. . . . . . . Q
. . . . . Q . .
. . . Q . . . .
7 2 1 3 0 5 4 7 3 0 6 4 2 6 5 1	- 0	0:00:00.098260

Some generations are left out for brevity but you can see that the engine can easily find optimal solutions to this puzzle. The solution above is particularly pleasing. We’ll see it again in another chapter.

Benchmarks

The cool thing about our implementation is it works for N queens on an NxN chessboard too, so we can benchmark it with a more difficult problem, like 20 queens.

def test_benchmark(self):
    genetic.Benchmark.run(lambda: self.test(20))

. . . . . . . . . . . Q . . . . . . . .
. . . . . . . . . . . . . . . . . . . Q
. Q . . . . . . . . . . . . . . . . . .
. . . . . . . . . Q . . . . . . . . . .
. . . . . . . . . . . . . . . . . . Q .
. . . . . Q . . . . . . . . . . . . . .
. . . . . . . Q . . . . . . . . . . . .
. . . . . . . . . . . . Q . . . . . . .
Q . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . Q . .
. . . . . . . . Q . . . . . . . . . . .
. . . . Q . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . Q . . . .
. . . Q . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . Q . . .
. . . . . . . . . . Q . . . . . . . . .
. . . . . . . . . . . . . Q . . . . . .
. . . . . . Q . . . . . . . . . . . . .
. . . . . . . . . . . . . . Q . . . . .
. . Q . . . . . . . . . . . . . . . . .
10 4 11 19 5 14 6 2 17 10 14 1 8 9 18 15 3 6 4 8 13 3 2 0 1 17 15 7 9 16 7 13 12 12 19 18 0 11 16 5	- 0	0:00:00.639702

We didn’t change any code in the genetic module, so we can just run the N queens benchmark.

               Benchmark
average (seconds)  |  standard deviation
----------------------------------------
      1.38         |         1.17

Summary

In this chapter we learned the difference between genotype and phenotype. This was the first project we’ve had where the genotype was different from the phenotype. We also learned that we can easily make the engine select for gene sequences with lower fitness values instead of higher ones, should that be useful in solving a problem.

Final Code

The final code for this chapter is available from:

https://github.com/handcraftsman/GeneticAlgorithmsWithPython/tree/master/ch04