The Queen (sometimes also called The Minister) is the most versatile piece on the chess board. Queens can move multiple steps diagonally like camels or bishops and can move along straight lines like rooks or elephants. The only thing they cannot do is jump over obstacles like the knight or horse pieces.
The 8-Queens Puzzle asks that we place 8 such queen pieces on standard 8x8 chessboard so that no queens attack each other. Sounds easier than it is, so give this a try. The Wikipedia article presents the problem, its history, and the set of solutions that work. In this post, we study how we might solve this problem on a computer.
One solution i.e. one configuration that meets the specification to this problem is below. The article also tells us that there are a total of 92 possible solutions that are each derived from a set of 12 "base solutions" through operations like reflection and rotation. Here's also a video that discusses the problem in more detail.
Representation
We see that any valid solution must have at most one queen in every row and column. So, minimally before we check the diagonal constraints, if we were to even construct solution configurations, they would be 8 tuples, or lists of 8 elements, with digits from 1 to 8 (given the 8x8 size of the chessboard), with no repeating digits. So the above chessboard would be represented as [5, 3, 1, 7, 2, 8, 6, 4] i.e. column 1 has a queen at the fifth row from the bottom, column 2 with one at the 3rd row from the bottom, etc.
Invariants
Rotation and reflection do not change the validity of a valid solution. To see this, imagine the above chess board transformed into one represented as [4, 6, 8, 2, 7, 1, 3, 5]. This is merely a reflection of the above board along a horizontal axis. The solution remains valid.
Next consider the chessboard represented by turning the above board 90 degrees in the clockwise direction. We end up with [6, 4, 7, 1, 8, 2, 5, 3]. Also a valid configuration of pieces for the 8 queens problem.
Of course, other transformed configurations of the pictured board are possible, by rotating it 180 degrees, 270 degrees, and by reflecting about the other (i.e. vertical) axis as well.
We solve this two ways - first, through using traditional computing, and second using genetic algorithms. In the first case, we solve the problem to find the full set of 92 possible configurations, then "whittle away the shadows" to find the core set of 12 solutions. With genetic algorithms, we outline how this works with code, then look at at least one solution the program generates. Let's get started.
Types of Approaches
There are different ways one might solve this problem. One way would be to generate all possible configurations with queens placed on different rows and columns, and then check which of these is valid. Given the search space is relatively small i.e. 8*7*6*5*4*3*2 = 40320 possibilities (convince yourself you understand why this is so before reading further), we can easily examine the full space to find possible solutions. After finding the full set of solutions, we can eliminate reflections and rotations to be left with the "core set of configurations of interest".
A second traditional computing approach might be to start by placing the first queen in one of the rows on column 1, then progressively place new queens on as-yet-unused rows in columns to come, all while checking the new configuration is such that they do not yet attack each other. If they do, then try other possible rows in that column, before backtracking to an earlier column to move that queen to a different row, then move forward again trying to fit the next queen, and so on till you find a configuration that solves the problem. This method uses branch-and-bound and backtracking ideas from computer science. But again, given the search space is so small to examine with the computer, we just use the approach from the previous paragraph and ignore this one.
A third approach we can try is one that uses Genetic Algorithms. We explain this in detail in a later section.
Traditional Search-Based Solution
import itertools;
s=[1,2,3,4,5,6,7,8];
x=itertools.permutations(s,8);
t=[];
for i in x: t+=[i];
First, we use the itertools module and generate all possible unique permutations of the digits 1 through 8. These are the configurations we test.
def pconv(pm):
u=[];
for i in range(1,9): u+=[(i,pm[i-1])];
return u;
def punconv(u): return tuple([i[1] for i in u]);
Then we define two helper functions. pconv converts a board from [6, 4, 7, 1, 8, 2, 5, 3] to [(1,6), (2,4),(3,7), (4,1), (5,8), (6,2), (7,5), (8,3)] - this helps with computations, since each position is reduced to a set of coordinates in the x-y grid. punconv performs the reverse transformation so we can still print things out compactly.
def dchk(j): #cth col has queen in row n
c,n=j[0],j[1];
v=[]
k1,k2=n,n;
for i in range(c-1,0,-1):
k1-=1;
if k1>0: v+=[(i,k1)];
k2+=1;
if k2<9: v+=[(i,k2)];
k1,k2=n,n;
for i in range(c+1,9,1):
k1-=1;
if k1>0: v+=[(i,k1)];
k2+=1;
if k2<9: v+=[(i,k2)];
return v;
The very important function dchk takes as input a 2-tuple (c,n) which indicates a queen is placed in column c in row n, and computes all other cells on the board the queen attacks diagonally (horizontal and vertical attacks are already accounted for by not allowing any 2 queens from being in the same row across columns in our setup). So, for example, if a queen is placed at (5,4), then dchk would return a list of positions including (4,3), (4, 5), (3, 2), (3, 6), ... to the left, and (6, 5), (6, 3), (7, 6), (7,2), ... to the right. We can then check if these cells are occupied by other queens, and if so, disqualify a solution candidate.
def rotate(v): # rotated board configurations
N=8;
r=[];
b=pconv(v);
b1=b[:];
u=[];
while u!=b:
u=[];
for i in b1: u+=[(i[1],N-i[0]+1)];
u.sort(key=lambda tup: tup[0]);
#print(u);
b1=u[:];
r+=[punconv(u[:])];
return r[:-1];
def reflect(v): # reflected board configurations
N=8;
b=pconv(v);
m=[];
for i in b: m+=[(i[0],8-i[1]+1)];
b.reverse();
return [tuple(punconv(m)),tuple(punconv(b))];
These two functions are the rotation and reflection transforms discussed earlier, presented above in code form. Pay particular attention to the rotate function. This is an oft-asked programming question in job interviews. It can be mildly challenging to write correctly under pressure.
Now, with all the pieces in place, the next steps are relatively easy. We check each of the candidates generated from permutations of the set [1, 2, 3, 4, 5, 6, 7, 8] to see if there are collisions (i.e. pieces attack each other), and if not, we have a solution!
u=[];
for i in t:
f=0;
x=pconv(i);
for j in x:
v=dchk(j);
if len(list(set(v).intersection(set(x))))!=0:
f=1;
break;
if f==0: u+=[i];
Here, we take each candidate generated using itertools earlier, then check if any of the diagonal attack positions from dchk for each queen on the board are occupied by other queens. If not, we have a solution! So with this loop complete, u is a list of possible solutions.We can verify, there are 92 when this part of the code completes. This agrees with what the Wikipedia article says. But wait, before popping the champagne, we need to eliminate duplicates - the reflections and rotations we spoke of earlier!
v=u[:];
rr=[];
dx={};
for i in u:
r=reflect(i);
if r[0] in v: v.remove(r[0]);
if r[1] in v: v.remove(r[1]);
if i in v:
dx[i]=[];
dx[i]+=[r[0],r[1]];
rr+=[i];
x=rotate(i);
dx[i]+=x;
for k in x:
if k in v: v.remove(k);
r=reflect(k);
if r[0] in v: v.remove(r[0]);
if r[1] in v: v.remove(r[1]);
dx[i]+=[r[0],r[1]];
dx[i]=list(set(dx[i]));
We do that in this above code. For each solution, we generate reflections and tag them against that solution, we do the same with rotations. All the while, we remove these transformed versions from those we capture in the unique solution set (variable rr). When the loop completes, for each unique solution in rr, we have it as a key in dictionary dx with a list of reflections and rotations that correspond to it. Cool, huh?
With that, we are done. We have all the 12 unique solutions the Wikipedia article lists. We can verify this easily.
The Genetic Algorithms Approach
Now let's look at solving the problem with genetic algorithms (GA). This post is already too long, so I won't explain all the details of genetic algorithms here, but will present the code outlining the main points of the solution. Our goal here is to find at least one solution. To find more solutions, simple run the code for "more generations".
Generally speaking the GA code proceeds in the following steps:
- Find a shape for candidate solutions. Generate a few and use them as the "base gene pool". We call these candidate chromosomes.
- Define a fitness function to evaluate how close the candidates are to solving the problem. In each "generation" we keep the best candidates, discard the rest.
- Define reproduction functions for good candidates so you inch closer to a solution. Reproduction is of two types a. evolution through mutation - take random bits in the candidate and flip them, b. crossover - take two parent chromosomes, generate two progeny from them snipping each parent at the same point, and crossing over the two segments - this is akin to "sexual reproduction".
- Only put valid new chromosomes in the pool. At each generation check if you already have a solution using the fitness function. If you do, stop. Otherwise, propagate further.
Simple! Now let's do this in code.
First we define a set of candidates we call chromosomes in the GA context. These are 8-tuples just like in the previous code-base from earlier in the article e.g. [6, 4, 7, 1, 8, 2, 5, 3] is a chromosome.
We define a "fitness function". This tells us how close a particular candidate is to being a solution. The fitness function we use below is one that counts the number of "intersections" (i.e. instances when two queens attack each other in a solution candidate). If this value is 0, we have a solution!
def xsection(v): # fitness function
# returns a measure of quality for a configuration pm
# 0 metric means v solves the problem
r=0;
b=pconv(v);
for i in b:
ds=dchk(i);
r+=len([k for k in b if k in ds]); # number of collisions
return r;
Next, we define the mutate and crossover functions that simulate the evolution of a candidate, and "sexual reproduction" between two candidate solutions to generate better solutions over time from the gene pool we have. Of course, we pick only the more promising solutions (based on their fitness values) to generate new candidates in future generation. This is akin to Darwin's "survival of the fittest" in action. Along with mutation and crossover, we also add new chromosome material to the gene pool, ensuring that all new chromosomes that are included are valid ones i.e. use digits 1-8 once and only once.
def mutate(c1): # mutate the chromosome
n=random.sample([1,2,3,4,5,6,7,8],4);
t1,t2=c1[n[0]],c1[n[2]];
c1[n[0]]=c1[n[1]];
c1[n[2]]=c1[n[3]];
c1[n[1]]=t1;
c1[n[3]]=t2;
return c1;
def regen(): # generate new chromosome
return random.sample([1,2,3,4,5,6,7,8],8);
def validc(c1):
r=[1,2,3,4,5,6,7,8]
x=[c1.count(i) for i in r];
if x.count(1)==8: return True;
return False;
def xover(c1,c2): # crossover c1 and c2 chromosomes
t=[1,2,3,4,5,6,7,8];
k1,k2=random.choices(t,k=8),random.choices(t,k=8);
k1,k2=c1[:cpt]+c2[cpt:],c1[cpt:]+c2[:cpt];
while validc(k1)==False or validc(k2)==False:
cpt=random.randint(1,8);
k1,k2=random.choices(t,k=8),random.choices(t,k=8);
k1,k2=c1[:cpt]+c2[cpt:],c1[cpt:]+c2[:cpt];
return (k1,k2);
Now we set up the gene pool defining its size.
pool=[];
pool_sz=5000;
def create_gene_pool():
# create gene pool with 5000 chromosome seeds
global pool,pool_sz;
while len(pool)<pool_sz:
candidate=regen();
if candidate not in pool: pool+=[candidate];
return pool;
We set up variables to detect if a solution has been found, and gather up the solutions as they are found. The rank_pool_chromosomes function ranks each chromosome in the pool using the fitness function so we can keep only the top x%, throw out the rest, and use the retained ones to "breed" candidates for generations to come.
solved=0;
solutions=[];
def rank_pool_chromosomes():
global solved, pool, solutions;
# rank pool by chromosome quality using fitness function
r=[];
for i in pool: r+=[(i,xsection(i))];
r.sort(key=lambda tup: tup[1]);
if r[0][1]==0:
solved=1;
solns=[i for i in r if i[1]==0];
for s in solns: solutions+=[s];
# reduce back to pool format
pool=[i[0] for i in r];
return pool;
The nexgen_pool function creates the next generation of the gene pool. The pct input controls how much of the best parts of the current generation we retain, while the mp variable allows us to set the mutation percentage. With 10% retained for new genetic material to be introduced, 1-mp%-10% is the allocation the code makes for new chromosomes generated via the crossover method.
def nexgen_pool(pct,mp):
# repopulate pool replacing bottom pct % with better
# mp is mutate %, xp is crossover % = 1-mp-0.1
global pool,pool_sz;
pool=pool[:int(pct*pool_sz)]; # truncate pool
numm=int((pool_sz-len(pool))*mp); # number of new mutate chromosomes
numx=pool_sz*0.9-len(pool)-numm; # number of crossover chromosomes
if numx%2!=0:
numx-=1;
numm+=1;
new_c=[]; # new chromosomes
for i in range(numm):
c1=random.sample(pool,1);
t1=mutate(c1);
if validc(t1) and t1 not in pool: pool+=[mutate(c1)];
for i in range(int(numx/2)):
c1,c2=random.sample(pool,2);
t1,t2=xover(c1,c2);
pool+=[t1,t2];
while len(pool)<pool_sz:
t=regen();
if t not in pool: pool+=[t];
return;
Finally, we come to the main body of the code. We create the gene pool first, then until a solution is found, we rank the chromosomes we have, keep the top 20%, mutate them to generate 60% of new chromosomes, with 10% of new ones, and 30% new chromosomes being created using crossover. We keep doing this until we find (a) solution(s).
create_gene_pool();
num_gen=0;
while solved==0:
print('generation:',num_gen);
rank_pool_chromosomes();
nexgen_pool(0.2,0.6);
num_gen+=1;
print('solutions are:');
for i in solutions: print(i[0]);
When done, the code prints the below 10 solutions after just a couple of generations. Not bad. Given there is some randomness here, your results may be different. You can check these for correctness against the Wikipedia article.
[2, 5, 7, 1, 3, 8, 6, 4]
[3, 6, 8, 1, 4, 7, 5, 2]
[5, 7, 2, 4, 8, 1, 3, 6]
[4, 7, 5, 3, 1, 6, 8, 2]
[4, 2, 7, 5, 1, 8, 6, 3]
[6, 4, 7, 1, 8, 2, 5, 3]
[5, 7, 1, 4, 2, 8, 6, 3]
[4, 2, 7, 3, 6, 8, 1, 5]
[2, 4, 6, 8, 3, 1, 7, 5]
[6, 3, 1, 8, 4, 2, 7, 5]
There you have it - the 8 Queens Problem solved two different ways. Some interesting videos on various approaches:
Have you done this other ways I don't discuss here? Please share in the comments.
No comments:
Post a Comment