Hi I'm currently taking an introductory programming course and my final project is to write the infamous N-Queens program (find & display all possible solutions for N queens on an NxN board such that they cannot attack one another) using recursion

I feel like I at least have a slight grasp of what I'm supposd to be doing, however when I run my code, the program keeps on crashing and I don't know what the problem is; any help would be greaty appreciated

note: in my program I denote the chessboard as an array of 'n' numbers where the array index is the column # and the number itself denotes the row position of the queen,,,(also i've been running/crashing my program with N=4, as trials if that should matter)

#include <iostream>
#include <math.h>

int n;//globally defined board size
int count = 1;//# of solutions counter
void nqueen(int board[], int col, int row);

//function runs from column 0 to n (left to right), each column starting at top row 1
void nqueen(int board[], int col, int row){
     if (col > n){//solution is found
        std::cout<<"solution "<<count<<std::endl;
        for (int i=0;i<n;i++){//display chessboard permutation of n numbers
            std::cout<<board[i];
            }
        std::cout<<std::endl;
        count += 1;//increment counter
        return;
        }
   
     while (row <= n){
           bool queen = true;//assume queen is placeable at row, col
           if (col = 0){//first column is automatically accepted
              board[col] = row;
              nqueen(board, col+1, 1);
              }
           for (int i=0;i<col;i++){//check against previous columns
               if (board[i] == row || fabs(board[i]-row) == fabs(i-col)){
                  queen = false;//if conflicting, can't place queen
                  }
               }
           if (queen == true){//if not conflicting, place queen and move onto next column
              board[col] = row;
              nqueen(board, col+1, 1);
              }
           if (queen == false){//conflicting, so increment row
              row += 1;  
              }    
     }
     nqueen(board, col-1, board[col-1]+1);//if row > n go to previous column and increment row
}


int main(){

    
    std::cout<<"Enter integer N: ";
    std::cin>>n;
    std::cin.ignore();
    
    int *board;
    board = new int[n];
    
    for (int i=0;i<n;i++){
        board[i] = 0;
        }
    
    nqueen(board, 0, 1);
    
    std::cin.get();
    return 0;
}

o yea also...currently I'm only responsible for finding all possible solutions (not distinct solutions)...so for 8x8 there should be 92...4x4 there should be 2 etc.

I am somewhat familiar with the problem, though not very familiar with the algorithm to solve it. I ran your code with some debugging output. Your function:

void nqueen(int board[], int col, int row)

is called thousands of time with row and col equal to 1 so you are in an infinite recursive call, eventually leading to a stack overflow. This line is never called as far as I can tell:

nqueen(board, col-1, board[col-1]+1);//if row > n go to previous column and increment row

So it looks to me like a parameter (col or row) is not getting changed when it should be or is getting changed when it shouldn't be.

I'm guessing your problem is this line:

if (col = 0)

= is the assignment operator. Do you mean ==, the comparison operator?

yea your right I meant '=='...but even with that my code is still crashing (or infinite looping I guess)

I'm still not sure why the function is looping infinitely (and I'm quite clueless as to how to debug at all besides using std::cout to see whats going on...but that doens't work since the program crashes right after i input N)

thx alot for your input Vernon

yea your right I meant '=='...but even with that my code is still crashing (or infinite looping I guess)

I'm still not sure why the function is looping infinitely (and I'm quite clueless as to how to debug at all besides using std::cout to see whats going on...but that doens't work since the program crashes right after i input N)

thx alot for your input Vernon

You're welcome. Here's what I did. I've changed your program slightly to incorporate one way to add some debugging, plus I changed the = to == (it's also not a bad idea to use an IDE and learn to use its debugger. You can quickly add breakpoints and see variable values). Your program actually does not crash right after you input N. There are several recursive calls before then. I've added a pause function and a call to pause at the top of your function. You may want to sprinkle that call (and add more debugging output) elsewhere. Run it, hit the return key a few times, and soon you'll see some very strange numbers that you almost certainly don't want, but which may help you track down the problem. Good luck!

#include <iostream>
#include <math.h>

int n;//globally defined board size
int count = 1;//# of solutions counter
void nqueen(int board[], int col, int row);


void pause (int col, int row)
{
     std::cout << "col = " << col << std::endl;
     std::cout << "row = " << row << std::endl;
     std::cout << "Press return key\n";
     char returnKey;
     std::cin.get(returnKey);
}


