8 Queens Problem
Duncan Booth
duncan at NOSPAMrcp.co.uk
Tue Jul 9 11:54:27 EDT 2002
Simon.Foster at smiths-aerospace.com wrote in
news:mailman.1026221774.20130.python-list at python.org:
> 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?
Here are a couple of solutions based on your version but using generators.
This has the advantage of giving you all the solutions for possible further
processing, instead of just printing them out, and also allows you to avoid
calculating all solutions if you just want one:
from __future__ import generators
def queens1(order, rows, solution=[], diaga=[], diagb=[]):
"""Generates all solutions based on the partial solution so far.
Output: (solution, diaga, diagb)"""
if order==0:
yield solution, diaga, diagb
return
y = order-1
for x in rows:
if x-y not in diaga and x+y not in diagb:
r = rows[:]
r.remove(x)
for s, d1, d2 in queens1(y, r, solution+[(x,y)],
diaga+[x-y], diagb+[x+y]):
yield s, d1, d2
for s,d1,d2 in queens1(8, range(8)):
print s
break
print "Total solutions",len(list(queens1(8, range(8))))
# A version that doesn't precompute the diagonals
from operator import add, sub
def queens2(order, rows, solution=[]):
"""Generates all solutions based on the partial solution so far.
Yields each solution"""
if order==0:
yield solution
return
y, diaga, diagb = order-1, [], []
if solution:
s = zip(*solution)
diaga, diagb = map(sub, *s), map(add, *s)
for x in rows:
if x-y not in diaga and x+y not in diagb:
r = rows[:]
r.remove(x)
for s in queens2(y, r, solution+[(x,y)]):
yield s
for s in queens2(8, range(8)):
print s
break
print "Total solutions",len(list(queens2(8, range(8))))
--
Duncan Booth duncan at rcp.co.uk
int month(char *p){return(124864/((p[0]+p[1]-p[2]&0x1f)+1)%12)["\5\x8\3"
"\6\7\xb\1\x9\xa\2\0\4"];} // Who said my code was obscure?
More information about the Python-list
mailing list