[Tutor] checking diagonals on a chessboard
dyoo at hkn.eecs.berkeley.edu
Thu Apr 13 22:07:29 CEST 2006
> 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
This is sensitive to the way that you're encoding the position of a queen.
If you're using chess's algebraic notation, like "e2" or "f7", although
it's familiar, this may not be be the most convenient representation for
doing positional calculations.
A slightly more convenient representation may be as cartesian coordinates.
i.e.: "e2" <==> (5, 2)
"f7" <==> (6, 7)
That is, treat the chessboard as if it were a piece of graph paper. The
reason that this particular encoding of position as 2-tuples is nice is
this: like the algebraic notation, it's easy to check rows and columns for
similarity. But furthermore, given two positions, it isn't too bad to see
if those positions lie on the same diagonal.
(Think back to algebra and slopes.)
So our choice of how we represent knowledge can matter. Math would suck
if we had to stick with Roman numerals.
>From my layman's understanding of genetic algorithms, I remember that an
effective choice in representation is also a big deal in evolving new
solutions, so it's always something to keep in mind. Are you reading
something like Melanie Mitchell's "An Introduction to Genetic Algorithms"?
This is an area I'd like to know more about too, so if you have any book
pointers, I'll put them on my wishlist. *grin*
Best of wishes to you!
More information about the Tutor