//function runs from column 0 to n (left to right), each column starting at top row 1
void nqueen(int board[], int col, int row){
     pause(col, row);
     if (col > n){//solution is found
        std::cout<<"solution "<<count<<std::endl;
        for (int i=0;i<n;i++){//display chessboard permutation of n numbers
            std::cout<<board[i];
            }
        std::cout<<std::endl;
        count += 1;//increment counter
        return;
        }
   
     while (row <= n){
           bool queen = true;//assume queen is placeable at row, col
           if (col == 0){//first column is automatically accepted
              board[col] = row;
              nqueen(board, col+1, 1);
              }
           for (int i=0;i<col;i++){//check against previous columns
               if (board[i] == row || fabs(board[i]-row) == fabs(i-col)){
                  queen = false;//if conflicting, can't place queen
                  }
               }
           if (queen == true){//if not conflicting, place queen and move onto next column
              board[col] = row;
              nqueen(board, col+1, 1);
              }
           if (queen == false){//conflicting, so increment row
              row += 1;  
              }    
     }
     nqueen(board, col-1, board[col-1]+1);//if row > n go to previous column and increment row
}


int main(){

    
    std::cout<<"Enter integer N: ";
    std::cin>>n;
    std::cin.ignore();
    
    int *board;
    board = new int[n];
    
    for (int i=0;i<n;i++){
        board[i] = 0;
        }
    
    nqueen(board, 0, 1);
    
    std::cin.get();
    return 0;
}

ooo wow i never would've thought of doing that myslef thanks alot...this is really helping me toward the right direction

yay...well i came to the realization that the way i had coded it the first (base) condition should've been "if (col == n){ solution found}" now I'm just trying to fix the fact that the program finds only this first solution and juss keeps looping this one solution

hi ChickenFox,
here comes my c++ solution similar to yours. It works well and finds all possible 92 solutions of an 8 by 8 board. You may look at check function what easily checks the row and both diagonals of a tentatively placed queen.

int nbs = 0;
    bool check(int board[], int k)
    { for (int i=0; i<k;i++)
      { if ((board[i]==board[k])||((board[i]-board[k])==(k-i))
        || ((board[k]-board[i])==(k-i))) return 0;
      } return 1;}
    void Queens(int nn, int board[], int k=0)
    { if (k==nn)
      { cout<<endl<<"Solution "<<(++nbs)<<":"<<endl;
        for (int i=0; i<nn; i++)
        { for (int j=0; j<nn;j++)
          { if (board[i]==j) cout<<("Q "); else cout<<(". ");
          } cout<<endl;} cout<<endl;}
        else
        { for (int i=0; i<nn; i++)
          { board[k]=i; if (check(board, k)) Queens(nn, board, k+1);
        }}}
    int main(int argc, char *argv[])
    { int nn = 8;
      int *board = new int[nn];
      Queens(nn, board);
      return 0;}

Here some output:

Solution 1:
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .

. . .

Solution 92:
. . . . . . . Q
. . . Q . . . .
Q . . . . . . .
. . Q . . . . .
. . . . . Q . .
. Q . . . . . .
. . . . . . Q .
. . . . Q . . .

krs,
tesu

oo thanks a lot ...yea i suspected having a separate check function is more reasonable...but being stubborn i juss kept trying to do it within the queen function

also what is the reasoning behind "int main(int argc, char *argv[])"...i mean i understand it's the main function but why are there parameters set instead of just "int main()"

thx again tesu

oo thanks a lot ...yea i suspected having a separate check function is more reasonable...but being stubborn i juss kept trying to do it within the queen function

also what is the reasoning behind "int main(int argc, char *argv[])"...i mean i understand it's the main function but why are there parameters set instead of just "int main()"

thx again tesu

You can pass parameters to the program that way. For example, if you compile this program and call it dummy.exe, then type this at the command line:

dummy Hello World

you'll get the following output:

Number of parameters = 3
The name of this program is: dummy
Here are the other parameters: 
Hello
World

This can be useful in some programs.

// Filename : dummy.cpp
#include <iostream>
int main (int argc, char* argv[])
{
    std::cout << "Number of parameters = ";
    std::cout << argc << std::endl;
    std::cout << "The name of this program is: ";
    std::cout << argv[0] << std::endl;
    std::cout << "Here are the other parameters: " << std::endl;
    for (int i = 1; i < argc; i++)
         std::cout << argv[i] << std::endl;
         
    return 0;
}

thx alot dozier & tesu i finally got my program to work as i want it and realize my errors...or more correctly...areas where i could've been more efficient programming-wise

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.