Eight Queens Puzzle by Magnus Lie Hetland
Bengt Richter
bokr at oz.net
Fri Aug 15 23:46:54 EDT 2003
On 15 Aug 2003 20:32:05 GMT, bokr at oz.net (Bengt Richter) wrote:
>On Fri, 15 Aug 2003 13:13:43 +0200, Borcis <borcis at 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
More information about the Python-list
mailing list