Showing the Lady Her Right Place

The eight queen puzzle is a well-known problem having been used in teaching algorithms design techniques and programming. The problem is simple: place 8 queens and place them on a chess board such that none of them is in the line of attack of any other. Does such a solution exist? Yes. 92 of them, apparently (keep reading).

In fact, finding a solution manually doesn't turn out to be too hard, but may be an interesting exercise if you are interested in that kind of puzzles. But our objective here is to find an algorithmic solution. That is, to write an algorithm that finds us the solution to the problem. Again, it's a solved problem. The algorithm is all there. Nothing new. But implementing it was a challenge nevertheless.

Let me try and summarise the approach as follows:

Firstly, a bit of staring at the problem will reveal that each queen must have her own row (column).

Consequently, a succinct representation of a solution would be a list of numbers corresponding to the column in which the queen is placed, the knowledge that they are placed in separate rows being implicit.

For example, to represent the following solution:

-----------------------------------------
|    |    |    |  X |    |    |    |    | 
-----------------------------------------
|    |    |    |    |    |  X |    |    | 
-----------------------------------------
|    |    |    |    |    |    |    |  X | 
-----------------------------------------
|    |    |  X |    |    |    |    |    | 
-----------------------------------------
|  X |    |    |    |    |    |    |    | 
-----------------------------------------
|    |    |    |    |    |    |  X |    | 
-----------------------------------------
|    |    |    |    |  X |    |    |    | 
-----------------------------------------
|    |  X |    |    |    |    |    |    | 
-----------------------------------------

 we just say:

[3, 5, 7, 2, 0, 6, 4, 1]

Now, for some bit of notations. Let's say we have come up with a positioning pos. We say, satisfy(pos, i), when the sublist of pos from i to 7 (denoted by pos[i:]) forms a satisfying solution, i.e. no pair of elements in pos[i:] attack, or conflict with, each other. The above very satisfactory condition can be described declaratively as follows:

for i < 7, satisfy(pos, i) <=> satisfy(pos, i + 1) and for all j in [i + 1...7], conflict(pos[i], pos[j]) = false

for i = 7, satisfy(pos, i)

which means satisfy(pos, i) is true if and only if satisfy(pos, i+1) is true and the ith element of pos (pos[i]) doesn't conflict with any of the subsequent elements. And the recursion bottoms up with i = 7, for which satisfy(pos, i) is true no matter what.

That's all the notation I can bear before I really dive into the algorithm, which is what I really want to present. But the above also pretty completes the conceptual groundwork for writing the algorithm, which is nearly a lexical replication of the above thought. And that should convince you why recursive thinking is such a good way of designing algorithms: because it allows you to write your algorithms as declaratively as possible. What may have appeared to be very complex a phenomenon if thought of as a procedure, becomes ridiculously simple if thought of as a condition to be satisfied.

#!/usr/bin/python
import random
from counter import *

def conflict(a, b, diff):
 return (a == b) or abs(a - b) == diff

def satisfy(lst):
 if(len(lst) == 1):
  return True
 if(satisfy(lst[1:])):
  for i in range(1, len(lst)):
   if(conflict(lst[0], lst[i], i)):
    return False
  return True

def solve(pos):
 inc = makeCounter_rec(8)
 while(not satisfy(pos)):
  pos = inc(pos)
 return pos

The function satisfy works recursively, calling itself as it goes down the board, one row at a time looking for smaller and smaller partial solutions.

Did you notice that this algorithm uses a base-8 counter to sweep through the search space of all solutions (which is 8 raised to 8)? And that should answer any doubt as to the practical application of the counter program that I presented here.

You want to see the above running? Just add the below main function to the above code.

if __name__ == '__main__':
 sol = solve([random.randint(0, 7)%8 for i in range(8) ])
 print sol

Want to see a pretty printed solution? Add the below function somewhere in the above code:

def printSolution(sol):
 hline = '-----------------------------------------'
 print hline
 for pos in sol:
  print '| ',
  for i in range(8):
   if(i != pos):
    print '  | ',
   else:
    print 'X | ',
  print
  print hline
 

...and add the following line in your main function shown above:

 printSolution(sol)

If you want to go ahead and find all the solutions, here's the function and the modified main function:

def solveAll():
 inc = makeCounter_rec(8)
 solutions = []
 pos = [0] * 8
 n = 0
 while(True):
  solution = solve(pos)
  if(solution in solutions):
   break
  else:
   print solution
   solutions.append(solution)
   pos = inc(solution)
   n = n + 1
 print 'found ' + str(n) + ' solutions.'
 return solutions

If you print out the output of this function, after running for a couple of minutes, it will show you all the solutions of the problem. As mentioned above, they turn out to be 92 in number.