Is my approach to the Eight Queens puzzle bad?

[tuesday0]

Hi there! I'm teaching myself how to program in C++ from the Deitel 10th edition "How To Program" text. I'm currently in the chapter concerning arrays, and one of the problems concerns the Eight Queens chess problem.

The Eight Queens puzzle is simple, conceptually, and many of you might already be familiar with it; the challenge is to place down eight queen pieces that don't contest one another (i.e., aren't "attacking" one another). Namely, no queen can occupy the same row, column, or diagonal as another queen.

I have some tentative code that only gets so far with the problem; in fact, it only places down six non-attacking queens. I'm currently not sure whether my approach needs to be scrapped, or if I just need to make some minor adjustments. The code uses, as requested, an "elimination" heuristic, whereby we define an array whose members represent the number of squares a queen "eliminates" from play for other queens. Basically, each array element is an integer that specifies the number of squares a queen would remove from play if she were placed there. The approach we are asked to use, then, should focus on making queens occupy squares with the lowest "elimination" values, to maximize our chances of placing down passive queens as the puzzle's solution develops.

My (doubtlessly inelegant) code, below, functions as follows. First the board is populated with zeroes (function cleanBoard achieves this). In main, queens are placed via the code inside the while loop. The loop declares and initializes an integer variable, minElim, to 29. The nested for loops check spots on the chessboard to see I) if they are valid spots for play; and II) what the elimination value for that spot is. If the elimination number is less than minElim, minElim is updated to the elimination number's value and the location is remembered via elimRow and elimColumn. Then I have the program place down a queen, denoted by char 'Q', and then mark out the spaces she eliminates with '*'s. I then update pieceCounter; after 8 pieces, the loop terminates.

One problem I identify is that the loop terminates even when eight queens aren't "placed," because pieceCounter updates regardless of what happens in the if statement. If I move it into the if statement, an infinite loop occurs, even if I specify if ( pieceCounter == 2 ){ complete = true; } . Furthermore, I don't know if I am on the right track to solving this problem using this heuristic or not; it's promising that I can get six properly placed queens, but that's two short of what I need.

I know there are plenty of code examples on this topic floating around on the internet, but they typically use methods which haven't been introduced in the textbook or are not explicitly asked for by the authors (back-tracking, for instance). So I'm not sure if I should obviate such methods or assume the authors tacitly intend for us to use them. The lines I believe the issue lies with are 32-42.

#include <iostream>
#include <iomanip>
#include <array>
#include <random>

const int squares{8};

bool validMove(std::array<std::array<char, squares>, squares>&, int, int);
void cleanBoard(std::array<std::array<char, squares>, squares>&);
void printBoard(std::array<std::array<char, squares>, squares>&);

int main() {
    std::array<std::array<char, squares>, squares> board;
    std::array<std::array<int, squares>, squares> elimination = {22, 22, 22, 22, 22, 22, 22, 22,
                                                                 22, 24, 24, 24, 24, 24, 24, 22,
                                                                 22, 24, 26, 26, 26, 26, 24, 22,
                                                                 22, 24, 26, 28, 28, 26, 24, 22,
                                                                 22, 24, 26, 28, 28, 26, 24, 22,
                                                                 22, 24, 26, 26, 26, 26, 24, 22,
                                                                 22, 24, 24, 24, 24, 24, 24, 22,
                                                                 22, 22, 22, 22, 22, 22, 22, 22};
                                                                 
    int currentRow, currentColumn, testRow, testColumn, pieceCounter{0}, scale, elimRow, elimColumn;
    bool complete{false};
    
    // populate the board with 0s
    cleanBoard(board);

    while ( !complete ) {
        int minElim{29};
        
        for ( size_t i{0}; i < squares; i++ ) {
            for ( size_t j{0}; j < squares; j++ ) {
                if ( validMove(board, i, j) ) {
                    if ( elimination[i][j] < minElim ) {
                        minElim = elimination[i][j];
                        elimRow = i;
                        elimColumn = j;
                    }
                }
            }
        }
        
        board[elimRow][elimColumn] = 'Q';
        ++pieceCounter;
        
        for ( size_t i{0}; i < squares; i++ ) {
            if ( board[elimRow][i] == '0' )
                board[elimRow][i] = '*';
        }
    
        for ( size_t i{0}; i < squares; i++ ) {
            if ( board[i][elimColumn] == '0' )
                board[i][elimColumn] = '*';
        }
    
        for ( size_t i{1}; i < squares - 1; i++ ) {
            if ( validMove(board, elimRow + i, elimColumn + i) ) 
                board[elimRow + i][elimColumn + i] = '*';
            if ( validMove(board, elimRow - i, elimColumn - i) )
                board[elimRow - i][elimColumn - i] = '*';
            if ( validMove(board, elimRow + i, elimColumn - i) )
                board[elimRow + i][elimColumn - i] = '*';
            if ( validMove(board, elimRow - i, elimColumn + i) )
                board[elimRow - i][elimColumn + i] = '*';
        }
        
        if ( pieceCounter == 8 )
            complete = true;
    }
    
    printBoard(board);
}

