Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > Re: Eight Queens Puzzle by Magnus Lie Hetland

Reply
Thread Tools

Re: Eight Queens Puzzle by Magnus Lie Hetland

 
 
Jeff Epler
Guest
Posts: n/a
 
      08-13-2003
View the chessboard as an 8x8 grid. Each square has an x and a y
coordinate which is an integer.

The vertical distance between (xi, yi) and (xj, yj) is abs(yi-yj).
Simularly, the horizontal distance is abs(xi-xj).

Two queens conflict if they are on the same row (identical y values), on
the same column (identical x values) or on the same diagonals. To be on
the same diagonal, the horizontal and vertical distance will be the same.

The i'th queen is at the location (state[i], i), and the queen being
placed is at (nextX, nextY), and nextY > i. So the 'if abs ... in
....:' test is identical to the description in the paragraph above, but
with the parts that are known impossible eliminated (same row) and the
calculation of the vertical distance eliminates the abs() call because
it is known to give a positive result.

Jeff

 
Reply With Quote
 
 
 
 
Bengt Richter
Guest
Posts: n/a
 
      08-14-2003
On Wed, 13 Aug 2003 09:50:38 -0500, Jeff Epler <(E-Mail Removed)> wrote:

>View the chessboard as an 8x8 grid. Each square has an x and a y
>coordinate which is an integer.
>
>The vertical distance between (xi, yi) and (xj, yj) is abs(yi-yj).
>Simularly, the horizontal distance is abs(xi-xj).
>
>Two queens conflict if they are on the same row (identical y values), on
>the same column (identical x values) or on the same diagonals. To be on
>the same diagonal, the horizontal and vertical distance will be the same.
>
>The i'th queen is at the location (state[i], i), and the queen being
>placed is at (nextX, nextY), and nextY > i. So the 'if abs ... in
>...:' test is identical to the description in the paragraph above, but
>with the parts that are known impossible eliminated (same row) and the
>calculation of the vertical distance eliminates the abs() call because
>it is known to give a positive result.
>


JFTHOI, I did a version based on 64-bit bitmaps of the board and
threat patterns from a queen at any given position. I forgot about generators, sorry
I bute forced the threatfrom and queenat setup for transparency.

I got 92 solutions. Is that correct? The heart of it is in doqueens().

