Eight Queens Puzzle by Magnus Lie Hetland
chansky
of the chapters he discusses how to use a Generator function to solve
the Eight Queens puzzle. The following is part of his codes:
#This function checks if the next Queen would cause any conflict with
the #previous one.
def conflict(state, nextX):
nextY=len(state)
for i in range(nextY):
if abs(state[i]-nextX) in (0,nextY-i):
return 1
return 0
def queens(num,state):
if len(state)==num-1:
for pos in range(num):
if not conflict(state,pos):
yield pos
I've a hard time to understand the following statement:
if abs(state[i]-nextX) in (0,nextY-i):
The author said that this statement will be True if the horizontal
difference b/w the next queen and the previous one under consideration
is euqal to zero or equal to the vertical distance (diagonally), and
false otherwise.
Well, maybe I'm really slow. What does that "vertical distance" really
mean? If someone out there has read his book, can you help me
understand that line of code.
Jeff Epler
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
Michael Surette
> I've been reading Magnus Lie Hetland's book, Practical Python. In one
> of the chapters he discusses how to use a Generator function to solve
> the Eight Queens puzzle. The following is part of his codes:
....
> I've a hard time to understand the following statement:
>
> if abs(state[i]-nextX) in (0,nextY-i):
>
> The author said that this statement will be True if the horizontal
> difference b/w the next queen and the previous one under consideration
> is euqal to zero or equal to the vertical distance (diagonally), and
> false otherwise.
>
> Well, maybe I'm really slow. What does that "vertical distance" really
> mean? If someone out there has read his book, can you help me
> understand that line of code.
I haven't read the book, but I would suspect that the vertical distance is
the difference in the Y values of the two positions, just as the
horizontal distance is the difference in the X values.
hth
Mike
Bengt Richter
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(8):
for col in xrange(8):
queenat[row,col] = 1L<<(8*row+col)
threat = 0L
for r in xrange(8):
for c in xrange(8):
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(8):
for col in range(8): 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(8):
for col in range(8):
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(8))
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
Grant Edwards
> 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
Bengt Richter
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
Terry Reedy
"Grant Edwards" <gra...@visi.com> wrote in message
news:3f3c1007$0$177$a186...@newsreader.visi.com...
> > 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
Grant Edwards
>>> 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
Bengt Richter
[...]
>
>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...
for row in range(8):
for col in range(8):
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(8))
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
Bengt Richter
>On 14 Aug 2003 20:57:44 GMT, bo...@oz.net (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(8))
return solutions
[...]
============================================================
Regards,
Bengt Richter
Borcis
>>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.
This will give you 12 solutions, one of which possesses an internal
2-fold symmetry, so 92 = 11*8 + 1*8/2.
Bengt Richter
This version discovers the 12 unique ones: (not too tested, and probably has some redundancies ;-)
This one does use generators ;-)
====< queens.py >========================================================
for row in range(8):
for col in range(8):
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, 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.append(qboard)
tryplace(0L, 0, range(8))
return solutions
rotates = (
((lambda r,c:(c, 7-r )), 'R+90'), # old->ccw->new
((lambda r,c:(7-c, r )), 'R-90'), # old->cw->new
((lambda r,c:(7-r, 7-c )), 'R+-180'),
)
flips = (
((lambda r,c:(r, 7-c )), 'E-W'),
((lambda r,c:(c, r )), 'NE-SW'),
)
def combo():
for flip in flips: yield flip
for rot in rotates: yield rot
for flip in flips:
for rot in rotates:
label = '%s, %s'%(flip[1],rot[1])
def f(r,c,flip=flip[0], rot=rot[0]): return rot(*flip(r,c))
yield f, label
def transforms(sol):
for fliprot, label in combo():
board =0L
for r in range(8):
for c in range(8):
if sol&queenat[r,c]:
board |= queenat[fliprot(r,c)]
yield board, label
if __name__ == '__main__':
solutions = doqueens()
unique = {}; transformed = {}
iunique=0
for sol in solutions:
if sol in unique or sol in transformed: continue
iunique+=1
unique[sol]=iunique
for tsol, label in transforms(sol):
if tsol in transformed: continue
transformed[tsol] = sol,label
loop = ''
iunique = 0
for iorig, sol in enumerate(solutions):
assert solok(sol) # just for warm fuzzies
if loop in ['', 'a']:
if sol in unique:
iunique+=1
print '\n====[ Unique Solution %s (orig %s/92) ]====[ bitmap %X ]====\n'%(
unique[sol], iorig+1, sol)
printsol(sol)
else:
usol, label = transformed[sol]
print '\n====[ Orig solution %s/92 is unique solution %s transformed %s ]====\n'%(
iorig+1, unique[usol], label)
if loop=='':
loop ='x'
while loop not in ['','a','q','t']:
loop = raw_input('\nPress Enter for another, a for all, t for transform, q to quit: ')
if loop=='t':
print '\n Original solution # %s/92:\n'%(iorig+1)
printsol(sol)
print '\n ... is the following unique solution %s transformed by %s:\n'%(
unique[usol], label)
printsol(usol)
loop = ''
if loop =='q': break
=========================================================================
Regards,
Bengt Richter
Bengt Richter
>On Fri, 15 Aug 2003 13:13:43 +0200, Borcis <bor...@users.ch> wrote:
>
>>Grant Edwards wrote:
>>
>>>>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.
>>
>>This will give you 12 solutions, one of which possesses an internal
>>2-fold symmetry, so 92 = 11*8 + 1*8/2.
>>
>This version discovers the 12 unique ones: (not too tested, and probably has some redundancies ;-)
>This one does use generators ;-)
>
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.
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))
====< queenset.py >========================================================
# board now represented by set of (r,c) tuples
# signifying queen placement with rows and columns
# in range(8) -- i.e., [0..7)
#
# map of board positions:
# 0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7
# 1,0 1,1 1,2 1,3 1,4 1,5 1,6 1,7
# 2,0 2,1 2,2 2,3 2,4 2,5 2,6 2,7
# 3,0 3,1 3,2 3,3 3,4 3,5 3,6 3,7
# 4,0 4,1 4,2 4,3 4,4 4,5 4,6 4,7
# 5,0 5,1 5,2 5,3 5,4 5,5 5,6 5,7
# 6,0 6,1 6,2 6,3 6,4 6,5 6,6 6,7
# 7,0 7,1 7,2 7,3 7,4 7,5 7,6 7,7
#
import sets
class Board(sets.Set):
def excluding(self, q):
ret = self.copy()
ret.discard(q)
return ret
threatfrom = {} # still a dict, now of sets
queenat = {} # also a dict of sets, just to get the & and | operations
for row in xrange(8):
for col in xrange(8):
queenat[row,col] = Board([(row,col)])
threat = Board()
for r in xrange(8):
for c in xrange(8):
if r==row or c==col or abs(r-row)==abs(c-col):
threat.add((r,c))
threatfrom[row,col] = threat
def sollines(sol):
ret = ['+---'*8+'+']
for r in range(8):
ret.append('| %s |' % ' | '.join(['%s'%(' Q'[(r,c) in sol]) for c in range(8)]))
ret.append(ret[0])
return ret
def printsol(sol):
print '\n'.join(sollines(sol)+[''])
def printpair(sola, solb, sep=' '):
for lina, linb in zip(sollines(sola), sollines(solb)): print '%s%s%s'%(lina,sep,linb)
def solok(sol):
"""check that each queen doesn't threaten the rest"""
for row in range(8):
for col in range(8):
q = (row, col)
if q in sol:
if Board(sol).excluding(q) & threatfrom[row,col]: return False
return True
def doqueens():
solutions = [] # list of sorted queen position tuples (overall list not sorted here)
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:
rclist = list(qboard)
rclist.sort()
solutions.append(tuple(rclist))
tryplace(Board(), 0, range(8))
return solutions
rotates = (
((lambda r,c:(c, 7-r )), 'R+90'), # old->ccw->new
((lambda r,c:(7-c, r )), 'R-90'), # old->cw->new
((lambda r,c:(7-r, 7-c )), 'R+-180'),
)
flips = (
((lambda r,c:(r, 7-c )), 'E-W'),
((lambda r,c:(c, r )), 'NE-SW'),
)
def combo():
for flip in flips: yield flip
for rot in rotates: yield rot
for flip in flips:
for rot in rotates:
label = '%s, %s'%(flip[1],rot[1])
def f(r,c,flip=flip[0], rot=rot[0]): return rot(*flip(r,c))
yield f, label
def transforms(sol):
for fliprot, label in combo():
board = Board()
for r in range(8):
for c in range(8):
if (r,c) in sol:
board |= queenat[fliprot(r,c)]
rclist = list(board)
rclist.sort()
yield tuple(rclist), label
if __name__ == '__main__':
solutions = doqueens()
solutions.sort() # for some kind of consistency
unique = {}; transformed = {}
ucount=0
for sol in solutions:
if sol in unique or sol in transformed: continue
ucount+=1
unique[sol]=ucount
for tsol, label in transforms(sol):
if tsol in transformed: continue
transformed[tsol] = sol, label
loop = ''
printmode = '-u'
for i92, sol in enumerate(solutions):
assert solok(sol) # just for warm fuzzies
if printmode=='u' and sol not in unique: continue
if loop in ['']:
while 1:
loop = raw_input('\nEnter => next, a => all, u => unique only (-u off), q to quit: ')
if loop in ('u', '-u'): printmode = loop
if loop in ['','a','q']: break
if loop =='q': break
if sol in unique:
print '\n====[ Unique Solution %s (orig %s/92) ]\n====[ %r ]====\n'%(
unique[sol], i92+1, sol)
printsol(sol)
else:
usol, label = transformed[sol]
print ( '\n Original solution # %s/92'
' <== transform %s of unique solution # %s:\n'%(
(i92+1), label, unique[usol])
)
printpair(sol, usol)
=========================================================================
It has prettier output:
[20:38] C:\pywk\clp>queenset.py
Enter => next, a => all, u => unique only (-u off), q to quit:
====[ Unique Solution 1 (orig 1/92) ]
====[ ((0, 0), (1, 4), (2, 7), (3, 5), (4, 2), (5, 6), (6, 1), (7, 3)) ]====
+---+---+---+---+---+---+---+---+
| Q | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | Q | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | Q |
+---+---+---+---+---+---+---+---+
| | | | | | Q | | |
+---+---+---+---+---+---+---+---+
| | | Q | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | Q | |
+---+---+---+---+---+---+---+---+
| | Q | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | Q | | | | |
+---+---+---+---+---+---+---+---+
Enter => next, a => all, u => unique only (-u off), q to quit:
====[ Unique Solution 2 (orig 2/92) ]
====[ ((0, 0), (1, 5), (2, 7), (3, 2), (4, 6), (5, 3), (6, 1), (7, 4)) ]====
+---+---+---+---+---+---+---+---+
| Q | | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | Q | | |
+---+---+---+---+---+---+---+---+
| | | | | | | | Q |
+---+---+---+---+---+---+---+---+
| | | Q | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | | | Q | |
+---+---+---+---+---+---+---+---+
| | | | Q | | | | |
+---+---+---+---+---+---+---+---+
| | Q | | | | | | |
+---+---+---+---+---+---+---+---+
| | | | | Q | | | |
+---+---+---+---+---+---+---+---+
Enter => next, a => all, u => unique only (-u off), q to quit:
Original solution # 3/92 <== transform NE-SW of unique solution # 2:
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| Q | | | | | | | | | Q | | | | | | | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | | | | | Q | | | | | | | | Q | | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | | Q | | | | | | | | | | | | | Q |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | | | | Q | | | | | | Q | | | | | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | | | | | | Q | | | | | | | | Q | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | Q | | | | | | | | | | | Q | | | | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | | | Q | | | | | | Q | | | | | | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
| | | Q | | | | | | | | | | | Q | | | |
+---+---+---+---+---+---+---+---+ +---+---+---+---+---+---+---+---+
Regards,
Bengt Richter
Anton Vredegoor
>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()
Bengt Richter
>bo...@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
Anton Vredegoor
>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 ;-/ )
There is also something with this puzzle that makes me think of the
"getting a submatrix of all true" thread. A solution there was a
combination of the columns, here a solution is a permutation of
range(len(columns)). Below I'm giving a possible way to solve the
puzzle using this observation, but maybe someone can see a way to
improve it.
Anton
#permqueens.py
from sets import Set
def unique(n):
""" nqueens solver filtered for solutions that
are rotations or reflections """
seen = Set()
for sol in nqueens(n):
if sol not in seen:
m = mirrors(sol)
seen |= Set(m)
yield min(m)
def asqueens(sol):
""" ascii-art representation of a solution """
R,res = range(len(sol)),""
Q,n = zip(R,sol[::-1]),len(sol)
for i in R:
for j in R:
res += '+Q'[(n-j-1,n-i-1) in Q]+ ' '
res += '\n'
return res
def nqueens(n):
""" iterative nqueens solver using permutations """
QC,R = queencovers(n),range(n)
for i in xrange(fac(n)):
p = indexedperm(i,R)
if checksol(p,QC): yield tuple(p)
def mirrors(sol):
""" a list of mirror images of a solution """
def flip(x): return x[::-1]
def transpose(x):
xx = list(x)
for i,j in enumerate(x): xx[j] = i
return tuple(xx)
f,t = flip(sol),transpose(sol)
ft,tf = flip(t),transpose(f)
ftf,tft = flip(tf),transpose(ft)
ftft = flip(tft)
return [sol,f,t,ft,tf,ftf,tft,ftft]
def queencovers(n):
""" a dictionary of the positions that are covered by
queens on all board positions on an nxn board """
board,queens = [divmod(i,n) for i in range(n*n)],{}
for pos in board: queens[pos] = Set(cover(pos,board))
return queens
def fac(n):
""" faculty of n """
return reduce(lambda x,y:x*y,range(2,n+1),1L)
def indexedperm(m,L):
""" permutations of list L by index """
n,res,T = len(L),L[:],L[:]
for i in range(n):
m,d = divmod(m,n-i)
res[i] = T.pop(d)
return res
def checksol(sol,QC):
""" a solution is a permutation of a range, to convert it to
a list of queen positions it is zipped with a range, a
solution is true if no queen threatens the other queens """
n = len(sol)
#first a little optimization, queens cannot be adjacent
for i in range(n-1):
if abs(sol[i]-sol[i+1]) == 1: return False
queens = Set(zip(range(n),sol))
#check if no queen threatens another queen
for queen in queens:
if queens & QC[queen]: return False
return True
def cover((i,j),board):
""" positions that are covered by queen(i,j),
without (i,j) itself """
def keep((x,y)):
if (i,j) == (x,y) : return False
return i==x or j==y or abs(x-i)==abs(y-j)
return filter(keep,board)
def test():
""" test the unique nqueens solver """
n = 8
for i,sol in enumerate(unique(n)):
print i, sol
print asqueens(sol)
if __name__=='__main__':
test()