• Status: Solved
• Priority: Medium
• Security: Public
• Views: 445

# 8 Queens Game Board

>> In this program I had to provide the implementations for is_solved() const, remove(), and print().

**************************Code*******************************

#ifndef QUEENS_H
#define QUEENS_H

const int max_board = 30;

class Queens {

public:

Queens(int size);// done
void print() const;// done
void solve_from(Queens &configuration);// done
bool unguarded(int col) const;// done
void insert(int col); // done
bool remove(int, int);// Not sure???????????????
int board_size;
char[8][8];

private:

int  count;
bool col_free[max_board];
bool upward_free[2 * max_board - 1];
bool downward_free[2 * max_board - 1];
int  queen_in_row[max_board];  //   column number of queen in each row
iteration = 0;

};

#endif

*******************

#include "queens.h"

// Post: The Queens object is set up as an empty configuration on a chess board
// with size squares in each row and column
Queens::Queens(int size) {

board_size = size;
count = 0;

for(int i = 0; i < board_size; i++)
col_free[i] = true;
for(int j = 0; j < (2 * board_size - 1); j++)
upward_free[j] = true;
for(int k = 0; k < (2 * board_size - 1);
downward_free[k] = true;

}

// Pre: The square in the first unoccupied row (row count) and column col is not
// guarded by any queen.
// Post: A queen has been inserted into the square at row count and column col;
// count as incremented by 1.
void Queens::insert(int col) {

queen_in_row[count] = col;
col_free[col] = false;
upward_free[count + col] = false;
downward_free[count - col + board_size - 1] = false;
count++;

}

// Post: Returns true or false according as the square in the first unoccupied row
// (row count) and column col is not guarded by any queen
bool Queens::unguarded(int col) const {

return col_free[col] && upward_free[count + col] && downward_free[count - col + board_
size - 1];

}

// Pre: The Queens configuration represents a partially completed arrangement of
// nonattacking queens on a chessboard.
// Post: All n-queues solutions that extend the given configuration are printed. The
// configuration is restored to its initial state.
// Uses: The class Queens and the function solve_from, recursively.
void Queens::solve_from(Queens &configuration) {

if(configuration.is_solved())
configuration.print();
else
for(int col = 0; col < configuration.board_size; col++)
if(configuration.unguarded(col)) {

configuration.insert(col);
solve_from(configuration);
configuration.remove(col);

}

return;

}

bool Queens::is_solved(int col) const {

bool retvalue = false;
int row = 0;
int counter = 0;

for(col = 0; col < 8; col++) {
for(row = 0; row < 8; row++) {
if(safesquare(row,col)) {
cout<< endl << "Placed a queen" << endl;

Board [row][col]='*';
counter++;
col++;
row++;
if(row >= 7)
row = 0;
display();
}
else
{
Board[row][col] = '.';

row++;
}
iteration++;

}
}

return retvalue;

}

bool Queens::remove(int row,int col) {

bool ok = true;
int crow,ccol;
for(ccol = row - 1;(ccol>=0 && ok); ccol--)
ok = (Board[ccol][col] !='*');
for(ccol = row + 1; (ccol < 8 && ok); ccol++)
ok= (Board[ccol][col] !='*');
for((ccol = col - 1, crow = row - 1);
(ccol>=0 && crow>=0 && ok);
ccol--, crow--)
ok = (Board [crow][ccol] !='*');
for((ccol = col + 1, crow = row + 1);
(ccol < 8 && crow < 8 && ok);
ccol++, crow++)
ok = (Board [crow][ccol] !='*');

return ok;

}

void Queens::print() const {

for(int i = 0; i < 8; i++) {
if(i < 10)
cout << "   " << i;
}
cout << endl;
for(i = 0;i < 8; i++) {

if(i < 10)
cout<< " " << i << " ";
for(int j = 0; j < 8; j++)
cout << Board[i][j] << "  ";
cout<<endl;
}
return;
}

*****************************

#include <iostream>
#include <iomanip>

using namespace std;

#include "queens.h"

void print_information();
void solve_from(Queens &);

int main(void)
{
int board_size;
print_information();
cout << "What is the size of the board? " << flush;
cin >> board_size;
if (board_size < 0 || board_size > max_board)
cout << "The number must be between 0 and " << max_board << endl;
else {
Queens configuration(board_size); //   Initialize an empty configuration.
solve_from(configuration); //  Find all solutions extending configuration.
}
return 0;
}

*****************************

0
edelossantos
• 3
• 2
2 Solutions

Commented:
Um, there are a *LOT* of open ends, I left some comments in there:

#ifndef QUEENS_H
#define QUEENS_H

const int max_board = 30;

class Queens {

public:

Queens(int size);// done
bool is_solved() /*const*/; // IMHO no need to pass a col. number if you examin the whole thing
void print_information() const;// done
void solve_from(Queens &configuration);// done
bool unguarded(int col) const;// done
void insert(int col); // done
bool remove(int row, int col);

bool safesquare(int row,int col) const { return false;} // implementaiton is MISSING!
void display() const { } // implementaiton is MISSING!

int board_size;
char Board[8][8]; // name was missing!

private:

int  count;
bool col_free[max_board];
bool upward_free[2 * max_board - 1];
bool downward_free[2 * max_board - 1];
int  queen_in_row[max_board];  //   column number of queen in each row
int iteration; // int was missing

};

#endif

*******************

#include "queens.h"
#include <iostream>

using namespace std;

// Post: The Queens object is set up as an empty configuration on a chess board
// with size squares in each row and column
Queens::Queens(int size) {

board_size = size;
count = 0;

for(int i = 0; i < board_size; i++)
col_free[i] = true;
for(int j = 0; j < (2 * board_size - 1); j++)
upward_free[j] = true;
for(int k = 0; k < (2 * board_size - 1); k++)
downward_free[k] = true;

}

// Pre: The square in the first unoccupied row (row count) and column col is not
// guarded by any queen.
// Post: A queen has been inserted into the square at row count and column col;
// count as incremented by 1.
void Queens::insert(int col) {

queen_in_row[count] = col;
col_free[col] = false;
upward_free[count + col] = false;
downward_free[count - col + board_size - 1] = false;
count++;

}

// Post: Returns true or false according as the square in the first unoccupied row
// (row count) and column col is not guarded by any queen
bool Queens::unguarded(int col) const {

return col_free[col] && upward_free[count + col] && downward_free[count - col + board_size - 1];

}

// Pre: The Queens configuration represents a partially completed arrangement of
// nonattacking queens on a chessboard.
// Post: All n-queues solutions that extend the given configuration are printed. The
// configuration is restored to its initial state.
// Uses: The class Queens and the function solve_from, recursively.
void Queens::solve_from(Queens &configuration) {

if(configuration.is_solved())
configuration.print_information();
else
for(int col = 0; col < configuration.board_size; col++)
if(configuration.unguarded(col)) {

configuration.insert(col);
solve_from(configuration);
configuration.remove(0, col); // which row do you mean here?

}

return;

}

bool Queens::is_solved() {

bool retvalue = false;
int row = 0;
int counter = 0;

for(int col = 0; col < 8; col++) {
for(row = 0; row < 8; row++) {
if(safesquare(row,col)) {
cout<< endl << "Placed a queen" << endl;

Board [row][col]='*'; //you can't alter the Board in a 'const' method!
counter++;
col++;
row++;
if(row >= 7)
row = 0;
display();
}
else
{
Board[row][col] = '.'; //you can't alter the Board in a 'const' method!

row++;
}
iteration++;

}
}

return retvalue;

}

bool Queens::remove(int row, int col) {

bool ok = true;
int crow,ccol;
for(ccol = row - 1;(ccol>=0 && ok); ccol--)
ok = (Board[ccol][col] !='*');
for(ccol = row + 1; (ccol < 8 && ok); ccol++)
ok= (Board[ccol][col] !='*');
for((ccol = col - 1, crow = row - 1);
(ccol>=0 && crow>=0 && ok);
ccol--, crow--)
ok = (Board [crow][ccol] !='*');
for((ccol = col + 1, crow = row + 1);
(ccol < 8 && crow < 8 && ok);
ccol++, crow++)
ok = (Board [crow][ccol] !='*');

return ok;

}

void Queens::print_information() const {

for(int i = 0; i < 8; i++) {
if(i < 10)
cout << "   " << i;
}
cout << endl;
for(i = 0;i < 8; i++) {

if(i < 10)
cout<< " " << i << " ";
for(int j = 0; j < 8; j++)
cout << Board[i][j] << "  ";
cout<<endl;
}
return;
}

*****************************

#include <iostream>
#include <iomanip>

using namespace std;

//#include "queens.h"

void print_information();
void solve_from(Queens &);

int main(void)
{
int board_size;
print_information();
cout << "What is the size of the board? " << flush;
cin >> board_size;
if (board_size < 0 || board_size > max_board)
cout << "The number must be between 0 and " << max_board << endl;
else {
Queens configuration(board_size); //   Initialize an empty configuration.
solve_from(configuration); //  Find all solutions extending configuration.
}
return 0;
}

*****************************
0

Author Commented:

// test.cpp
//#ifndef QUEENS_H
//#define QUEENS_H

#include <iostream>
#include <iomanip>

using namespace std;

const int max_board = 30;

class Queens {

public:

Queens(int size);// done
bool is_solved() /*const*/; // IMHO no need to pass a col. number if you examin the whole thing
void print_information() const;// done
void solve_from(Queens &configuration);// done
bool unguarded(int col) const;// done
void insert(int col); // done
void place(int);
bool remove(int row, int col);
void clearboard();

bool safesquare(int row,int col) const { return false;} // implementaiton is MISSING!
void display() const { } // implementaiton is MISSING!

int board_size;
char Board[8][8]; // name was missing!

private:

int  count;
bool col_free[max_board];
bool upward_free[2 * max_board - 1];
bool downward_free[2 * max_board - 1];
int  queen_in_row[max_board];  //   column number of queen in each row
int iteration; // int was missing

};

//#endif

//#include "queens.h"
//#include <iostream>

//using namespace std;

// Post: The Queens object is set up as an empty configuration on a chess board
// with size squares in each row and column
Queens::Queens(int size) {

board_size = size;
count = 0;

for(int i = 0; i < board_size; i++)
col_free[i] = true;
for(int j = 0; j < (2 * board_size - 1); j++)
upward_free[j] = true;
for(int k = 0; k < (2 * board_size - 1); k++)
downward_free[k] = true;

}

// safe square fuction
bool Queens::safesquare(int row,int col)
{
bool ok=true;
int crow,ccol;
// To check the row
for (ccol=row-1;(ccol>=0 && ok);ccol--)
ok= (Board[ccol][col] !='*');
// To check the diagonal up left
for((ccol=col-1,crow=row-1);(ccol>=0 && crow>=0 && ok);ccol--,crow--)
ok=(Board [crow][ccol] !='*');
// To check the diagonal down right
for((ccol=col-1,crow=row+1);(ccol>=0 && crow<8 && ok);ccol--,crow--)
ok=(Board [crow][ccol] !='*');
return ok;

}

// Pre: The square in the first unoccupied row (row count) and column col is not
// guarded by any queen.
// Post: A queen has been inserted into the square at row count and column col;
// count as incremented by 1.
void Queens::insert(int col) {

queen_in_row[count] = col;
col_free[col] = false;
upward_free[count + col] = false;
downward_free[count - col + board_size - 1] = false;
count++;

}

// Post: Returns true or false according as the square in the first unoccupied row
// (row count) and column col is not guarded by any queen
bool Queens::unguarded(int col) const {

return col_free[col] && upward_free[count + col] && downward_free[count - col + board_size - 1];

}

// Pre: The Queens configuration represents a partially completed arrangement of
// nonattacking queens on a chessboard.
// Post: All n-queues solutions that extend the given configuration are printed. The
// configuration is restored to its initial state.
// Uses: The class Queens and the function solve_from, recursively.
void Queens::solve_from(Queens &configuration) {

if(configuration.is_solved())
configuration.print_information();
else
for(int col = 0; col < configuration.board_size; col++)
if(configuration.unguarded(col)) {

configuration.insert(col);
solve_from(configuration);
configuration.remove(0, col); // which row do you mean here?

}

return;

}

bool Queens::is_solved() {

bool retvalue = false;
int row = 0;
int counter = 0;

for(int col = 0; col < 8; col++) {
for(row = 0; row < 8; row++) {
if(safesquare(row,col)) {
cout<< endl << "Placed a queen" << endl;

Board [row][col]='*'; //you can't alter the Board in a 'const' method!
counter++;
col++;
row++;
if(row >= 7)
row = 0;
display();
}
else
{
Board[row][col] = '.'; //you can't alter the Board in a 'const' method!

row++;
}
iteration++;

}
}

return retvalue;

}

bool Queens::remove(int row, int col) {

bool ok = true;
int crow,ccol;
for(ccol = row - 1;(ccol>=0 && ok); ccol--)
ok = (Board[ccol][col] !='*');
for(ccol = row + 1; (ccol < 8 && ok); ccol++)
ok= (Board[ccol][col] !='*');
for((ccol = col - 1, crow = row - 1);
(ccol>=0 && crow>=0 && ok);
ccol--, crow--)
ok = (Board [crow][ccol] !='*');
for((ccol = col + 1, crow = row + 1);
(ccol < 8 && crow < 8 && ok);
ccol++, crow++)
ok = (Board [crow][ccol] !='*');

return ok;

}

void Queens::place( int col)
{
int row=0;
//for( col=0;col<boardsize;col++)
// {
for( row=0;row<8;row++)
{
if ( safesquare (row,col)) // call safe square if it is ok then place square
{
cout<<endl<<"Placed a queen"<<endl;
Board [row][col]='*'; // place a queen
col++; // increment the col
row++; // increment the row
if (row >=7 && col<8) // if row was greater than seven dont stop until col will be less than 8
row = 0;
display(); // show the board
}
else // if it is not safe square
{
row++;
Board[row][col]='.';
}
iteration++;

}
// }
}

void Queens::print_information() const {

for(int i = 0; i < 8; i++) {
if(i < 10)
cout << "   " << i;
}
cout << endl;
for(i = 0;i < 8; i++) {

if(i < 10)
cout<< " " << i << " ";
for(int j = 0; j < 8; j++)
cout << Board[i][j] << "  ";
cout<<endl;
}
return;
}

// display function
void Queens::display()
{
for ( int i=0;i<boardsize;i++)
{
cout<<"   "<<i;
}
cout<<endl;
for(i=0;i<boardsize;i++)
{
cout<<" "<<i<<" ";
for( int j=0;j<boardsize;j++)
cout<<Board[i][j]<<"  ";
cout<<endl;
}

}

// to restart and clear the board
void Queens::clearboard()
{
int i, j,x;

for (i = 0; i < boardsize; i++)
{
for (j = 0; j < boardsize; j++)
{
Board[i][j] = '.';
cout<<Board[i][j]<<"  ";
}
cout<<endl;
}
cin>>x;
}

//#include "queens.h"

//#include <iostream>
//#include <iomanip>

//using namespace std;

void print_information();
void solve_from(Queens &);

int main(void)
{
int board_size;
print_information();
cout << "What is the size of the board? " << flush;
cin >> board_size;
if (board_size < 0 || board_size > max_board)
cout << "The number must be between 0 and " << max_board << endl;
else {
Queens configuration(board_size); //   Initialize an empty configuration.
solve_from(configuration); //  Find all solutions extending configuration.
}
return 0;
}
0

Commented:
OKthat here compiles - one step further :o)

