[Matthew Singletary] >> I'm building a genetic algorithm to solve the queen placement problem, >> the complicated stuff I can do on my own, but I'm not getting one >> part. >> suppose the queen is on a square, I can check that it is in the same >> row or same col but the diagonals, are less straight-forward. >> I know I could solve this by just smashing away at it, but I was >> wondering if anyone could suggest some tips on directions to work >> >> I'm NOT looking for any answers, just some tips to an _elegant_ method >> to solve this.
[Lloyd Kvam] > This problem is discussed in "The ICON Programming Language" by Ralph > and Madge Griswold around page 150. The basic approach they take is to > number diagonals, just like you number rows and columns. So every > queen's position involves a row #, col #, and diag #. > > Scratching your head over how to number the diagonals I'll leave to you. > They counted 30 diagonals, so if you come up with a different count, you > either have an original approach or have blundered somewhere. > > (Hopefully that was the kind of pointer you were looking for. Tim > Peters (I think) has written about this problem in a Python context, but > citing Icon.) There's a short and sweet Queens solver in Python's test_generators.py, part of Python's standard test suite. The comments explain one way to uniquely number the diagonals in the general (NxN board) case, as linear functions of the row and column indices. It's easy but tedious :-) _______________________________________________ Tutor maillist - Tutor@python.org http://mail.python.org/mailman/listinfo/tutor
