JustBoo wrote:
On 28 Jan 2006 02:47:31 -0800, "wh*************@gmail.com"
<wh*************@gmail.com> wrote:Actually the program is running till 19 steps. Then it backtracks till
the 16th step. And then is stuck forever.
So i dont know how to go about storing the moves in a an array, so that
the backtrack function can start its next search from that particualr
move.
Would the Command Pattern or the Memento Pattern be of use in this
case? They are in the Design Patterns book.
Sounds interesting. I read a lot about patterns in this group, but I have
never gotten into any of those books that everybody else seems to absorb at
amazing speed. Programming is just a past time activity to me, so the
amount of reading I spend on it is limited.
Anyway, this sounds like an interesting test case since the complexity is
not to high although the problem is non-trivial. Since the knights tour
sound like a homework problem, let's consider the problem of placing 8
queens on the chess board so that they do not threaten one another.
Here is the straight forward solution just using recursion to extend a
partial solution. I would love to see a pattern oriented approach for
comparison.
#include <iostream>
#include <stdexcept>
template < unsigned BoardSize >
struct Board {
typedef std::pair< unsigned, unsigned > Field;
static
bool are_threatening ( Field const a, Field const & b ) {
if ( a.first == b.first ) { return ( true ); }
if ( a.second == b.second ) { return ( true ); }
if ( a.second - b.second == a.first - b.first ) { return ( true ); }
if ( a.second - b.second == b.first - a.first ) { return ( true ); }
return ( false );
}
private:
bool data [BoardSize][BoardSize];
unsigned num;
static
void throw_if_invalid( Field const & f ) {
if ( ! ( f.first < BoardSize && f.second < BoardSize ) ) {
throw ( std::out_of_range( "invalid field" ) );
}
}
bool const & at ( Field const & f ) const {
throw_if_invalid( f );
return ( this->data[f.first][f.second] );
}
bool & at ( Field const & f ) {
throw_if_invalid( f );
return ( this->data[f.first][f.second] );
}
public:
Board ( void )
: data ()
, num ( 0 )
{}
void put_queen ( Field const & f ) {
if ( ! this->at(f) ) {
this->at(f) = true;
++ this->num;
}
}
bool has_queen ( Field const & f ) const {
return( this->at(f) );
}
unsigned num_queens ( void ) const {
return ( this->num );
}
unsigned size ( void ) const {
return( BoardSize );
}
void print ( void ) const {
for ( unsigned row = 0; row < BoardSize; ++row ) {
for ( unsigned col = 0; col <BoardSize; ++col ) {
if ( this->has_queen( Field( row, col ) ) ) {
std::cout << row << " " << col << "\n";
}
}
}
}
bool is_threatened ( Field const & f ) const {
for ( unsigned row = 0; row < BoardSize; ++row ) {
for ( unsigned col = 0; col <BoardSize; ++col ) {
Field g ( row, col );
if ( has_queen( g ) && are_threatening( f, g ) ) {
return ( true );
}
}
}
return ( false );
}
private:
static
void extend_partial_solution ( Board const & configuration ) {
if ( configuration.num_queens() == configuration.size() ) {
throw ( configuration );
}
for ( unsigned row = 0; row < configuration.size(); ++row ) {
for ( unsigned col = 0; col < configuration.size(); ++col ) {
Field f ( row, col );
if ( ! configuration.is_threatened( f ) ) {
Board new_conf ( configuration );
new_conf.put_queen( f );
extend_partial_solution( new_conf );
}
}
}
}
public:
static
Board solve ( void ) {
try {
extend_partial_solution( Board() );
}
catch ( Board b ) {
return ( b );
}
throw ( std::logic_error( "no solution" ) );
}
};
int main ( void ) {
Board<8>::solve().print();
}
Best
Kai-Uwe Bux
