Eight Queens Puzzle by Magnus Lie Hetland

[Bengt Richter]

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 ;-)

====< 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"""
    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