Eight Queens Puzzle by Magnus Lie Hetland

[Anton Vredegoor]

bokr at oz.net (Bengt Richter) wrote:

>I decided to see how it would go if I did the same thing using a set of position tuples
>to represent a board. I found that the strict ordering of the bitmap in a long was doing
>stuff I wanted (i.e., allowing me to use it as a unique dict key), so I wound up representing
>solutions as tuples of the set tuples, sorted. I changed the printout to print any of the 92
>showing a selected unique solution along with the transformation(s) to transform the unique
>to the other.

First of all, I explicitly disclaim to be able to follow precisely
what you have been programming. This reply is just because some of the
things you are talking about seem to be vaguely reminiscent of the
things I'm doing. 

IMO it would be best to find a unique representative for a solution,
for example by hashing all its mirror images and always choosing the
mirror image with the smallest hash value as a canonical
representative for a solution.


>I guess I might think that a set of small integers might map nicely to bits in an int or long
>and back, and might be useful as a hidden optimization.
>
>Another useful thing might be to make a set hashable by sorting the element list and
>hashing that as a tuple, the way I did manually. Of course it wouldn't always work, but
>if e.g., the underlying representation was a bit vector, it could work fast. You'd
>want a coercion method to accept a long or int as a bit vector integer set representation,
>or maybe an as_bitvec property that you could operate through, e.g.,
>
>    mySet = sets.Set()
>    mySet.as_bitvec |= 0xff
>
>could mean the same as
>
>    msSet = sets.Set()
>    mySet |= sets.Set(range(256))

The comment I made above is still valid here, so please take my
remarks with a grain of salt. I *think* you are advocating that sets
could (and should) sometimes be represented with long integers, which
I heartily agree with. Dictionaries are close competitors for set
programming and have the advantage of being faster. In order for sets
to have a niche in the programmers mind they should be blazingly fast
and this can be done nicely by representing them by long integer
*bitfields*. This has been discussed before, see for example:

http://home.hccnet.nl/a.vredegoor/universe

(the link above points to a broken set implementation, I'm just using
it as an example of a possible alternative way of programming sets, I
still think that it is possible to program sets this way, but progress
in this area has been halted for quite some time now, and the project
is lingering in limbo)

Specific for the queen solving problem however is the need to reduce
the search space (I'm just assuming people generalize the problem to
n-sized boards) and this can be done by using symmetry to find
solutions which represent whole categories of solutions. I'm
interested in the problem because finding representative solutions is
used in a lot of other areas too. For example -in my case- programming
go -baduk- can use it effectively and also it can be used for
programming solutions to rubiks cubes of size 5x5x5 and up.

What I like to do is to find the canonical representatives first and
to generate the list of solutions later, by applying the different
transforms to them. I think neither my code below nor your code -which
is much appreciated- do that.

A completely different problem is the need to write readable code,
which I have not solved yet. When the subject of the code is getting
more and more abstract -as is the case with mirror transforms of
abstractions from solution spaces- the advantages of Python as a
readable programming language dwindle fast. The same kind of problems
can be observed when trying to read numerical Python code or code
about three -or more- dimensional computations or when reading
difficult combinatorics code.

While the code is readable for the coder, anyone else has a hard time
to reproduce the *history* of code creation which IMO is an important
cue for why the code has become as it is instead of having been done
in a different way. Since you're posting different developmental
versions the readers get a view in your kitchen and can have a look at
your coding recipes and follow the creative process, which is much
appreciated.

As a counterexample I'm giving a piece of code of mine -also meant to
slow you down a bit to give me time to follow :-) - which does more or
less the same as your code (no competition however, your code is a lot
better) and is a bit easier to follow for *me only* [1] because I
programmed it.

I wouldn't be surprised if even seasoned coders would have a hard time
following it, while it's only very simple code. If true, the audience
can give the verdict about what kind of code is easier to read and
which guidelines should be followed to make it easier to mentally
reproduce the *flow* of the program.

Anton

[1] A friend of mine when asked for solutions to difficult
mathematical problems, sometimes replies by sending me the solution in
the form of an -incomprehensible- excel spreadsheet :-) I'm still
trying to get even the idea of using Python for communicating
solutions across, in order to not replace one problem with a solution
inside another problem.


< snip much appreciated yet hard to follow code >
>====< queenset.py >========================================================
< and returning the favor (maybe it's a lot easier to read? I don't
think so :-) >

def uniqueQueens(size):
    """n-Queens solver without solutions that are rotations
       or mirror images of previous solutions"""
    n = size
    board = [divmod(i,n) for i in range(n*n)]
    d = {}
    for solution in queens(n,board):
        c = hashmirror(n,solution)
        if c not in d:
            d[c] = solution
            yield solution

def queens(n,F,Q=[]):
    """recursive n-Queens solver"""
    if n==0: yield Q
    for i,q in enumerate(F):
        for gen in queens(n-1,prune(q,F[i+1:]),Q+[q]):
            yield gen

def  hashmirror(sz,sol):
    """turn the solution into a matrix representation and
       find the mirror image of this matrix with the smallest
       hash value, and return the hash value"""
    mat = [[0]*sz for i in range(sz)]
    for i,j in sol: mat[i][j] = 1
    def hm(mat):
        #horizontal mirror image
        m = mat[:]
        for i in range(sz/2):  m[i],m[sz-i-1]=m[sz-i-1],m[i]
        return m
    def d1(mat): return zip(*mat)
    def r1(mat): return zip(*hm(mat))
    def r2(mat): return r1(r1(mat))
    def r3(mat): return hm(zip(*mat))
    def vm(mat): return d1(r3(mat))
    def d2(mat): return d1(r2(mat))
    def I(mat): return mat[:]
    mh =1L<<100
    for T in [hm,vm,d1,d2,r1,r2,r3,I]:
        h = hash(tuple(map(tuple,T(mat))))
        if h < mh: mh = h
    return mh

def prune((i,j),F):
    """removes positions that are covered by Queen(i,j)"""
    def keep((x,y)): 
        return i!=x and j!=y and abs(x-i)!=abs(y-j)
    return filter(keep,F)

def test():
    size = 8
    for i,solution in enumerate(uniqueQueens(size)):
        print i,solution
            
if __name__=='__main__':
    test()