#include <iostream>
#include <iomanip>

using namespace std;

const int max_board = 30;

class Queens {

public:

Queens(int size);// done
bool is_solved() /*const*/; // IMHO no need to pass a col. number if you examin the whole thing
void print_information() const;// done
void solve_from(Queens &configuration);// done
bool unguarded(int col) const;// done
void insert(int col); // done
void place(int);
bool remove(int row, int col);
void clearboard();

bool safesquare(int row,int col) const;
void display() const;

int board_size;
char Board[8][8]; // name was missing!

private:

int  count;
bool col_free[max_board];
bool upward_free[2 * max_board - 1];
bool downward_free[2 * max_board - 1];
int  queen_in_row[max_board];  //   column number of queen in each row
int iteration; // int was missing

};

//#endif

//#include "queens.h"
//#include <iostream>

//using namespace std;

// Post: The Queens object is set up as an empty configuration on a chess board
// with size squares in each row and column
Queens::Queens(int size) {

board_size = size;
count = 0;

for(int i = 0; i < board_size; i++)
col_free[i] = true;
for(int j = 0; j < (2 * board_size - 1); j++)
upward_free[j] = true;
for(int k = 0; k < (2 * board_size - 1); k++)
downward_free[k] = true;

}

// safe square fuction
bool Queens::safesquare(int row,int col) const
{
bool ok=true;
int crow,ccol;
// To check the row
for (ccol=row-1;(ccol>=0 && ok);ccol--)
ok= (Board[ccol][col] !='*');
// To check the diagonal up left
for((ccol=col-1,crow=row-1);(ccol>=0 && crow>=0 && ok);ccol--,crow--)
ok=(Board [crow][ccol] !='*');
// To check the diagonal down right
for((ccol=col-1,crow=row+1);(ccol>=0 && crow<8 && ok);ccol--,crow--)
ok=(Board [crow][ccol] !='*');
return ok;

}

