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

*i*th 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

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.

## No comments:

Post a Comment