Author: Dann Corbit
Date: 23:50:19 01/17/03
Go up one level in this thread
#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) {
try {
board = new int [queen_count];
}
catch (...)
{
cout << "Exception thrown. Problem size too big?" << endl;
cout << "Try a smaller problem." << endl;
throw; // Crash and burn, baby.
}
this->queen_count = queen_count;
}
//--------------------------------------------------------
// Only a complete and utter moron would forget the
// destructor in a program that uses new[]
//--------------------------------------------------------
~n_queens() {
delete []board;
}
//--------------------------------------------------------
// 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.