Re: Eight Queens Puzzle by Magnus Lie Hetland

Discussion in 'Python' started by Jeff Epler, Aug 13, 2003.

  1. Jeff Epler

    Jeff Epler Guest

    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), 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
     
    Jeff Epler, Aug 13, 2003
    #1
    1. Advertising

  2. On Wed, 13 Aug 2003 09:50:38 -0500, Jeff Epler <> 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), 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(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
     
    Bengt Richter, Aug 14, 2003
    #2
    1. Advertising

  3. 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
     
    Grant Edwards, Aug 14, 2003
    #3
  4. On 14 Aug 2003 22:41:11 GMT, (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
     
    Bengt Richter, Aug 15, 2003
    #4
  5. Jeff Epler

    Terry Reedy Guest

    "Grant Edwards" <> wrote in message
    news:3f3c1007$0$177$...
    > > 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
     
    Terry Reedy, Aug 15, 2003
    #5
  6. 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
     
    Grant Edwards, Aug 15, 2003
    #6
  7. On 14 Aug 2003 20:57:44 GMT, (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(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, 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, Aug 15, 2003
    #7
  8. On 15 Aug 2003 01:50:00 GMT, (Bengt Richter) wrote:

    >On 14 Aug 2003 20:57:44 GMT, (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
     
    Bengt Richter, Aug 15, 2003
    #8
  9. (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[j] = 1
    def hm(mat):
    #horizontal mirror image
    m = mat[:]
    for i in range(sz/2): m,m[sz-i-1]=m[sz-i-1],m
    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()
     
    Anton Vredegoor, Aug 16, 2003
    #9
  10. On Sat, 16 Aug 2003 12:12:47 +0200, (Anton Vredegoor) wrote:

    > (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
     
    Bengt Richter, Aug 17, 2003
    #10
  11. (Bengt Richter) wrote:

    >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 = 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-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()
     
    Anton Vredegoor, Aug 20, 2003
    #11
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. cfanatic
    Replies:
    3
    Views:
    581
    cfanatic
    Oct 16, 2003
  2. jblazi

    The eight queens problem

    jblazi, Aug 30, 2004, in forum: C++
    Replies:
    9
    Views:
    2,588
    Karl Heinz Buchegger
    Aug 30, 2004
  3. Vittorio
    Replies:
    8
    Views:
    523
    Scott David Daniels
    Nov 11, 2005
  4. Matt

    "Eight Queens" program

    Matt, Aug 18, 2004, in forum: C Programming
    Replies:
    5
    Views:
    473
    -berlin.de
    Aug 21, 2004
  5. sathya_me

    Is this OT(was:Re: "Eight Queens" program)

    sathya_me, Aug 20, 2004, in forum: C Programming
    Replies:
    5
    Views:
    318
    sathya_me
    Aug 20, 2004
Loading...

Share This Page