Author: Dann Corbit
Date: 22:36:58 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.
#include <iostream>
#include <cstdlib>
using namespace std; // yes, I really am that lazy.
//############################################################
// This has been adapted from a C program I found on the net
// some time ago. Original author unknown. -- d. corbit
//############################################################
//============================================================
// The class n_queens is used to solve the n-queens problem.
// Given an NxN board and N queens, place them in such a way
// that none of them attack any of the others.
//============================================================
class n_queens {
private:
//--------------------------------------------------------
// Store queens by row.
// We only need to store the column where we put the queen
int *board;
//--------------------------------------------------------
// queen_count is the size of the problem.
// We assume a square board and one queen for each row.
size_t queen_count;
//--------------------------------------------------------
// Method to find a safe queen location.
// Might be a faster way, but we avoid divide and % here.
//--------------------------------------------------------
bool find_safe_queen_location(int n, int j) {
for (int k = 0; k < n; k++) {
if (board[k] == j)
return false;
if (n - k == board[k] - j)
return false;
if (n - k == j - board[k])
return false;
}
return true;
}
//--------------------------------------------------------
// Method to display a solution
//--------------------------------------------------------
void show_queens() {
cout << endl;
for (int i = 0; i < queen_count; i++) {
for (int j = 0; j < queen_count; j++)
if (j != board[i])
cout << '#';
else
cout << 'q';
cout << endl;
}
cout << endl;
}
//--------------------------------------------------------
// Method to store a solution
//--------------------------------------------------------
int put_queen_on_board(int n) {
// All done? Display the chess board.
if (n == queen_count) {
show_queens();
return 1;
} else {
// Find the next solution
int solution_count = 0;
for (int j = 0; j < queen_count; j++)
if (find_safe_queen_location(n, j)) {
board[n] = j;
// recurse...
solution_count += put_queen_on_board(n + 1);
}
return solution_count;
}
}
public:
//--------------------------------------------------------
// Constructor defaults to 8 queens.
//--------------------------------------------------------
n_queens(size_t queen_count = 8) {
board = new int [queen_count];
this->queen_count = queen_count;
}
//--------------------------------------------------------
// The public method to solve the puzzle.
//--------------------------------------------------------
void solve(void) {
cout << endl << "The " << queen_count << " queens problem.";
cout << put_queen_on_board(0) << " solutions." << endl;
}
};
int main(void)
{
n_queens N_8(8);
N_8.solve();
n_queens N_5(5);
N_5.solve();
return 0;
}
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.