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