# C++ N queens problem

Discussion in 'OT Technology' started by durondude, Jun 11, 2007.

1. ### durondudeOT Addict

Joined:
May 7, 2001
Messages:
24,058
5
Location:
Earth, The Planet

fastest evar! Kinda cheating and not as fun as brute force method but way faster!

Code:
```#include <iostream>
#include <vector>

using namespace std;

vector <int> addVectors( vector <int> & a , vector <int> & b ){
vector <int> temp;

for( int x = 0 ; x < a.size() ; x ++ )
temp.push_back( a[x] );

for( int x = 0 ; x < b.size() ; x++ )
temp.push_back( b[x] );

return temp;
}

void listPieces( vector <int> pieces ){
for( int x = 0 ; x < pieces.size() ; x ++ ){
cout << "(" << pieces[x] << "," << x << ")" << endl;
}
}

void drawBoard( vector <int> & pieces ){
for( int x = 0 ; x < pieces.size() ; x++ )
cout << " _";

cout << endl;

for( int y = 0 ; y < pieces.size() ; y ++ ){
for( int x = 0 ; x < pieces.size() ; x ++ ){
if( pieces[y]-1 == x ){
cout << "|o";
} else {
cout << "|_";
}
}
cout << "|" << endl;
}
}

int main( void ){
int num, rem;
vector <int> evens;
vector <int> odds;
vector <int> queens;

cout << "N?: ";
cin >> num;

if( ( num == 2 ) || ( num == 3 ) ){
cout << "Sorry, " << num << " won't work, please enter a number that is = 1 or > or = to 4" << endl;
return 0;
}

rem = num % 12;

for( int x = 2 ; x <= num ; x += 2 ){
evens.push_back( x );
}

for( int x = 1 ; x <= num ; x += 2 ){
odds.push_back( x );
}

if( rem == 8 ){//switch pairs
vector <int> temp;

for( int x = 0 ; x < odds.size() ; x += 2 ){
temp.push_back( odds[x+1] );
temp.push_back( odds[x] );
}
odds = temp;
}

if( ( rem == 3 ) || ( rem == 9 ) ){//move 2 to end of list.
evens.erase( evens.begin() );
evens.push_back( 2 );
}

if( rem == 2 ){//switch places of 1 and 5 , move 5 to the end of the list
//switch 1 and 3
odds.erase( odds.begin() );
odds.erase( odds.begin() );

if( num > 4 ){
odds.erase( odds.begin() );
odds.push_back( 5 );
}

odds.insert( odds.begin() , 1 );
odds.insert( odds.begin() , 3 );
}

if( ( rem == 3 ) || ( rem == 9 ) ){
int a = odds[0];
int b = odds[1];

odds.erase( odds.begin() );
odds.erase( odds.begin() );

odds.push_back( a );
odds.push_back( b );
}

queens = addVectors( evens , odds );

drawBoard( queens );
listPieces( queens );

return 0;
}```
I'll post the brute force method also if anyone is interested

2. ### deusexaetheraOT Supporter

Joined:
Jan 27, 2005
Messages:
19,712
0
What the hell are you talking about?

3. ### durondudeOT Addict

Joined:
May 7, 2001
Messages:
24,058
5
Location:
Earth, The Planet
The eight queens puzzle is the problem of putting eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queen's moves. The colour of the queens is meaningless in this puzzle, and any queen is assumed to be able to attack any other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n queens puzzle of placing n queens on an n×n chessboard.

4. ### durondudeOT Addict

Joined:
May 7, 2001
Messages:
24,058
5
Location:
Earth, The Planet
compile it and run it to see what the hell i am talking about

5. ### durondudeOT Addict

Joined:
May 7, 2001
Messages:
24,058
5
Location:
Earth, The Planet
here is the slow method

