File: Location.h
File: Queen.cpp
File: Board.cpp
File: main.cpp
#ifndef nQueen_Location_h
#define nQueen_Location_h
const int UNDEFINED = -1;
class Location {
private:
int row;
int col;
public:
Location();
Location( int row, int col );
void setLocation( int row, int col );
void setLocation( Location* location );
int getRow();
int getCol();
};
#endif
File: Location.cpp
#include "Location.h"
Location::Location(){
row = UNDEFINED;
col = UNDEFINED;
};
Location::Location( int _row, int _col ){
row = _row;
col = _col;
};
void Location::setLocation( int _row, int _col ) {
row = _row;
col = _col;
};
void Location::setLocation( Location* location ) {
row = location->getRow();
col = location->getCol();
};
int Location::getCol() {
return col;
};
int Location::getRow(){
return row;
};
File: Queen.h
#ifndef nQueen_Queen_h
#define nQueen_Queen_h
#include "Location.h"
#include <stdlib.h>
class Queen {
private:
Location* location;
public:
Queen();
Queen( int row, int col );
bool canAttack( int row, int col );
int getRow();
int getCol();
Location* getLocation();
void setLocation(int row, int col);
void resetLocation();
~Queen();
};
#endif
File: Queen.cpp
#include "Queen.h"
Queen::Queen() {
Queen( UNDEFINED, UNDEFINED );
};
Queen::Queen( int row, int col ){
location = new Location( row, col );
};
bool Queen::canAttack( int row, int col ){
int myRow = getRow();
int myCol = getCol();
if ( myCol == UNDEFINED || myRow == UNDEFINED ) {
return false;
}
if ( myRow == row || myCol == col ) {
return true;
}
/* Compute the all 4 diagonal */
int rowDiff = abs ( row - myRow );
int colDiff = abs ( col - myCol );
if ( rowDiff == colDiff ) {
return true;
}
return false;
};
Location* Queen::getLocation() {
return location;
};
void Queen::setLocation( int _row, int _col ){
if ( location == nullptr ) {
location = new Location( _row, _col);
return;
}
location->setLocation(_row, _col );
};
void Queen::resetLocation() {
setLocation(UNDEFINED, UNDEFINED);
}
int Queen::getRow() {
return location->getRow();
}
int Queen::getCol() {
return location->getCol();
}
Queen::~Queen(){
delete location;
}
File: Board.h
#ifndef nQueen_Board_h
#define nQueen_Board_h
#include "Queen.h"
class Board{
private:
Queen* queens;
int boardSize;
int numOfSoln;
bool _solve( int row, Queen* queen );
bool isCellSafe( int row, int col );
public:
Board( int boardSize);
void print();
void solve();
};
#endif
File: Board.cpp
#include "Board.h"
#include<iostream>
using namespace std;
bool Board::_solve( int row, Queen* queen ){
if ( row == boardSize ) {
print();
return true;
}
Queen* subQueen = queen;
for ( int col = 0; col < boardSize; col ++ ) {
if ( isCellSafe(row, col ) ) {
subQueen->setLocation( row, col );
_solve(row + 1, subQueen + 1 );
subQueen->resetLocation();
}
}
return false;
};
bool Board::isCellSafe( int row, int col ) {
Queen* tmpQueen = queens;
for ( int i = 0 ; i < boardSize; i ++ ) {
if ( tmpQueen->canAttack( row, col ) ) {
return false;
}
tmpQueen++;
}
return true;
};
Board::Board( int _boardSize) {
boardSize = _boardSize;
queens = new Queen[boardSize];
for( int i = 0 ; i < boardSize; i++ ) {
Queen* tmpQueen = new Queen( UNDEFINED, UNDEFINED );
queens[i] = *tmpQueen;
}
};
void Board::print(){
Queen* rowQueen = queens;
numOfSoln++;
cout << "Printing solution: " << numOfSoln << "\n";
for( int rownum = 0 ; rownum < boardSize; rownum++ ) {
cout << rownum << ", " << rowQueen->getCol() << endl;
rowQueen++;
}
};
void Board::solve() {
if ( _solve(0, queens ) ){
print();
return;
}
if ( numOfSoln == 0 ) {
cout << "Could not find a solution" << endl;
}
};
File: main.cpp
#include<iostream>
#include "Board.h"
int main(int argc, const char * argv[]) {
if ( argc != 2 ) {
fprintf(stderr, "Please provide board size.");
return 1;
}
int size = atoi( argv[1]);
Board* board = new Board( size);
board->solve();
delete board;
return 0;
}
If something is not write please let me know.
