I want to ask anyone here on how to solve the 8 queens problem only using a one dimensional array. I am not a student, however I did graduate with a Computer Science degree and I have been going back over some of my older C++ books just to see if I can still do some the problems again just because I have time to kill at work right now. Anyway, back to the point I am currently doing a problem from Data Abstraction and Problem Solving with C++ Walls and Mirrors 4/e that specifies to use a 1d array for the board. My brain is having a hard time grasping how it can be accomplished and I was wondering if I could get some help.

Here is the header file for the Queen class


#ifndef QUEEN_H
#define QUEEN_H

class Board; // declaration of Board class

/** @class Queen
* The Queen class. */
class Queen
{
public:
/** Puts queen in upper left corner of board. */
Queen();
/** Places Queen in supplied location. */
Queen(int inRow, int inCol);

/** @return Column number. */
int getCol() const;
/** @return Row number. */
int getRow() const;
/** Moves queen to next row.*/
void nextRow();

/** Determines whether the queen is under attack by another queen.
* @return If there is a queen in the same row or the same
* diagonal, returns true; otherwise, returns false. */
bool isUnderAttack() const;

/** Saves a pointer to the board for all queens. */
static void setBoard(const Board *bPtr);

private:
/** Row (or prospective row) of queen if it is on the board. */
int row;
/** Column (or prospective column) of queen if it is on the board. */
int col;

/** All queens share the same board. */
static const Board *boardPtr;
}; // end Queen

#endif

The Board class


#ifndef BOARD_H
#define BOARD_H

#include "Queen.h"
#include <vector>
#include <iostream>

using namespace std;

static const int BOARD_SIZE = 8;

/** The Board class. */
class Board
{
public:
/** Supplies the Queen class with a pointer to the board. */
Board();
/** Clears the board and removes pointer from queens. */
~Board();

/** Clears board. */
void clear();
/** Displays board. */
void display() const;

/** Initiates the Eight Queens problem. */
void doEightQueens();

/** @return The number of queens on the board. */
int getNumQueens() const;

/** @return A pointer to the queen at the designated index. */
const Queen *getQueen(int index) const;

private:

/** Determines whether there is a queen in position (inRow,
* inCol). */
bool isQueen(int inRow, int inCol) const;

/** Attempts to place queens on board starting with the
* designated queen. */
bool placeQueens(Queen *queenPtr);

/** Removes the last queen on the board, but does not delete
* it. */
void removeQueen();

/** Places a queen on the board. */
void setQueen(const Queen *queenPtr);

/** Array of queens on the board. */
vector<const Queen *> queens;
}; // end Board

#endif

And the author actually gives you the placeQueens function implementation

bool Board::placeQueens(Queen *queenPtr)
{
// Base case. Trying to place Queen in a non-existent column.
if (queenPtr->getCol() >= BOARD_SIZE)
{ delete queenPtr;
return true;
} // end if

bool isQueenPlaced = false;

while (!isQueenPlaced && queenPtr->getRow() < BOARD_SIZE)
{ // If the queen can be attacked, then try moving it to the
// next row in the current column.
if (queenPtr->isUnderAttack())
queenPtr->nextRow();
// Else put this queen on the board and try putting a new
// queen in the first row of the next column.
else
{ setQueen(queenPtr);
Queen *newQueenPtr = new Queen(0, queenPtr->getCol() + 1);
isQueenPlaced = placeQueens(newQueenPtr);
// If it wasn't possible to put the new Queen in the next
// column, backtrack by deleting the new Queen and
// removing the last Queen placed and moving it down one
// row.
if (!isQueenPlaced)
{ delete newQueenPtr;
removeQueen();
queenPtr->nextRow();
} // end if
} // end if
} // end while
return isQueenPlaced;
} // end placeQueens


Alrighty so here is what my implentation for Queen class is thus far:


Queen::Queens(): row(0), col(0)
{}

Queen::Queen(int inRow, int inCol): row(inRow), col(inCol)
{}

int Queen::getCol() const
{
return col;
}