anyone know how I could speed this up?
Code:
```#include <vector>
#include <iostream>
#include <string>

using namespace std;

class queen;
class row;
class square;

class queen{
public:
queen( int col );
bool shiftRight( int num );
int getCol();

private:
int col;
};

class row{
public:
square & operator[]( const int index );
void resize( const int num );
int size();
bool checkRow();

private:
vector <square> data;
};

class square{
public:
square();
void occupy();
void unOccupy();
bool isOccupied();
private:
bool occupied;
};

queen::queen( int col ){
queen::col = col;
}

bool queen::shiftRight( int num ){
if( col + 1 < num ){
col++;
return true;
} else {
return false;
}
}

int queen::getCol(){
return queen::col;
}

square & row::operator[]( const int index ){
return row::data[ index ];
}

void row::resize( const int num ){
row::data.resize( num );
}

int row::size(){
return row::data.size();
}

bool row::checkRow(){
for( int c = 0 ; c < row::data.size() ; c ++ ){
if( row::data[c].isOccupied() ) return false;
}

return true;
}

square::square()
{
square::occupied = false;
}

void square::occupy(){
square::occupied = true;
}

void square::unOccupy(){
square::occupied = false;
}

bool square::isOccupied(){
if( occupied ) return true;
else return false;
}

bool checkSquare( vector <row> & board , int x , int y , int size ){
//cout << "Checking square (" << x << "," << y << ")" << endl;

//check row for queens
//cout << "Checking row - ";
if( board[y].checkRow() ){
//cout << "empty" << endl;
} else {
//cout << "taken" << endl;
//cout << "Failed" << endl;

return false;
}
//cout << "Success" << endl;

//check column for queens
//cout << "Checking column - ";
for( int c = 0 ; c < board.size() ; c ++ ){ //check squares above
if( board[c][x].isOccupied() ){
//cout << "taken" << endl;
//cout << "Failed" << endl;

return false;
} else {
//cout << "empty" << endl;
}
}
//cout << "Success" << endl;

//check diagonals (the fun part)
int x1 = x;
int y1 = y;
for(;;){ // Check squares behind and above
if( ( x1 < 0 ) || ( y1 < 0 ) ){
break;
}

if( board[y1][x1].isOccupied() ){
return false;
}

x1--;
y1--;
}

x1 = x;
y1 = y;
for(;;){ // Check squares behind and below
if( ( x1 < 0 ) || ( y1 >= board.size() ) ){
break;
}

if( board[y1][x1].isOccupied() ){
return false;
}

x1--;
y1++;
}

x1 = x;
y1 = y;
for(;;){ // Check squares infront and above
if( ( x1 >= board.size() ) || ( y1 < 0 ) ){
break;
}

if( board[y1][x1].isOccupied() ){
return false;
}

x1++;
y1--;
}

x1 = x;
y1 = y;
for(;;){ // Check squares infront and below
if( ( x1 >= board.size() ) || ( y1 >= board.size() ) ){
break;
}

if( board[y1][x1].isOccupied() ){
return false;
}

x1++;
y1++;
}

//if no queens found return true
//cout << "- Square ok!" << endl;
return true;
}

void fillBoard( vector <row> & board , int size ){
board.resize( size );
for( int c = 0 ; c < size ; c ++ ){
board[c].resize( size );
}

for( int c = 0 ; c < board.size() ; c ++ ){
for( int r = 0 ; r < board[ c ].size() ; r ++ ){
board[ c ][ r ].unOccupy();
}
}
}

void drawBoard( vector <row> & board ){
for( int x = 0 ; x < board.size() ; x ++ ){
cout << " _";
}
cout << endl;

for( int y = 0 ; y < board.size() ; y ++ ){
for( int x = 0 ; x < board.size() ; x ++ ){
if( board[y][x].isOccupied() )
cout << "|o";
else
cout << "|_";
}
cout << "|" << endl;
}
}

void listQueens( vector <queen> queens ){
cout << queens.size() << " Queens!" << endl;
for( int x = 0 ; x < queens.size() ; x ++ ){
cout << "(" << queens[x].getCol()+1 << "," << x+1 << ")" << endl;
}
}

void clearRow( vector <row> & board , int row ){
for( int x = 0 ; x < board.size() ; x ++ ){
board[x][row].unOccupy();
}
}

void updateBoard( vector <row> & board , vector <queen> & queens , int num ){
fillBoard( board , num );

for( int y = 0 ; y < queens.size() ; y ++ ){
int x = queens[y].getCol();
board[y][x].occupy();
}
}

int main( void ){
int num;
bool allFound = false;
int crow = 0;
int ccol = 0;
bool nextRow = false;
vector <queen> queens;

cout << "Number of rows?: ";
cin >> num;

vector <row> board;

fillBoard( board , num );

while( allFound == false ){
nextRow = false;

if( ccol >= num ){
//cout << "Backtrack" << endl;
crow-=1;
ccol = queens.back().getCol() + 1;
queens.pop_back();
updateBoard( board , queens , num );
//drawBoard( board );
}

if( ccol < num ){
//cout << "Trying (" << ccol+1 << "," << crow+1 << ") - ";
if( checkSquare( board , ccol , crow , num ) ){
//cout << "Good." << endl;

queen temp( ccol );
queens.push_back( temp );
nextRow = true;
ccol = 0;
crow++;

updateBoard( board , queens , num );
//drawBoard( board );
} else {
//cout << "No good, next" << endl;

ccol++;
}
}

if( crow >= num ){
allFound = true;
break;
}

//cout << "Row: " << crow << ", Col: " << ccol << endl;
updateBoard( board , queens , num );
//drawBoard( board );
}

updateBoard( board , queens , num );
drawBoard( board );
listQueens( queens );

return 0;
}
```

6. ### deusexaetheraOT Supporter

Joined:
Jan 27, 2005
Messages:
19,712
0
Once you actually posted a description, it was immediately clear what you were doing. Thanks.

7. ### Sexual VanillaNew Member

Joined:
May 23, 2005
Messages:
6,305
0
Location:
South Carolina
Knights Tour > Queens

8. ### durondudeOT Addict

Joined:
May 7, 2001
Messages:
24,058
5
Location:
Earth, The Planet

9. ### deusexaetheraOT Supporter

Joined:
Jan 27, 2005
Messages:
19,712
0
Real software > Math games

10. ### Sexual VanillaNew Member

Joined:
May 23, 2005
Messages:
6,305
0
Location:
South Carolina
11. ### durondudeOT Addict

Joined:
May 7, 2001
Messages:
24,058
5
Location:
Earth, The Planet
true, I was helping my cousin with his C++ hw

Joined:
Dec 22, 2000
Messages:
2,630