// Pre: The square in the first unoccupied row (row count) and column col is not
// guarded by any queen.
// Post: A queen has been inserted into the square at row count and column col;
// count as incremented by 1.
void Queens::insert(int col) {

queen_in_row[count] = col;
col_free[col] = false;
upward_free[count + col] = false;
downward_free[count - col + board_size - 1] = false;
count++;

}

// Post: Returns true or false according as the square in the first unoccupied row
// (row count) and column col is not guarded by any queen
bool Queens::unguarded(int col) const {

return col_free[col] && upward_free[count + col] && downward_free[count - col + board_size - 1];

}

// Pre: The Queens configuration represents a partially completed arrangement of
// nonattacking queens on a chessboard.
// Post: All n-queues solutions that extend the given configuration are printed. The
// configuration is restored to its initial state.
// Uses: The class Queens and the function solve_from, recursively.
void Queens::solve_from(Queens &configuration) {

if(configuration.is_solved())
configuration.print_information();
else
for(int col = 0; col < configuration.board_size; col++)
if(configuration.unguarded(col)) {

configuration.insert(col);
solve_from(configuration);
configuration.remove(0, col); // which row do you mean here?

}

return;

}

bool Queens::is_solved() {

bool retvalue = false;
int row = 0;
int counter = 0;

for(int col = 0; col < 8; col++) {
for(row = 0; row < 8; row++) {
if(safesquare(row,col)) {
cout<< endl << "Placed a queen" << endl;

Board [row][col]='*'; //you can't alter the Board in a 'const' method!
counter++;
col++;
row++;
if(row >= 7)
row = 0;
display();
}
else
{
Board[row][col] = '.'; //you can't alter the Board in a 'const' method!

row++;
}
iteration++;

}
}

return retvalue;

}