bool validMove(std::array<std::array<char, squares>, squares>& gameBoard, int row, int col) {
    return ( row < squares && row >= 0 && col < squares && col >= 0 && gameBoard[row][col] == '0');
}

void cleanBoard(std::array<std::array<char, squares>, squares>& gameBoard) {
    for ( size_t i{0}; i < squares; i++ ) {
        for ( size_t j{0}; j < squares; j++ ) {
            gameBoard[i][j] = '0';
        }
    }
}

void printBoard(std::array<std::array<char, squares>, squares>& gameBoard) {
    for ( size_t i{0}; i < squares; i++ ) {
        for ( size_t j{0}; j < squares; j++ ) {
            std::cout << std::setw(3) << gameBoard[i][j];
        }
        
        std::cout << std::endl;
    }
}

Edit: my output:

  Q  *  *  *  *  *  *  *
  *  *  *  *  *  *  *  Q
  *  Q  *  *  *  *  *  *
  *  *  *  *  Q  *  *  *
  *  *  *  *  *  *  Q  *
  *  *  *  *  *  *  *  *
  *  *  *  *  *  *  *  *
  *  *  Q  *  *  *  *  *

[JRManx]

Have you tried writing some pseudocode to help with the logic stuff? I find that if I get confused, a good pseudocode will be a great help.

[tuesday0]

I have not tried using any pseudocode for this problem, yet. I'll be sure to give that a go!

[lastchance]

@tuesday0,
I'm not convinced that your "place next in the position that blocks least squares" approach is guaranteed to work (though I can't prove it either way). It only thinks one step ahead and you may end up stuck at the next step.

Fundamentally, back-tracking works on the "try this square, and if it doesn't work remove it and try the next one" principle. So, if there is a solution then it would find it eventually (though it could take a very long time).

Your recursion would be at most 8 deep - I think backtracking is the most reasonable approach here, and you actually have much of the necessary code already set up.

[lastchance]

Backtracking version:

#include <iostream>
using namespace std;

const int N = 8;                                           // standard chessboard - but you can increase
bool A[N][N]{}, row[N]{}, col[N]{}, diag[2*N-1]{}, gaid[2*N-1]{};
int tcount = 0;
bool findAllCases = false;


//==========================================================


void display()
{
   for ( int i = 0; i < N; i++ )
   {
      for ( int j = 0; j < N; j++ ) cout << ".Q"[A[i][j]];
      cout << '\n';
   }
}


//==========================================================


bool check( int i, int j )                                 // check if you can place a Queen at i, j
{
   if ( row[i] || col[j] ) return false;                   // check rows and cols
                                                         
   int d = i - j + ( N - 1 ), g = i + j;
   if ( diag[d] || gaid[g] ) return false;                 // check diagonals

   row[i] = col[j] = diag[d] = gaid[g] = true;             // mark row, col, diagonals as taken
   return true;
}


