[Tutor] checking diagonals on a chessboard

Danny Yoo 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

Hi Matt,

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 mailing list