bool Queens::remove(int row, int col) {

bool ok = true;
int crow,ccol;
for(ccol = row - 1;(ccol>=0 && ok); ccol--)
ok = (Board[ccol][col] !='*');
for(ccol = row + 1; (ccol < 8 && ok); ccol++)
ok= (Board[ccol][col] !='*');
for((ccol = col - 1, crow = row - 1);
(ccol>=0 && crow>=0 && ok);
ccol--, crow--)
ok = (Board [crow][ccol] !='*');
for((ccol = col + 1, crow = row + 1);
(ccol < 8 && crow < 8 && ok);
ccol++, crow++)
ok = (Board [crow][ccol] !='*');

return ok;

}

void Queens::place( int col)
{
int row=0;
//for( col=0;col<boardsize;col++)
// {
for( row=0;row<8;row++)
{
if ( safesquare (row,col)) // call safe square if it is ok then place square
{
cout<<endl<<"Placed a queen"<<endl;
Board [row][col]='*'; // place a queen
col++; // increment the col
row++; // increment the row
if (row >=7 && col<8) // if row was greater than seven dont stop until col will be less than 8
row = 0;
display(); // show the board
}
else // if it is not safe square
{
row++;
Board[row][col]='.';
}
iteration++;

}
// }
}

void Queens::print_information() const {

for(int i = 0; i < 8; i++) {
if(i < 10)
cout << "   " << i;
}
cout << endl;
for(i = 0;i < 8; i++) {

if(i < 10)
cout<< " " << i << " ";
for(int j = 0; j < 8; j++)
cout << Board[i][j] << "  ";
cout<<endl;
}
return;
}

