Bragging about Python (8 queens)

[Steve Howell]

--- Paul McGuire <ptmcg at austin.rr.com> wrote:
> >
> > So I'm throwing down the gauntlet--can somebody
> write
> > a short program (maybe 10 to 20 lines) where you
> solve
> > a problem more simply than a similar
> > non-generator-using solution would solve it? 
> Maybe
> > something like Eight Queens?
> >
> 
> Well, I misread your "gauntlet throwing", and
> implemented a brief 8-
> queens using recursion and exceptions.  Perhaps this
> could serve as
> the "before" to an "after" using generators. (I note
> that neither
> recursion nor exceptions are covered in your
> examples.)  

Actually, there was a minor example with exceptions,
but agreed re:recursion, and this is just such a
classic problem, it belongs on the page.

> Also, in
> googling about for other 8-queens solutions in
> Python, most are quite
> complicated - this one uses only 24 lines, and works
> for boards of any
> size.  I also think this line for printing out the
> board:
> 
> print "\n".join( "."*q+"Q"+"."*(BOARD_SIZE-q-1) for
> q in queens )
> 
> illustrates a couple of interesting idioms of Python
> (joining a list,
> generator expression, "."*repetition to give
> "....").

Agreed.

> 
> Worthy of your page?
> 

Definitely worthy.  Go ahead and add it.  

FWIW I have been labelling programs by the number of
lines of code.  So this is program #24, which now
creates a gap between #16 and #23.  

Also, I humbly suggest test_queens instead of
testQueens.  I don't want to reopen the PEP 8 debate,
just a recommendation.  I think PEP 8 would also
suggest some white space around '+' and '=='.

> 
> BOARD_SIZE = 8
> def validate(queens):
>     left = right = col = queens[-1]
>     for r in reversed(queens[:-1]):
>         left,right = left-1,right+1
>         if r in (left, col, right):
>             raise Exception
> 
> def add_queen(queens):
>     for i in range(BOARD_SIZE):
>         testQueens = queens+[i]
>         try:
>             validate(testQueens)
>             if len(testQueens)==BOARD_SIZE:
>                 return testQueens
>             else:
>                 return add_queen(testQueens)
>         except:
>             pass
>     raise Exception
> 
> queens = add_queen([])
> print queens
> print "\n".join( "."*q+"Q"+"."*(BOARD_SIZE-q-1) for
> q in queens )
> 

Very Pythonic solution IMHO.  Nicely done.




       
____________________________________________________________________________________
Looking for a deal? Find great prices on flights and hotels with Yahoo! FareChase.
http://farechase.yahoo.com/