Eight Queens Puzzle by Magnus Lie Hetland
Bengt Richter
bokr at oz.net
Sun Aug 17 04:51:19 EDT 2003
On Sat, 16 Aug 2003 12:12:47 +0200, anton at vredegoor.doge.nl (Anton Vredegoor) wrote:
>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.
I suspect you are being too modest. Maybe immodestly modest ;-)
OTOH, I think my code has some silliness in it that is probably hard
to understand the reason for ;-P (E.g., the redundancies in the transforms
returned by the transform function generator. I really didn't need two kinds of flips.
Obviously (after seeing your code and on thinking ;-) a board has two sides with
four rotational positions each, for a total of 8 == 1 identity plus 7 T's ;-/ )
>
>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 like the general idea, but in this case ISTM we are filtering an original
set of solutions to eliminate some of them according to a filter which happens to
check for symmetries mapping to the already chosen.
Pre-calculating a canonical choice amongst the symmetries seems like potential
extra work, since it doesn't allow short cut logic to notice that one
of the transforms already happens to *be* the canonical version and can be
found already in the unique set.
See code below for a bitvector version that shortcuts in uniqueness testing.
>
>>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
Sorry to say, that got me
--
Not Found
The requested URL /a.vredegoor/universe/default.css was not found on this server.
Apache/1.3.26 Server at home.hccnet.nl Port 80
--
>
>(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)
>
I think the sets implementation could hide the representation transparently,
something like integers can be represented as 32-bit ints until they are automatically
promoted to longs. I.e., if you create a set whose members are always from range(32),
then an int can be used internally. Similarly for some reasonable number of bits of long.
That's just a hidden optimization until you want to convert the set to something else.
The thing is that the representation has implicit order, which you don't have to use,
but which eliminates sorting to get a canonical representation of the set, when/if
you want that, or other mappings dependent on canonical order.
>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.
That territory seems interesting and pretty, but I have hardly explored
any of it at all.
>
>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.
Well, as you see, first versions are hardly ever worth much as code, except
to communicate a general approach. But I think it's often worth more to
post something that seems to work and communicates the idea than to try to
polish prematurely. Almost inevitably, if someone is interested, they will
at least stimulate some ideas on evolving the design, and often much more.
>
>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 say my code is better. (but I will say the code below is faster ;-)
>
>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.
>
I think the only speed bump I hit was how that first yield in queens()
really works.
>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 >
Sorry, I will try to comment better. And I should have factored aside the
interactive presentation part. I was hacking things in to feed that.
>>====< queenset.py >========================================================
>< and returning the favor (maybe it's a lot easier to read? I don't
>think so :-) >
<snip nice original version>
<returning a little alternative, maybe not as easy to read, but I hope I imporoved a little>
First some timings. I changed your code so test just returns the appends to a list of solutions
instead of printing them, and then returns the list, so I wouldn't be timing the printing.
A version I made is almost identical in timing, even though it pre-creates various mappings and helper
functions (all of which is part of the time measured, for fairness). I won't show the code here.
Then I decided to illustrate what I meant by early out logic in filtering for uniqueness vs
calculating all mirrorings and choosing a canonical, and only then checking. Of course using
bit maps makes things faster, and accounts for most of it. I also wonder whether putting the
identity function first or last is better. I will resist temptation to test right now ;-)
[ 0:45] C:\pywk\clp\queens>tanton.py 4
testing 4 x 4 ...
anton_orig2: 0.010149
anton (new): 0.010964
bitqueens: 0.005826
[ 0:47] C:\pywk\clp\queens>tanton.py 5
testing 5 x 5 ...
anton_orig2: 0.052339
anton (new): 0.047755
bitqueens: 0.017368
[ 0:47] C:\pywk\clp\queens>tanton.py 6
testing 6 x 6 ...
anton_orig2: 0.242987
anton (new): 0.236497
bitqueens: 0.025699
[ 0:47] C:\pywk\clp\queens>tanton.py 7
testing 7 x 7 ...
anton_orig2: 1.549231
anton (new): 1.507050
bitqueens: 0.104489
[ 0:47] C:\pywk\clp\queens>tanton.py 8
testing 8 x 8 ...
anton_orig2: 10.707655
anton (new): 10.630505
bitqueens: 0.315929
[ 0:48] C:\pywk\clp\queens>tanton.py 9
testing 9 x 9 ...
anton_orig2: 81.656248
anton (new): 81.697701
bitqueens: 1.340059
[ 0:51] C:\pywk\clp\queens>tanton.py 10
testing 10 x 10 ...
anton_orig2: 675.432185
anton (new): 679.048513
bitqueens: 4.385570
The screen saver came into this last one, but you can see bitqueens
is increasing its advantage.
One more from the kitchen ;-)
====< bitqueens.py >======================================================
""" bitmap of board
0 1 2 ... n-1
n n+1 n+2 ... 2*n-1
2*n 2*n+1 2*n+2 ... 3*n-1
...
(n-1)*n (n-1)*n+1 (n-1)*n+2 ... n*n-1
"""
threatfrom = {}
queenat = {}
def qandt(n):
"""generate two dictionaries mapping i,j board index tuples to
a single bit vector board representation with a single bit
for a single queen in the queenat dict, and all the bits
covered by that queen in the bit vector for threatfrom."""
for row in xrange(n):
for col in xrange(n):
queenat[row,col] = 1L<<(n*row+col)
threat = 0L
for r in xrange(n):
for c in xrange(n):
if r==row or c==col or abs(r-row)==abs(c-col):
threat |= 1L<<(n*r+c)
threatfrom[row,col] = threat
def printsol(sol, n=8):
"""print a bit vector solution with Q in queen positions and + elsewhere."""
for row in range(n):
for col in range(n): print '+Q'[(sol>>(row*n+col))&1],
print
def solok(sol, n=8):
"""check that each queen doesn't threaten the rest"""
for row in range(n):
for col in range(n):
if (sol>>(row*n+col))&1:
q = 1L<<(row*n+col)
if (sol^q) & threatfrom[row,col]: return False
return True
def doqueens(n):
"""recursively place a queen in each successive row from 0 to n-1
by checking each column still available to see if threat from
that position attacks any queens so far on the board. If not,
place a queen there and recurse to the next row and remaining cols,
until all rows are occupied. Append that board bitvector to the
solution list and return to outer loops until every column of
the first row has been recursed through. Return the whole list."""
solutions = {}
def tryplace(board, row, cols):
for col in cols:
if (board&threatfrom[row,col]): continue
qboard = board|queenat[row,col]
if row<n-1:
xcols = cols[:]
xcols.remove(col)
tryplace(qboard, row+1, xcols)
else:
solutions[qboard]=None
tryplace(0L, 0, range(n))
return solutions
mirrorfuns = []
def mkmirrorfuns(n):
"""make a list of functions that will do the 8 mirrorings of a board
represented by a bit vector and returning same. Functions are implemented
by a table of single-bit mappings for each bit position in the board map
bitvector bits 0 to n*n-1. A board is mirrored by shifting down the
bits of the source board and using the single-bit bit mask in the table
to or into the new board bitvector image. No oring is done for zero bits,
so only n out of n*n bits require in a solution representation."""
global mirrorfuns
mirrorfuns = []
mapt1=[]; mapt2=[]; mapt3=[]; mapt4=[]; mapt5=[]; mapt6=[]; mapt7=[];
for i in xrange(n):
for j in xrange(n):
ii=j; jj=i #transpose
mapt1.append(1L<<(ii*n+jj))
ii=n-1-ii #row reverse
mapt2.append(1L<<(ii*n+jj))
ii,jj = jj,ii #transpose
mapt3.append(1L<<(ii*n+jj))
ii=n-1-ii #row reverse
mapt4.append(1L<<(ii*n+jj))
ii,jj = jj,ii #transpose
mapt5.append(1L<<(ii*n+jj))
ii=n-1-ii #row reverse
mapt6.append(1L<<(ii*n+jj))
ii,jj = jj,ii #transpose
mapt7.append(1L<<(ii*n+jj))
for table in [mapt1, mapt2, mapt3, mapt4, mapt5, mapt6, mapt7]:
def mirrorboard(sol, table=table):
board=0L
for queenbit in table:
if sol&1: board|=queenbit
sol>>=1
return board
mirrorfuns.append(mirrorboard)
mirrorfuns.append(lambda b:b) #I
def unique(solutions, n):
"""return the unique subset of the solution list, such that none
is a mirroring of another."""
mkmirrorfuns(n) # make list of the 8 functions (identity last)
unique = {}
for sol in solutions:
for mf in mirrorfuns:
if mf(sol) in unique: break # early out if match
else:
unique[sol]=None # no match, so unique
return unique.keys()
def test(n):
"""set up tables mapping coordinates i,j to bitvector board
representations of single queens in queenat, and the squares
they cover as a multibit vector in threatfrom. Then generate
a set of functions that do the eight kinds of mirroring of
bitvector boards. Then generate the full set of solutions.
Then filter the full set by accumulating a set that is not
added to unless a candidate solution has no mirrored solutions
in the unique set being accumulated."""
qandt(n) # queenat and threatfrom dicts keyed by [i,j]
solutions = doqueens(n)
return unique(solutions, n)
if __name__ == '__main__':
import sys
n = int(sys.argv[1])
solutions = test(n)
loop = ''
nsolutions = len(solutions)
for i, sol in enumerate(solutions):
assert solok(sol,n) # just for warm fuzzies
if loop in ['', 'a']:
print '\n====[ Solution # %s of %s ]====[ bitmap %X ]====\n'%(
i+1, nsolutions, sol)
printsol(sol,n)
if loop=='':
loop ='x'
while loop not in ['','a','q']:
loop = raw_input('\nPress Enter for another, a for all, q to quit: ')
if loop =='q': break
==========================================================================
Oops, some of the description of test should be in unique, where the mirror function
setup got moved. I don't like the globals, but time to close the kitchen for now ;-)
Regards,
Bengt Richter
More information about the Python-list
mailing list