//==========================================================


bool solve( int i )                                        // main backtracking routine; index is row
{
   if ( i == N )                                           // *** COMPLETION
   {
      tcount++;
      return !findAllCases;
   }

   for ( int j = 0; j < N; j++ )
   {
      int d = i - j + ( N - 1 ), g = i + j;                // store initial state
      bool ro = row[i], co = col[j], di = diag[d], ga = gaid[g];

      A[i][j] = true;
      if ( check( i, j ) && solve( i + 1 ) ) return true;  // *** MAIN RECURSIVE CALL ***

      A[i][j] = false;                                     // reinstate initial state if impossible
      row[i] = ro;   col[j] = co;   diag[d] = di;   gaid[g] = ga;
   }

   return false;
}


//==========================================================


int main()
{
   solve( 0 );
   if ( findAllCases ) cout << "Number of cases: " << tcount << '\n';
   else                display();
}

Q.......
....Q...
.......Q
.....Q..
..Q.....
......Q.
.Q......
...Q....

[tuesday0]

@lastchance
Thank you for your implementation! I will study it and see how to incorporate it into my code. Perhaps the point of the exercise is to see that a heuristic involves careful study of a problem but isn't guaranteed to work. The next exercise involves randomization and brute force approaches to solving the problem. I personally wasn't convinced of the efficacy of the heuristic either!

[tuesday0]

So I scrapped the last program and am attempting recursion. See especially lines 58-65.
Edit: I have found that the second for loop in validMove (lines 41-44) is returning false. It turns out that i = j = 18446744073709551613. There was an issue with me declaring the counter variables as size_t and not as ints. The book I use suggests always using size_t to loop through arrays...

#include <iostream>
#include <iomanip>
#include <array>

#define N 8 // number of squares in a row/column; number of queens to be placed

std::array<std::array<bool, N>, N> gameBoard{false};

void printBoard(std::array<std::array<bool, N>, N>&);
bool validMove(std::array<std::array<bool, N>, N>&, int, int);
bool solveQueen(std::array<std::array<bool, N>, N>&, int);

int main() {
    if ( !solveQueen(gameBoard, 0) )
        std::cout << "No solution found!" << std::endl;
    
    printBoard(gameBoard);
}

void printBoard(std::array<std::array<bool, N>, N>& gameBoard) {
    for ( size_t i{0}; i < N; i++ ) {
        for ( size_t j{0}; j < N; j++ ) {
            if ( gameBoard[i][j] )
                std::cout << std::setw(3) << 'Q';
            else 
                std::cout << std::setw(3) << '0';
        }
        
        std::cout << std::endl;
    }
    
    std::cout << std::endl;
}

bool validMove(std::array<std::array<bool, N>, N>& gameBoard, int row, int col) {
    for ( size_t i{0}; i < col; i++ ) { // check the row to the left
        if ( gameBoard[row][i] )
            return false;
    }
    
    for ( size_t i = row, j = col; i >= 0 && j >= 0; --i, --j ) {   // check top left diagonal
        if ( gameBoard[i][j] )
            return false;
    }
    
    for ( size_t i = row, j = col; i < N && j >= 0; ++i, --j ) {    // check bottom left diagonal
        if ( gameBoard[i][j] )
            return false;
    }
    
    return true;    // return true if no conflicts are detected
}

bool solveQueen(std::array<std::array<bool, N>, N>& gameBoard, int col) {
    if ( col == N ) // all queens have been placed
        return true;
    
    for ( size_t row{0}; row < N; row++ ) {
        if ( validMove(gameBoard, row, col) ) {
            gameBoard[row][col] = true;
            if ( solveQueen(gameBoard, col + 1) )   // recursion step
                return true;
            gameBoard[row][col] = false; // remove queen if no place is vacant
        }
    }
    
    return false; // no solution exists
}