Solved

8 Queens Game Board

Posted on 2005-04-19
417 Views
>> 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
Question by:edelossantos

LVL 86

Assisted Solution

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 Comment

// 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

LVL 86

Accepted Solution

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 Comment

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

Author Comment

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

Some Windows API functions expect you to provide a pointer to a CALLBACK function that the system will need to call as part of the operation.  Such API functions as SetTimer, timeSetEvent, CreateThread, EnumWindows, LineDDA, even window message hand…
Included as part of the C++ Standard Template Library (STL) is a collection of generic containers. Each of these containers serves a different purpose and has different pros and cons. It is often difficult to decide which container to use and …
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will learn additional member functions of the vector class. Specifically, the capacity and swap member functions will be introduced.