// display function
void Queens::display() const
{
for ( int i=0;i<board_size;i++)
{
cout<<"   "<<i;
}
cout<<endl;
for(i=0;i<board_size;i++)
{
cout<<" "<<i<<" ";
for( int j=0;j<board_size;j++)
cout<<Board[i][j]<<"  ";
cout<<endl;
}

}

// to restart and clear the board
void Queens::clearboard()
{
int i, j,x;

for (i = 0; i < board_size; i++)
{
for (j = 0; j < board_size; j++)
{
Board[i][j] = '.';
cout<<Board[i][j]<<"  ";
}
cout<<endl;
}
cin>>x;
}

//#include "queens.h"

//#include <iostream>
//#include <iomanip>

//using namespace std;

//void print_information();
//void solve_from(Queens &);

int main(void)
{
int board_size;

cout << "What is the size of the board? " << flush;
cin >> board_size;
if (board_size < 0 || board_size > max_board)
cout << "The number must be between 0 and " << max_board << endl;
else {
Queens configuration(board_size); //   Initialize an empty configuration.
configuration.solve_from(configuration); //  Find all solutions extending configuration.
configuration.print_information();
}
return 0;
}
0

Author Commented:
Outstanding!!!  A trillion and one thank yous' jkr.  Del
0

Author Commented:
void Queens::solve_from(Queens &configuration) {

if(configuration.is_solved())
configuration.print_information();
else
for(int col = 0; col < configuration.board_size; col++)
if(configuration.unguarded(col)) {

configuration.insert(col);
solve_from(configuration);
configuration.remove(0, col);   // which row do you mean here?

}

return;

}

>> I did not see this question.  I believe it is the row in which the queen is to be inserted.  I will have to read further into this to be certain.  Del

0

## Featured Post

• 3
• 2
Tackle projects and never again get stuck behind a technical roadblock.