Author: Ricardo Gibert
Date: 22:04:52 01/17/03
Go up one level in this thread
On January 17, 2003 at 23:58:25, Russell Reagan wrote: >If you were writing a program to solve the 8-queens problem, and your goal was >speed, would you use "normal" computer chess techniques (like, say, 0x88 or >bitboards) or would you do something more specific? > >For instance, rather than detecting attacks via traditional 0x88 or bitboard >methods, you could keep track of which ranks and files are already occupied (and >thus are not candidates for further occupation), and then you could quickly rule >out large chunks of the board that are not available for a queen. This would >seem to be much faster than doing a typical "full blown" attack detection. > >You could also use a simple pseudo-attack array (easy to create for 0x88 or >bitboards) and cut out the extra code to determine if a pseudo-attack is a real >attack, since in this problem, a pseudo-attack means two queens are attacking >each other somewhere. > >I am interested in two things. First, I would be interested in knowing how >people would approach this problem (and other "chess-like" problems) where >traditional computer chess methods will work, but might not necessarily be as >fast as other methods. Second, I would be interested in knowing of other chess >problems that are not "game" problems (IE something a typical chess engine can't >solve, like the 8-queens problem or a knight's tour problem). The knight's tour >problem seems like another one that fits into this category. > >For those who may not know what the 8 queens problem is, it involves finding >positions using only 8 queens where no queen attacks another queen. You can only >use queens. So adding pawns to block a queen attack, for example, is not >allowed. The way I remember solving (a very long time ago) the "8 queens problem" was by first solving the "8 rooks problem." The latter problem is trivial. It is equivalent to just permuting 8 objects to produce all the solutions. Now the idea was to test whether an 8 rook solution was also an 8 queen solution. I created an array of 30 (26?) flags where each flag represented whether a particular diagonal was occupied or not. Now as I generated the 8 rook solutions, I would test if a diagonal was already occupied. If yes, I would back track to generate the next candidate. I also remeber doing an optimization that avoided candidate solutions where the piece was diagonally adjacent. So I was only generating a subset of 8 rook solutions to see if they were also 8 queen solutions. I don't remember what board represention I used. Probably because there was no board explicitly represented.
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.