8 Queens Variation- Number of Arrangements Backtracking Implementation- Wrong Output

Question

I'm trying to write a program that, given an initial input, will count the number of different arrangements of 8 queens on an 8X8 chessboard. For some reason, my test data is not giving me the appropriate output. I was wondering if you guys could point me in the right direction. I am having no compiler errors, but I am getting a segmentation fault on the last data set.

I've tried debugging, but I think I've just looked at my code for so long that I'm starting to confuse myself. If anyone could give me some help, I would be grateful. Thanks. I think my problem is either in isSafe function, or in my terminating conditions in the solveNQUtil method.

My test data, (each line is a separate case of row, column, my output and expected result):

r    c    Output      Expected output
1    2       14         8
6    7       8          14
7    8       312        8
8    8       312        4
2    2       4          16
2    4       12         8
1    7       8          8
8    3    Seg Fault     16

My code:

#include <iostream>
#include<stdio.h>
using namespace std;
int arrangements = 0;
int column_start = 0;
/* A utility function to print solution */
void printSolution(int board[8][8])
{
    for (int i = 0; i < 8; i++)
    {
        for (int j = 0; j < 8; j++)
            if( board[i][j] ) {
                printf(" Q ");
            }else{
                printf(" . ");
            }
            //printf(" %d ", board[i][j]);
        printf("\n");
    }
}
bool isSafe(int board[8][8], int row, int col)
{
    int i, j;
    for (i = 0; i < 8; i++){
        if (board[row][i]){
            return false;
        }
    }
    for (i = row, j = col; i >= 0 && j >= 0; i--, j--){
        if (board[i][j]){
            return false;
        }
    }
    for (i = row, j = col; i < 8 && j < 8; i++, j++){
        if (board[i][j]){
            return false;
        }
    }
    for (i = row, j = col; j >= 0 && i < 8; i++, j--) {
        if (board[i][j]){
            return false;
        }
    }
    for( i = row, j = col; j < 8 && i >= 0; i--, j++){
        if (board[i][j]){
            return false;
        }
    }
    return true;
}
void solveNQUtil(int board[8][8], int queens, int col)
{
    if (queens >= 8){
        printSolution(board);
        cout << "---------------------------------------------" << endl;
        arrangements++;
    }else{
        for (int i = 0; i < 8; i++){
            if ( isSafe(board, i, col) ){
                board[i][col] = 1;
                int tempCol = (col + 1) % 8;
                solveNQUtil(board, queens + 1, tempCol );
                //backtrack
                board[i][col] = 0; 
            }
        }  
    }
}
bool solveNQ(){
    int row = 0;
    int col = 0;
    int board[8][8];
    for(int i = 0; i < 8; i++){
        for(int j = 0; j < 8; j++){
            board[i][j] = 0;
        }
    }
    cin >> row >> col;
    board[row][col] = 1;
    column_start = col;
    solveNQUtil(board, 1, (col + 1) % 8);
    //solveNQUtil(board,0,0);
    if(arrangements == 0){
        printf("Solution does not exist");
        return false;
    }
    return true;
}
int main(){
    solveNQ();
    cout << "Arrangements: " << arrangements << endl;
    return 0;
}

Answer 1

You programmed it to start from zero index, so you just need to decrement input by one. All output will match the expected result.

cin >> row >> col;
row--;
col--;
if (row < 0 || row >= 8 || col < 0 || col >= 8) return false;

Answer 2

As long as your row < 8 and col < 8 the output you are getting is correct. The expected output you have given is wrong.

When row = 8 or col = 8 the array index goes outof bound and tries to assign the value to some memory which is not allocated to your array.

• If that other memory is free it will store in it and there wont be any error but your output will be wrong because your first queen is outside the board but you are telling your solveNQUtil that there is a queen in the board.
• But if that other memory is already allocated to something else you will get segmentation fault.