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

8 Queens Game Board

>> In this program I had to provide the implementations for is_solved() const, remove(), and print().  
Not sure if this is the correct syntax.  Please advise.

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


#ifndef QUEENS_H
#define QUEENS_H

const int max_board = 30;

class Queens {

public:

   Queens(int size);// done
   bool is_solved(int) const; // I am not sure about this implementation??????????????
   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
Asked:
edelossantos
  • 3
  • 2
2 Solutions
 
jkrCommented:
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
 
edelossantosAuthor Commented:
>> jkr, I added the missing implementations and also added two other implementations.  Please advise and thank you.  Del

// 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
 
jkrCommented:
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
 
edelossantosAuthor Commented:
Outstanding!!!  A trillion and one thank yous' jkr.  Del
0
 
edelossantosAuthor 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

Free Tool: Site Down Detector

Helpful to verify reports of your own downtime, or to double check a downed website you are trying to access.

One of a set of tools we are providing to everyone as a way of saying thank you for being a part of the community.

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