Author: Frank Schneider
Date: 22:36:40 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. Hi, constraint programming is probably the method of choice to solve this (and similar) problems. A great (but quite scientific) book is online here: http://cswww.essex.ac.uk/CSP/papers/Tsang-Fcs1993.pdf/ Frank
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.