Author: Bas Hamstra
Date: 04:42:12 01/18/03
Go up one level in this thread
Hi Russell,
Reminds me of the assembly NQueens.com program that I once wrote. You start it
with Queens n, where n is the number of queens on a nxn board. The comfile is
687 bytes, which includes 18 bytes for the error message "Usage: NQueens n". For
14 queens it outputs:
"QUEENS=14 Solutions=365596"
In a few seconds. If I am not mistaken it doesn't even use a board, but just
computes the number of queens per "ray". Have to look it up, it is a while ago.
In fact it was not straight asm, but a C-- variant (contra C++) which is halfway
between C and asm (Sphinx C-- compiler). It was fun, we did contests back then,
to see who could solve it fastest. We also did travelling salesman problems with
impossible numbers of cities, every day new distance records were posted...
Brute force didn't work anymore, so heuristics, like genetic algo's etc. I think
an approach where the "route" was encoded as an array, and you randomly swapped
random portions of the route was a simple and very effective approach. If length
increased more than a certain margin, you swap it back. The margin prevents more
or less getting stuck in a local optima. Optimum solution not guarantueed of
course, but you get nearly optimal solutions extremely fast. Sorry if I drifted
away from your question a bit :-)
Bas.
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.
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.