int Queen::getRow() const
{
return row;
}

void Queen::nextRow()
{
row += 1;
}

bool Queen:isUnderAttack() const
{
// this is where I am scratching my head
}

void Queen::setBoard(const Board *bPtr)
{
// a little confused on what exactly goes on in here
}


The Board implentation thus far:

Board::Board()
{
queens.capacity(BOARD_SIZE);
}

Board::~Board()
{
queens.clear();
}

void Board::clear()
{
queens.clear();
}

// haven't implemented anything else


So my main question is how to solve the isUnderAttack() function. How do you index items that are queens using a row and column when your vector is a 1d array? Is there an indexing trick I am just not getting? Anyhow I am hoping that once I have this question answered I will be able to solve the rest on my own. Thanks for any help! Please feel free to ask any questions if I am not being clear on anything.

you can allocate a 1d array and access it like a 2d array:

for(int i = 0; i < height; ++i)
{
for(int j = 0; j < width; ++j)
{
... array[width * i + j] ...
}
}

you can allocate a 1d array and access it like a 2d array:

for(int i = 0; i < height; ++i)
{
for(int j = 0; j < width; ++j)
{
... array[width * i + j] ...
}
}

That would work great if the array wasn't of size 8, if the array was say size of 64 it would definitely solve the problem. Thanks for your comment. The book gives the following explanation for the single dimension array of size 8.

The simplest representation would be a 2d array; however, such an array wastes space because only 8 squares out of 64 are used. Another approach would be to use a 1d array of only the squares that contain a queen.
[/quote]

Unless I am misunderstanding the question, doesn't that mean use only an array size of 8? Indicated by the BOARD_SIZE constant the author supplies you with.

In the 8-queens problem each column contains exactly one queen. Instead of a 2D array indicating which squares are occupied, you can use a 1D array that indicates where in the column you have a queen.

By the way, we have *very* different programming styles.

#include <iostream>
#include <algorithm>
#include <cstdlib>

int main() {
int a[8]={0,1,2,3,4,5,6,7};
while (std::next_permutation(a,a+8)) {
for (int i=0; i<7; ++i) {
for (int j=i+1; j<8; ++j) {
if (std::abs(a-a[j])==(j-i))
goto CONTINUE;
}
}
for (int i=0; i<7; ++i)
std::cout << a << ' ';
std::cout << '\n';
CONTINUE:;
}
}


In the 8-queens problem each column contains exactly one queen. Instead of a 2D array indicating which squares are occupied, you can use a 1D array that indicates where in the column you have a queen.

Ah I get it!! I don't know why my brain was having a hard time with it but I see what your saying here. For instance, if a queen is in column 1 row 3 the array would as follows: board[0] = 2. This is based on row and column indexing starting at 0. Thanks that helps out a ton, I don't know why I wasn't seeing it at first but that was a very helpful hint

Ok so two steps forward and one step back, grrr. Anyway so I understand how the 1d array represents the entire board, however I am still fuzzy on how to implement a couple of functions in board. The function bool isQueen(int inRow, int inCol) const.

Here is what I am thinking

[source lang="cpp"]
bool Board::isQueen(int inRow, int inCol)
{


}
[/source]

I am correct in this assumption? If the queen at this columns row matches the desired row, then a queen already exists there. This would be because every queen initially is assigned 0,0 as it's starting row/col.

Question:

For the Queen class the static void setBoard(const Board* bPtr) function obviously relates directly to the private member static const Board *boardPtr. The issue I am having trouble following is that I know the static private variable Board is used by all instances of Queen (I'd hope I would know that!), anyway the function static void setBoard(const Board* bPtr) then would be as follows I assume:


void Queen:setBoard(const Board *bPtr)
{
boardPtr = bPtr
}


I haven't really needed to use static functions/members in awhile so I am sort of confused on how you set this pointer up. In the board class do you then just do the following:


Board::Board()
{
queens.at(0)->setBoard(this);

// or this which doesn't feel like this is correct but makes sense because it would issue the pointer to the Queen class in general
Queen::setBoard(this)
}