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