5

I have written a function in C++ code for the eight queens problem. The program is supposed to print out all 92 possible solutions. I only can run up to 40. Don't know where the problem is. Try to debug but I'm still stuck.

#include "stdafx.h"
#include <cmath>
#include <iostream>
using namespace std;

bool ok(int board[8][8]){
    for(int c = 7; c > 0; c--){
        int r = 0;
        while(board[r][c] != 1 ){
            r++;
        } // while loop

        for(int i = 1; i <= c; i++){
            if(board[r][c-i] == 1)
                return false;
            else if (board[r-i][c-i] == 1)
                return false;
            else if (board[r+i][c-i] == 1)
                return false;
        } // for loop

    } // for loop
        return true;
} // ok

void print(int board[8][8], int count){
    cout << count << endl;
    for(int i = 0; i < 8; i++){
        for(int j = 0; j < 8; j++){
            cout << board[i][j];
        } // for loop 
        cout << endl;

    } // for loop

    cout << endl;
} // print board

int main (){

    int board[8][8]={0};
    int count = 0;
    for(int i0 = 0; i0 < 8; i0++)
       for(int i1=0; i1 < 8; i1++)
          for(int i2 = 0; i2 < 8; i2++)
         for(int i3 = 0; i3 < 8; i3++)
            for(int i4 = 0; i4 < 8; i4++)
           for(int i5 = 0; i5 < 8; i5++)
              for(int i6 = 0; i6 < 8; i6++)
                 for(int i7 = 0; i7 < 8; i7++){
                board[i0][0]=1;
                            board[i1][1]=1;
                            board[i2][2]=1;
                            board[i3][3]=1;
                            board[i4][4]=1;
                            board[i5][5]=1;
                            board[i6][6]=1;
                            board[i7][7]=1;

                            if(ok(board))print(board, ++count);

                            board[i0][0]=0;
                            board[i1][1]=0;
                            board[i2][2]=0;
                            board[i3][3]=0;         
                            board[i4][4]=0; 
                            board[i5][5]=0;
                            board[i6][6]=0;
                            board[i7][7]=0;

                                }
    return 0;
}
menjaraz
  • 7,551
  • 4
  • 41
  • 81
Mister Bunker
  • 93
  • 3
  • 9

1 Answers1

14

Your problem is in the ok function. It has three errors, all relating to the bounds of your matrix. The first error (which will if anything cause you to receive too many solutions), is here:

for(int c = 7; c > 0; c--){

This will never check column 0. The test should be c >= 0.

The other two errors, which cause unpredictable behavior, are here:

    for(int i = 1; i <= c; i++){
        if(board[r][c-i] == 1)
            return false;
        else if (board[r-i][c-i] == 1)
            return false;
        else if (board[r+i][c-i] == 1)
            return false;
    } // for loop

This can cause the ok function to return an arbitrary number of false negatives. In my case, compiling and running your program with these two errors produced no solutions. It is only by chance that it produces 40 solutions for you.

The problem is again with bounds. The i variable is moving from 1 up to and including c, so c-i moves down from c-1 to 0, as intended.

However, you are not checking that r-i and r+i remain within the bounds of the matrix. Consider the case that r = 7 and i = 4. Then, r+i = 11, which runs past the end of the row. Similarly, if r = 0 and i is anything other than 0, r-i will be negative and run past the beginning of the row.

You need to add additional checks to make sure that the row values used in the tests within this loop are within the range 0 to 7. You can take advantage of the short-circuiting behavior of the logical operators in C++ to do this, for example:

 else if (<test> && board[r-i][c-i] == 1)

will examine board[r-i][c-i] only if <test> is true.

I'm leaving adding the corrections to these second two errors as an exercise for you, since this is very likely to be a homework assignment (and if it is, you should add the [homework] tag to the question).

Tyler McHenry
  • 74,820
  • 18
  • 121
  • 166