8 Queens Problem

Simon.Foster at smiths-aerospace.com Simon.Foster at smiths-aerospace.com
Tue Jul 9 09:10:28 EDT 2002


Just For Fun!

I've been working on a solution to the eigth queens puzzle.
Here is my attempt.  There's a solution in Scheme in SICP
which takes only 13 lines.  Can anyone come up with a shorter
solution in Python, without any of the obvious silliness?

Having to do the list copies:

                r = rows[:]
                s = solution[:]

seems like a bit of a waste, does anyone see a solution that 
doesn't involve lots of copying?

Seems to me that functional languages have the edge for this sort
of problem.  Anyone have anny comments.

SICP = "Structure and Interpretation of Computer Programs"
     by Abelson, Sussman and Sussman

PS.     For the functional gurus out there:
    Would this solution qualify as tail-recursive?

PPS.    What's a closure?  A continuation?

----


import sys

def queens( order, rows, solution ):
    if order:
        for x in rows:
            y = order - 1
            for i, j in solution:
                if x - y == i - j: break
                if x + y == i + j: break
            else:
                r = rows[:]
                s = solution[:]
                r.remove( x )
                s.append(( x, y ))
                queens( y, r, s )
    else: print solution

queens( 8, range(8), [] )





More information about the Python-list mailing list