Author: Ricardo Gibert
Date: 03:54:25 01/18/03
Go up one level in this thread
On January 18, 2003 at 06:31:24, Dan Andersson wrote: >Correct, you are enumerating a sparse binary vector. That can be made pretty >efficient. Wonder what the minimal generator is. But is it faster than using the >backtracing algorithm? It certainly takes more space. So it might be trading >space for speed, but I doubt that. The backtracking algorithm and the >Rook-to-Queen sieve are pretty equal in design. You still "backtrack". The 8 rook solution generator constructs each solution one rook at a time. You stop at mid construction of a candidate solution (with the suitable modification) if the solution is invalid for the 8 queens problem and backtrack to construct the next candidate. Maybe I'm mixed up though. I did this about 20 years ago in pascal. Maybe I should take another swing at this for old times sake? The only difference is that >instead of generating an additional #RemainingQueens! number of boards and then >skipping them in O(1) or worse. You simply don't generate them at all in the >backtracker. For large boards this will kill your sieve algorithm. > >MvH Dan Andersson
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.