In Part 1 we built our first genetic solver to generate the string “Hello World!”. This time we’re going to take on the slightly more interesting 8 Queens puzzle.
In the game of Chess, the Queen can attack across any number of unoccupied squares horizontally, vertically, or diagonally.
The 8 Queens puzzle asks us to place 8 Queens on a Chess board such that none of them are under attack. Take a couple of minutes to try to solve this with something physical like pennies on a paper Chess board to get a feel for how it might work.
It turns out getting 7 Queens into safe positions on a Chess board isn’t too difficult.
Getting 8 takes a bit more work. According to WikiPedia there are only 92 solutions to this puzzle and once we remove mirrorings and rotations there are only 12 unique solutions.
Clearly a straight iterative method is impractical – we’d be looking at 64 * 63 * 62 * 61 * 60 * 59 * 58 * 57 potential locations for the Queens assuming we don’t apply some logic to reduce the search space.
So how do we solve this genetically? We have to figure out a couple of things in order to set this up for our genetic solver.
- what should our genes represent
- how do we calculate partial fitness
In the previous post the genes were the solution, so we were able to use them without transformation. We could do the same thing with this puzzle by having genes represent rows and columns where Queens are placed – one gene for the row, and another for the column. But that introduces additional complexity into the solver that we don’t need yet. Instead, let’s keep the genes as one-to-one mappings of Queen locations through the use of a somewhat more complex Point encoding scheme. We’ll assign each square on the 8×8 Chess board a symbol from the 64 symbol set ([a-z][A-Z][0-9]@#) as follows:
We’ll start off with the final code from the previous part in this series.
To convert a gene to a board position we find its index in the set of genes then convert that index to a row and column.
public static class CharExtensions
{
public static Point ToPoint(this char gene)
{
const string genes = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789@#";
var index = genes.IndexOf(gene);
var row = index / 8;
var column = index % 8;
return new Point(row, column);
}
}
Next we need a way to check all the board positions that could be attacked by a Queen from a particular board position. The Queen can attack in any of 8 different directions, which we can equate to Cardinal and Ordinal directions. We need to check each direction until another piece or the edge of the board is encountered. There are any number of ways to code this. Let’s try one that uses a variation of the Generate function from the previous post.
public static class TExtensions
{
public static IEnumerable<T> GenerateFrom<T>(this T initial, Func<T,T> next)
{
var current = initial;
while (true)
{
yield return current;
current = next(current);
}
}
}
If we number the internal board starting at zero from the top left corner we can get the attackable points as follows:
public class EightQueensSolver
{
public static int XOffsetEast = 1;
public static int XOffsetWest = -1;
public static int YOffsetNorth = -1;
public static int YOffsetSouth = 1;
public static int BoardWidth = 8;
public static int BoardHeight = 8;
public static IEnumerable<IEnumerable<Point>> GetAttackablePoints(Point queenPosition)
{
return new Func<Point,Point>[]
{
GoNorth, GoNorthEast, GoEast, GoSouthEast,
GoSouth, GoSouthWest, GoWest, GoNorthWest
}
.Select(direction => queenPosition
.GenerateFrom(direction)
.Skip(1)
.TakeWhile(IsOnTheBoard));
}
public static Point GoNorth(Point point)
{
return CreatePoint(point, 0, YOffsetNorth);
}
public static Point GoNorthEast(Point point)
{
return CreatePoint(point, XOffsetEast, YOffsetNorth);
}
public static Point GoEast(Point point)
{
return CreatePoint(point, XOffsetEast, 0);
}
public static Point GoSouthEast(Point point)
{
return CreatePoint(point, XOffsetEast, YOffsetSouth);
}
public static Point GoSouth(Point point)
{
return CreatePoint(point, 0, YOffsetSouth);
}
public static Point GoSouthWest(Point point)
{
return CreatePoint(point, XOffsetWest, YOffsetSouth);
}
public static Point GoWest(Point point)
{
return CreatePoint(point, XOffsetWest, 0);
}
public static Point GoNorthWest(Point point)
{
return CreatePoint(point, XOffsetWest, YOffsetNorth);
}
public static Point CreatePoint(Point point, int xOffset, int yOffset)
{
return new Point(point.X + xOffset, point.Y + yOffset);
}
public static bool IsOnTheBoard(Point point)
{
return point.X >= 0 && point.X < BoardWidth && point.Y >= 0 && point.Y < BoardHeight;
}
}
Next we need to determine the fitness of a particular gene sequence, or set of Queen positions. In the Hello World! problem we determined fitness by counting how many characters matched the desired result. In this case we don’t know the exact result, all we have are characteristics, so it would be better to count the negative. The equivalent for the Hello World! problem would be counting how many characters don’t match. When we get a zero fitness we’ve solved the problem. Let’s start by changing the GeneticSolver to use that logic for selecting the next parent.
public string GetBest(int length, string geneSet, Func<string, int> getFitness, Action<int, int, string> displayChild)
{
int generationCount = 1;
var parent = GenerateSequence(length, geneSet);
var parentScore = getFitness(parent);
displayChild(generationCount, parentScore, parent);
while (parentScore > 0)
{
var child = Mutate(parent, geneSet);
var childScore = getFitness(child);
if (childScore < parentScore)
{
parentScore = childScore;
parent = child;
displayChild(generationCount, childScore, child);
}
generationCount++;
}
return parent;
}
Now the fitness can be a simple count of the number of Queens that can be attacked by any other Queen.
public class EightQueensSolver
{
private const string GeneSet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123456789@#";
private const int GeneCount = 8;
public string Solve()
{
Func<string, int> getFitness = child =>
{
var queenLocations =
new HashSet<Point>(child.Select(x => x.ToPoint(GeneSet, BoardWidth)));
int fitness =
queenLocations.Sum(
x =>
CountQueensAttacked(GetAttackablePoints(x), queenLocations));
return fitness;
};
// ...
}
private static int CountQueensAttacked(
IEnumerable<IEnumerable<Point>> attackablePoints,
ICollection<Point> queenLocations)
{
return attackablePoints.Count(direction => direction.Any(queenLocations.Contains));
}
// ...
which necessitates a change in the ToPoint function
public static class CharExtensions
{
public static Point ToPoint(this char gene, string geneSet, int width)
{
int index = geneSet.IndexOf(gene);
int row = index/width;
int column = index%width;
return new Point(row, column);
}
}
Finally, we need a way to visualize the Queen positions on the board.
public string Solve()
{
Func<string, int> getFitness = child =>
{
var queenLocations = new HashSet<Point>(child.Select(x => x.ToPoint(GeneSet, BoardWidth)));
int fitness = queenLocations.Sum(x => CountQueensAttacked(GetAttackablePoints(x), queenLocations));
return fitness;
};
var stopwatch = new Stopwatch();
stopwatch.Start();
Action<int, int, string> displayCurrentBest =
(generation, fitness, item) =>
{
var board = new char?[BoardHeight,BoardWidth];
foreach (var queenLocation in item.Select(x => x.ToPoint(GeneSet, BoardWidth)))
{
board[queenLocation.X, queenLocation.Y] = 'Q';
}
for (int i = 0; i < BoardHeight; i++)
{
for (int j = 0; j < BoardWidth; j++)
{
Console.Write(board[i, j] ?? '.');
}
Console.WriteLine();
}
Console.WriteLine("generation\t{0} fitness\t{1} elapsed: {2}",
generation.ToString().PadLeft(5, ' '),
fitness.ToString().PadLeft(2, ' '),
stopwatch.Elapsed);
};
string result = new GeneticSolver().GetBest(geneCount,
GeneSet,
getFitness,
displayCurrentBest);
Console.WriteLine(result);
return result;
}
And we’re ready to run it. Let’s see what happens.
public static void Main()
{
new EightQueensSolver().Solve();
}
output:
...Q..Q. ........ ........ ..QQ.Q.. ........ ......Q. Q....... .Q...... generation 1 fitness 64 elapsed: 00:00:00.1066393 ...Q.... ........ ........ ..QQ.Q.. ........ ......Q. Q....... .Q...... generation 15 fitness 56 elapsed: 00:00:00.1371373 ...Q.... ........ ........ ..QQ.Q.. ........ ......Q. ........ .Q...... generation 31 fitness 48 elapsed: 00:00:00.1701097 ........ ........ ........ ..QQ.Q.. ........ ......Q. ........ .Q...... generation 50 fitness 40 elapsed: 00:00:00.1983747 ........ ........ ........ ..QQ.... ........ ......Q. ........ .Q...... generation 72 fitness 32 elapsed: 00:00:00.2252662 ........ ........ ........ ..QQ.... ........ ......Q. ........ ........ generation 254 fitness 24 elapsed: 00:00:00.2629383
Wait, there are only 3 queens! What’s happening? Remember the frog? Nature is really good a filling vacuums, and so are genetic solvers. Our fitness function didn’t specify that the 8 Queens had to occupy different positions and the solver found that hole and optimized for it. So what do we do about it? Let’s return a very high value when two Queens occupy the same position so that it never happens.
Func<string, int> getFitness = child =>
{
var queenLocations = new HashSet<Point>(child.Select(x => x.ToPoint(GeneSet, BoardWidth)));
var fitness = queenLocations.Sum(x => CountQueensAttacked(GetAttackablePoints(x), queenLocations));
fitness += 10000 * (GeneCount - queenLocations.Count);
return fitness;
};
Now run it again and get output like the following:
...Q...Q ..Q.QQ.. ........ ........ ......Q. ...Q.... ........ ......Q. generation 1 fitness 14 elapsed: 00:00:00.0539012 .......Q ..Q.QQ.Q ........ ........ ......Q. ...Q.... ........ ......Q. generation 2 fitness 12 elapsed: 00:00:00.0568409 .......Q ..Q.QQ.. ........ ...Q.... ......Q. ...Q.... ........ ......Q. generation 28 fitness 10 elapsed: 00:00:00.0639691 .......Q ..Q.Q... ........ ...Q.... ......Q. ...Q.... .Q...... ......Q. generation 111 fitness 8 elapsed: 00:00:00.0836195 .......Q ..Q.Q... Q....... ...Q.... ......Q. ........ .Q...... ......Q. generation 575 fitness 6 elapsed: 00:00:00.1559271
We can let this run a long, long time and it won’t make much if any progress beyond a certain point. It stalls like our first solution to Hello world!. Clearly, randomly changing one Queen location at a time isn’t going to get us there. We’re going to have to improve our solver.
We currently have one Strategy – Mutation. We’re going to add another Strategy from nature – Cross Breeding successful individuals. In order to do that we’ll need a pool of individuals to select from. We’ll generate a number of children in each generation instead of just one and cross breed the best ones by randomly copying one gene from the second parent in place of the gene in the first parent – this is known as Crossover.
If we’re going to have a number of individuals, we’ll need a way to associate a fitness with each individual.
public class Individual
{
public string Genes;
public int Fitness;
}
Next we’ll add a convenience method to the genetic solver for generating parents
private IEnumerable<Individual> GenerateParents(int length, string geneSet)
{
Func<Individual> next = () => new Individual
{
Genes = GenerateSequence(length, geneSet)
};
var initial = next();
return initial.Generate(next);
}
And another for generating the next generation using a particular strategy.
private IEnumerable<Individual> GenerateChildren(
IList<Individual> parents,
Func<Individual, Individual, string, Individual> strategy,
string geneSet)
{
int count = 0;
while (count < parents.Count)
{
int parentAIndex = _random.Next(parents.Count);
int parentBIndex = _random.Next(parents.Count);
if (parentAIndex == parentBIndex)
{
continue;
}
var parentA = parents[parentAIndex];
var parentB = parents[parentBIndex];
yield return strategy(parentA, parentB, geneSet);
count++;
}
}
Then we’ll change the implementation of Mutate to be compatible
private Individual Mutate(Individual parentA, Individual parentB, string geneSet)
{
var parentGenes = parentA.Genes.ToCharArray();
int location = _random.Next(0, parentGenes.Length);
parentGenes[location] = geneSet[_random.Next(0, geneSet.Length)];
return new Individual { Genes = new String(parentGenes) };
}
and add a Crossover implementation that starts with all the genes from parent A and replaces one with a gene from parent B.
private Individual Crossover(Individual parentA, Individual parentB, string geneSet)
{
int crossOverPoint = _random.Next(parentA.Genes.Length);
var childGenes = parentA.Genes.ToCharArray();
var parentBGenes = parentB.Genes.ToCharArray();
childGenes[crossOverPoint] = parentBGenes[crossOverPoint];
var child = new Individual
{
Genes = new String(childGenes)
};
return child;
}
Next we’ll revise the implementation of GetBest to use a pool of parents to generate children using the Crossover strategy. If none of the children has a fitness at least as good as the worst parent then we’ll generate the next generation using the Mutation strategy. We’ll also introduce a constraint that none of the generated individuals be identical to any previously generated individual. This helps to maintain the diversity of our gene pool. We’ll use a gene pool of three times the number of items in the geneSet.
public string GetBest(int length,
string geneSet,
Func<string, int> getFitness,
Action<int, int, string> displayChild)
{
int maxIndividualsInPool = geneSet.Length * 3;
int generationCount = 1;
var uniqueIndividuals = new HashSet<string>();
var parents = GenerateParents(length, geneSet)
.Where(x => uniqueIndividuals.Add(x.Genes))
.Take(maxIndividualsInPool)
.ToList();
foreach (var individual in parents)
{
individual.Fitness = getFitness(individual.Genes);
}
parents = parents.OrderBy(x => x.Fitness).ToList();
displayChild(generationCount, parents.Last().Fitness, parents.Last().Genes);
int worstParentFitness = parents.Last().Fitness;
var children = GenerateChildren(parents, Crossover, geneSet);
do
{
var improved = new List<Individual>();
foreach (var child in children.Where(x => uniqueIndividuals.Add(x.Genes)))
{
child.Fitness = getFitness(child.Genes);
if (worstParentFitness >= child.Fitness)
{
improved.Add(child);
if (worstParentFitness > child.Fitness)
{
displayChild(generationCount, child.Fitness, child.Genes);
worstParentFitness = child.Fitness;
}
}
}
generationCount++;
if (improved.Any())
{
parents = parents
.Concat(improved)
.OrderBy(x => x.Fitness)
.Take(maxIndividualsInPool)
.ToList();
children = GenerateChildren(parents, Crossover, geneSet);
}
else
{
children = GenerateChildren(parents, Mutate, geneSet);
}
} while (parents[0].Fitness > 0);
return parents[0].Genes;
}
Finally, let’s also add a space between the visual board positions to make the displayed board look more square.
for(int i = 0; i < BoardHeight; i++)
{
for(int j = 0; j < BoardWidth; j++)
{
Console.Write(board[i,j]??'.');
Console.Write(' ');
}
Console.WriteLine();
}
Now run it again and get results like the following:
. . . . . . . . . . . . . . . . . . . . . . . . . . . . Q . . . Q Q . . . . Q . . . Q . . . . . . . . . . . . . . . . . . . . . generation 1 fitness 30008 elapsed: 00:00:00.1161487 . . . . Q Q Q . . . . . . . . . . . . . . . . . . . . . . . . . Q Q . . . . . . . . Q . . . . Q . . . . . . . . . . . . . . . . generation 1 fitness 10014 elapsed: 00:00:00.1220378 . . Q . . . . . . . . . . . . . . . . . . . . . Q . . . . . . Q Q . . Q . . . . . . Q . . . . . . . . Q . . . . . . Q . . . . . generation 1 fitness 20 elapsed: 00:00:00.1248852 . . . . Q . . Q . . Q . . . . . . . . . . Q . . . . . . . . . . . . . . . . . . . . . Q . . . . . . . . Q Q . . . . Q . . . . . generation 1 fitness 14 elapsed: 00:00:00.1344589 . . . . . . . . . . . . . . . . . . . Q Q . . . . . . . . . Q . . . Q . . . . . . Q . . . Q . . Q . . . . . . . . . . . . . . Q generation 1 fitness 12 elapsed: 00:00:00.1451020 Q . . . Q . . . . . . . . . Q . . . . . Q . . . . . Q . . . . . . Q . . . Q . . . . . . . . . . . . . . Q . . . . . . . . . . . generation 1 fitness 10 elapsed: 00:00:00.1546707 Q . . . Q . . . . . . . . . Q . . . . . Q . . . . . Q . . . . . . . . . . Q . . . Q . . . . . . . . . . Q . . . . . . . . . . . generation 2 fitness 8 elapsed: 00:00:00.2066084 . . . . Q . . . . . . . . . Q . . . . . Q . . . . . Q . . . . . . . . . . Q . . . Q . . . . . . . . . . Q . . . . . . . . . . Q generation 3 fitness 6 elapsed: 00:00:00.2303158 Q . . . . . . . . . . . . . Q . . . . . . . Q . . . Q . . . . . . . . . . Q . Q . Q . . . . . . . . . . Q . . . . . . . . . . . generation 21 fitness 4 elapsed: 00:00:00.7416604 . . . Q . . . . . . . . . . Q . . . . . . . Q . . . Q . . . . . . . . . . Q . . . Q . . . . . . . . . . Q . . . . . . . . . . Q generation 99 fitness 2 elapsed: 00:00:02.7303553 . . . Q . . . . . . . . . . . Q Q . . . . . . . . . Q . . . . . . . . . . Q . . . Q . . . . . . . . . . . . Q . . . . . Q . . . generation 316 fitness 0 elapsed: 00:00:06.9379407 A8pdL2Pq
Success!
As a final modification, let’s change the method to return null if it finds a non-optimal solution and sort the position codes in the result since their order doesn’t matter.
return getFitness(result) == 0
? new String(result.OrderBy(x => x).ToArray())
: null;
You can download the final source code from my github repository.
Go on to Part 3 or checkout my implementation of this problem in Go
[...] The algorithm reviewed in this article has a very simple problem to solve. The genes in a chromosome directly map to a solution to the problem (i.e. characters of a string). When applied to more complicated problems, the genes in a chromosome become decoupled from the problem space and are used purely as a means of encoding information. To learn more about this fascinating step up the complexity ladder, visit the 8 Queens Puzzle blog post. [...]
Thanks a lot for this series on genetic algorithms. This is really helping me understand the topic. It’s very well written, which is a rare treat!
Josh Smith
[...] I studied the most, and from which my algorithm’s gene encoding system is based, can be found here. My algorithm is heavily influenced by Clinton’s but different in several [...]