====< queens.py >===========================================
""" bitmap of board
00 01 02 03 04 05 06 07
08 09 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63
"""
threatfrom = {}
queenat = {}
for row in xrange(:
for col in xrange(:
queenat[row,col] = 1L<<(8*row+col)
threat = 0L
for r in xrange(:
for c in xrange(:
if r==row or c==col or abs(r-row)==abs(c-col):
threat |= 1L<<(8*r+c)
threatfrom[row,col] = threat


def printsol(sol):
for row in range(:
for col in range(: print '+Q'[(sol>>(row*8+col))&1],
print

def solok(sol):
"""check that each queen doesn't threaten the rest"""
threats=0L
for row in range(:
for col in range(:
if (sol>>(row*8+col))&1:
q = 1L<<(row*8+col)
if (sol^q) & threatfrom[row,col]: return False
return True

def doqueens():
solutions = {}
def tryplace(board, threats, row, cols):
for col in cols:
if (board&threatfrom[row,col]) or (queenat[row,col]&threats): continue
if row<7:
xcols = cols[:]
xcols.remove(col)
tryplace(board|queenat[row,col],threats|threatfrom[row,col], row+1, xcols)
else:
board |= queenat[row,col]
solutions[board]=None
tryplace(0L, 0L, 0, range()
return solutions

if __name__ == '__main__':
solutions = doqueens()
loop = ''
for i, sol in enumerate(solutions.keys()):
assert solok(sol) # just for warm fuzzies
if loop in ['', 'a']:
print '\n====[ Solution # %s ]====[ bitmap %X ]====\n'%(i+1, sol)
printsol(sol)
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
================================================== ==========

[14:02] C:\pywk\clp>queens.py

====[ Solution # 1 ]====[ bitmap 1040080104802002 ]====

+ Q + + + + + +
+ + + + + Q + +
+ + + + + + + Q
+ + Q + + + + +
Q + + + + + + +
+ + + Q + + + +
+ + + + + + Q +
+ + + + Q + + +

Press Enter for another, a for all, q to quit:

etc...

Regards,
Bengt Richter
 
Reply With Quote
 
 
 
 
Grant Edwards
Guest
Posts: n/a
 
      08-14-2003
In article <bhgt48$8su$0@216.39.172.122>, Bengt Richter wrote:

> JFTHOI, I did a version based on 64-bit bitmaps of the board
> and threat patterns from a queen at any given position. I
> forgot about generators, sorry I bute forced the threatfrom
> and queenat setup for transparency.
>
> I got 92 solutions. Is that correct? The heart of it is in doqueens().


Yup. That's right according to my program:

ftp://ftp.visi.com/users/grante/python/queens.py

The search is slowed way down so it can be animated. I just
ran a quick hacked version w/o delays and it found 92
solutions. My program is probably bit wordy and not very
idiomatic since it's a direct translation of a Scheme program.

--
Grant Edwards grante Yow! Don't SANFORIZE me!!
at
visi.com
 
Reply With Quote
 
Bengt Richter
Guest
Posts: n/a
 
      08-14-2003
On 14 Aug 2003 22:41:11 GMT, http://www.velocityreviews.com/forums/(E-Mail Removed) (Grant Edwards) wrote:

>In article <bhgt48$8su$0@216.39.172.122>, Bengt Richter wrote:
>
>> JFTHOI, I did a version based on 64-bit bitmaps of the board
>> and threat patterns from a queen at any given position. I
>> forgot about generators, sorry I bute forced the threatfrom
>> and queenat setup for transparency.
>>
>> I got 92 solutions. Is that correct? The heart of it is in doqueens().

>
>Yup. That's right according to my program:
>
>ftp://ftp.visi.com/users/grante/python/queens.py
>
>The search is slowed way down so it can be animated. I just
>ran a quick hacked version w/o delays and it found 92
>solutions. My program is probably bit wordy and not very
>idiomatic since it's a direct translation of a Scheme program.
>

I just made mine up from what I thought the problem definition was, so I thought it might
be interesting to post.

But yours has nice visual animation.

BTW, my version got all 92 solutions in < 155ms on a 300mhz P2 without attempting to optimize
(just the call to doqueens that is, not including import time).

Regards,
Bengt Richter
 
Reply With Quote
 
Terry Reedy
Guest
Posts: n/a
 
      08-14-2003

"Grant Edwards" <(E-Mail Removed)> wrote in message
news:3f3c1007$0$177$(E-Mail Removed).. .
> > I got 92 solutions. Is that correct? The heart of it is in

doqueens().
>
> Yup. That's right according to my program:
>
> ftp://ftp.visi.com/users/grante/python/queens.py


For another comparison, Python22+/Lib/test/test_generators.py has
generator-based N-queens (and Knight's-tour) programs.

TJR


 
Reply With Quote
 
Grant Edwards
Guest
Posts: n/a
 
      08-15-2003
In article <bhh6hg$pmk$0@216.39.172.122>, Bengt Richter wrote:

>>> I got 92 solutions. Is that correct? The heart of it is in doqueens().

>>
>>Yup. That's right according to my program:
>>
>>ftp://ftp.visi.com/users/grante/python/queens.py
>>
>>The search is slowed way down so it can be animated. I just ran a quick
>>hacked version w/o delays and it found 92 solutions. My program is probably
>>bit wordy and not very idiomatic since it's a direct translation of a Scheme
>>program.

>
> I just made mine up from what I thought the problem definition was, so I
> thought it might be interesting to post.
>
> But yours has nice visual animation.


Mine was originally an exercise to figure out how Tk worked.

> BTW, my version got all 92 solutions in < 155ms on a 300mhz P2 without
> attempting to optimize (just the call to doqueens that is, not including
> import time).


Someday I want to modify it to keep a list of solutions and eliminating all
the ones that are mirror images or rotations. But, it's been 6 or 7 years
since I wrote the original program, so I wouldn't hold my breath.

--
Grant Edwards grante Yow! I just forgot my
at whole philosophy of life!!!
visi.com
 
Reply With Quote
 
Bengt Richter
Guest
Posts: n/a
 
      08-15-2003
On 14 Aug 2003 20:57:44 GMT, (E-Mail Removed) (Bengt Richter) wrote:
[...]
>
>JFTHOI, I did a version based on 64-bit bitmaps of the board and
>threat patterns from a queen at any given position. I forgot about generators, sorry


Oops, sorry. Some cruft and a redundant test removed. Time reduced by ~135/155.
Not worth going to diff...

====< queens.py >===========================================
""" bitmap of board
00 01 02 03 04 05 06 07
08 09 10 11 12 13 14 15
16 17 18 19 20 21 22 23
24 25 26 27 28 29 30 31
32 33 34 35 36 37 38 39
40 41 42 43 44 45 46 47
48 49 50 51 52 53 54 55
56 57 58 59 60 61 62 63
"""
threatfrom = {}
queenat = {}
for row in xrange(:
for col in xrange(:
queenat[row,col] = 1L<<(8*row+col)
threat = 0L
for r in xrange(:
for c in xrange(:
if r==row or c==col or abs(r-row)==abs(c-col):
threat |= 1L<<(8*r+c)
threatfrom[row,col] = threat


def printsol(sol):
for row in range(:
for col in range(: print '+Q'[(sol>>(row*8+col))&1],
print

def solok(sol):
"""check that each queen doesn't threaten the rest"""
for row in range(:
for col in range(:
if (sol>>(row*8+col))&1:
q = 1L<<(row*8+col)
if (sol^q) & threatfrom[row,col]: return False
return True

def doqueens():
solutions = {}
def tryplace(board, threats, row, cols):
for col in cols:
if (board&threatfrom[row,col]): continue
qboard = board|queenat[row,col]
if row<7:
xcols = cols[:]
xcols.remove(col)
tryplace(qboard, threats|threatfrom[row,col], row+1, xcols)
else:
solutions[qboard]=None
tryplace(0L, 0L, 0, range()
return solutions

if __name__ == '__main__':
solutions = doqueens()
loop = ''
for i, sol in enumerate(solutions.keys()):
assert solok(sol) # just for warm fuzzies
if loop in ['', 'a']:
print '\n====[ Solution # %s ]====[ bitmap %X ]====\n'%(i+1, sol)
printsol(sol)
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
================================================== ==========

Regards,
Bengt Richter
 
Reply With Quote
 
Bengt Richter
Guest
Posts: n/a
 
      08-15-2003
On 15 Aug 2003 01:50:00 GMT, (E-Mail Removed) (Bengt Richter) wrote:

>On 14 Aug 2003 20:57:44 GMT, (E-Mail Removed) (Bengt Richter) wrote:
>[...]
>>
>>JFTHOI, I did a version based on 64-bit bitmaps of the board and
>>threat patterns from a queen at any given position. I forgot about generators, sorry

>
>Oops, sorry. Some cruft and a redundant test removed. Time reduced by ~135/155.
>Not worth going to diff...
>

argh ... down another 10ms to ~125
====< queens.py >===========================================
[...]
def doqueens():
solutions = {}
def tryplace(board, row, cols):
for col in cols:
if (board&threatfrom[row,col]): continue
qboard = board|queenat[row,col]
if row<7:
xcols = cols[:]
xcols.remove(col)
tryplace(qboard, row+1, xcols)
else:
solutions[qboard]=None
tryplace(0L, 0, range()
return solutions
[...]
================================================== ==========

Regards,
Bengt Richter
 
Reply With Quote
 
Anton Vredegoor
Guest
Posts: n/a
 
      08-16-2003
(E-Mail Removed) (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()




 
Reply With Quote
 
Bengt Richter
Guest
Posts: n/a
 
      08-17-2003
On Sat, 16 Aug 2003 12:12:47 +0200, (E-Mail Removed) (Anton Vredegoor) wrote:

>(E-Mail Removed) (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=:
"""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=:
"""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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Lie Hetland book: Beginning Python.. Vittorio Python 8 11-11-2005 05:15 PM
The eight queens problem jblazi C++ 9 08-30-2004 05:01 PM
"Eight Queens" program Matt C Programming 5 08-21-2004 04:14 AM
Is this OT(was:Re: "Eight Queens" program) sathya_me C Programming 5 08-20-2004 03:57 PM
Eight queens using stacks instead of recursion cfanatic C++ 3 10-16-2003 06:47 PM



Advertisments