101 lines
2.9 KiB
C++
101 lines
2.9 KiB
C++
#include <windows.h>
|
|
#include <iostream>
|
|
#include <string>
|
|
|
|
//--------------------------------------------------------------------------------------------------
|
|
using namespace std;
|
|
|
|
//--------------------------------------------------------------------------------------------------
|
|
class point
|
|
{
|
|
public:
|
|
int x, y;
|
|
point(){ x = y = 0; }
|
|
void set( int a, int b ){ x = a; y = b; }
|
|
};
|
|
//--------------------------------------------------------------------------------------------------
|
|
class nQueens
|
|
{
|
|
public:
|
|
void solve( int c )
|
|
{
|
|
_count = c; int len = ( c + 1 ) * ( c + 1 ); _queens = new bool[len]; memset( _queens, 0, len );
|
|
_cl = new bool[c]; memset( _cl, 0, c ); _ln = new bool[c]; memset( _ln, 0, c );
|
|
point pt; pt.set( rand() % c, rand() % c ); putQueens( pt, c ); displayBoard();
|
|
delete [] _queens; delete [] _ln; delete [] _cl;
|
|
}
|
|
|
|
private:
|
|
void displayBoard()
|
|
{
|
|
system( "cls" ); string t = "+---+", q = "| Q |", s = "| |";
|
|
COORD c = { 0, 0 }; HANDLE h = GetStdHandle( STD_OUTPUT_HANDLE );
|
|
for( int y = 0, cy = 0; y < _count; y++ )
|
|
{
|
|
int yy = y * _count;
|
|
for( int x = 0; x < _count; x++ )
|
|
{
|
|
SetConsoleCursorPosition( h, c ); cout << t;
|
|
c.Y++; SetConsoleCursorPosition( h, c );
|
|
if( _queens[x + yy] ) cout << q; else cout << s;
|
|
c.Y++; SetConsoleCursorPosition( h, c );
|
|
cout << t; c.Y = cy; c.X += 4;
|
|
}
|
|
cy += 2; c.X = 0; c.Y = cy;
|
|
}
|
|
}
|
|
|
|
bool checkD( int x, int y, int a, int b )
|
|
{
|
|
if( x < 0 || y < 0 || x >= _count || y >= _count ) return true;
|
|
if( _queens[x + y * _count] ) return false;
|
|
if( checkD( x + a, y + b, a, b ) ) return true;
|
|
return false;
|
|
}
|
|
|
|
bool check( int x, int y )
|
|
{
|
|
if( _ln[y] || _cl[x] ) return false;
|
|
if( !checkD( x, y, -1, -1 ) ) return false;
|
|
if( !checkD( x, y, 1, -1 ) ) return false;
|
|
if( !checkD( x, y, -1, 1 ) ) return false;
|
|
if( !checkD( x, y, 1, 1 ) ) return false;
|
|
return true;
|
|
}
|
|
|
|
bool putQueens( point pt, int cnt )
|
|
{
|
|
int it = _count;
|
|
while( it )
|
|
{
|
|
if( !cnt ) return true;
|
|
if( check( pt.x, pt.y ) )
|
|
{
|
|
_queens[pt.x + pt.y * _count] = _cl[pt.x] = _ln[pt.y] = true;
|
|
point tmp = pt; if( ++tmp.x >= _count ) tmp.x = 0; if( ++tmp.y >= _count ) tmp.y = 0;
|
|
if( putQueens( tmp, cnt - 1 ) ) return true;
|
|
_queens[pt.x + pt.y * _count] = _cl[pt.x] = _ln[pt.y] = false;
|
|
}
|
|
if( ++pt.x >= _count ) pt.x = 0;
|
|
it--;
|
|
}
|
|
return false;
|
|
}
|
|
|
|
int _count;
|
|
bool* _queens, *_ln, *_cl;
|
|
};
|
|
//--------------------------------------------------------------------------------------------------
|
|
int main( int argc, char* argv[] )
|
|
{
|
|
nQueens n; int nq;
|
|
while( true )
|
|
{
|
|
system( "cls" ); cout << "Enter board size bigger than 3 (0 - 3 to QUIT): "; cin >> nq;
|
|
if( nq < 4 ) return 0; n.solve( nq ); cout << endl << endl;
|
|
system( "pause" );
|
|
}
|
|
return 0;
|
|
}
|
|
//--------------------------------------------------------------------------------------------------
|