patterncppModerate

N*N queen algorithm

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

algorithmqueenstackoverflow

Problem

I was just playing around with N queen problems means accommodating N queens on NN chees board such that no one can kill each other. I tried a simple algorithm which uses backtracking.The program is working fine till 29 queens but after 29 it is just going on and on..I am not able to decide is it due to some logic error or due to too much calculations need to be done above 2929..

I am pasting my code here.It is a win32 console applications. If anyone can tell me some logic error or some way of optimizing it..It would be helpful to me..

Code..

```
// Queen_Game.cpp : Defines the entry point for the console application.
#include
using namespace std;
class chess_block
{
public:
bool bQueen;
chess_block()
{
bQueen=false;
}
};
bool IsSafeToPutQueen(int nRow, int nCol,chess_block **Chess_Board,int n )
{
// We need to check for three directions upper left diagonal, lower left diagonal, and left horizontally;
int nTempColLeft=nCol-1; int nTempBelowRow=nRow+1;int nTempAboveRow=nRow-1;
bool bSafe=true;
//
while(nTempColLeft>=0 || nTempBelowRow=0)
{
if( ((nTempAboveRow>=0)&&(nTempColLeft>=0)&&(Chess_Board[nTempAboveRow][nTempColLeft].bQueen==true)) /Left Upper Diagonal/
||((nTempBelowRow=0)&&(Chess_Board[nTempBelowRow][nTempColLeft].bQueen==true))/Left Lower Diagonal/
||((nTempColLeft>=0)&&(Chess_Board[nRow][nTempColLeft].bQueen==true))) /Left Block/
{

bSafe=false;
break;

}
else
{

nTempColLeft--;
nTempAboveRow--;
nTempBelowRow++;
}
}
return bSafe;
}

chess_block **PrepareTheChessBoard(int n)//Allocate memory for n*n blocks
{
//chess_block Chess_Board= (chess_block )malloc(nsizeof(chess_block ));

ches

Solution

You didn't wait long enough. The code works.

Your programming style is very much oriented around "C". You should work your way through a good book on C++. But even if you don't, there's a lot you could do to improve it even in the style as written.

-
Idiomatically, you shouldn't test boolean variables against true and false. It's legal, and the existence of a native boolean type means it's not dangerous like it was in C. But instead of if (condition == true) you can just say if (condition), and instead of if (condition == false) you can say if (!condition) or if (not condition). The "not" keyword is only in C++ and less commonly seen, but there are other verbose terms like "and" instead of &&...as well as "or" instead of || since the beginning. They're standard and I find them more pleasant, and easier to see as I edit code in a proportional font. If you're using bool and true/false you've already got a C++ buy-in, why not use them?

-
Hungarian Notation prefixes are horribly misunderstood. Their proper use depends on creating new abstract types...not robotic encoding of the low level implementation types. So instead of int nRowMax; int nColumnFirst; you would say something like typedef int Row; typedef int Column; and then declare Row rowMax; Column columnFirst; Whether you find that stilted compared to "maxRow" and "firstColumn" or short variable names like "r" and "c" is an issue of personal preference...and you can debate that with people all day. But NO ONE should put n in front of each and every integer variable, it's silly and was never even correct Hungarian to begin with.

(Note: I prefer things like rowMax to maxRow. If I find myself in a routine with a single Row variable, I can start by calling it just "row" and then I only bother to give it differentiating suffixes based whether it's needed by the context. This process is an easier transformation: say I start with Row row and then that works for a while, until I realize I need a "remote" and a "local" row. I just tack "Local" on and get rowLocal and don't need to recase it like localRow. Something about putting it's "rowness" first also appeals to me aesthetically...kind of like how I prefer the way Spanish puts the nouns in front of the adjectives.)

-
Pursuant to the previous point, avoid prefixing boolean variables with b. What I like to do is to have boolean variables start with stems like "has", "is", "was", "should", etc. This leads to an English-like readability of conditional logic, like if (shouldDeleteFile) { ... } I think the Qt API guidelines have some interesting philosophies on this and other points: http://doc.qt.nokia.com/qq/qq13-apis.html#theartofnaming

-
You had a constructor for your chess_block which set bQueen to false. Yet your code still had to loop through the arrays you dynamically allocated to set bQueen to false. That's just one of the many reasons to use new and delete in C++ (and their array forms new[] and delete[]).

-
Don't obfuscate your algorithms. For instance, you used a for loop that always incremented a counter and then try and "undo" the effect of the coming increment by subtracting. There are other kinds of loops...while and do/while. If you don't always want to increment the counter (and sometimes want to subtract from it) then make that logic more clear by separating out the incrementation part.

-
When posting code on StackOverflow, try to make it so there's no horizontal scroll bar. That's really frustrating to read on the web. If possible, isolate your problem to samples that can fit without a vertical scroll bar.

There is a lot more you can do. C++ offers vectors that are safer and easier to work with than raw dynamic allocation of arrays. If you start encapsulating N inside of a board class then you can pass board objects around and they will carry their size with them. Knowing C++ is a good thing. But here's an example of the kind of very basic changes I am talking about without invasively redesigning your code:

```
#include

using namespace std;

struct Square {
bool hasQueen;
Square () {
hasQueen = false;
}
};

void PrintChessBoard(Square** board, int n) {
for (int row = 0; row = 0) or (rowBelow = 0)) {
bool leftUpperDiagonalAttack = (rowAbove >= 0)
and (columnLeft >= 0)
and board[rowAbove][columnLeft].hasQueen;

bool leftLowerDiagonalAttack = (rowBelow = 0)
and board[rowBelow][columnLeft].hasQueen;

bool leftAttack = (columnLeft >= 0)
and board[row][columnLeft].hasQueen;

if (leftUpperDiagonalAttack or leftLowerDiagonalAttack or leftAttack) {
return false;
} else {
columnLeft--;
rowAbove--;
rowBelow++;
}
}
return true;
}

bool CanSolveWithBackTrack(Square** board, int n) {
bool inBacktrack = false;
int column = 0;
while (column > n;

// Dynamically allocate array of arrays for chess board
Square** boa

Code Snippets

#include <iostream>

using namespace std;

struct Square {
  bool hasQueen;
  Square () {
    hasQueen = false;
  }
};

void PrintChessBoard(Square** board, int n) {
  for (int row = 0; row < n; row++) {
    for (int column = 0; column < n; column++) {
      if (board[row][column].hasQueen) {
        cout << "Q";
      } else {
        cout << ".";
      }
    } 
    cout << "\n";
  }
}

bool IsSafeToPutQueen(int row, int column, Square** board, int n) {
  int columnLeft = column - 1;
  int rowBelow = row + 1;
  int rowAbove = row - 1;

  while ((columnLeft >= 0) or (rowBelow < n) or (rowAbove >= 0)) {
    bool leftUpperDiagonalAttack = (rowAbove >= 0) 
        and (columnLeft >= 0) 
        and board[rowAbove][columnLeft].hasQueen;

    bool leftLowerDiagonalAttack = (rowBelow < n) 
        and (columnLeft >= 0) 
        and board[rowBelow][columnLeft].hasQueen;

    bool leftAttack = (columnLeft >= 0) 
        and board[row][columnLeft].hasQueen;

    if (leftUpperDiagonalAttack or leftLowerDiagonalAttack or leftAttack) {
      return false;
    } else {
      columnLeft--;
      rowAbove--;
      rowBelow++;
    }
  }
  return true;
}

bool CanSolveWithBackTrack(Square** board, int n) {
  bool inBacktrack = false;
  int column = 0;
  while (column < n) {
    bool wasQueenPlaced = false;
    for (int row = 0; row < n; row++) {
      if (IsSafeToPutQueen(row, column, board, n)) {
        if (inBacktrack) {
          if (board[row][column].hasQueen) {
              board[row][column].hasQueen = false;
              inBacktrack = false;
              // now Move to Next Row
              continue;
          }
        } else {
          board[row][column].hasQueen = true;
          wasQueenPlaced = true;
          break;              
        }
      }
    }

    if ((not wasQueenPlaced) and (not board[n-1][column].hasQueen)) {
      column--;
      if (column < 0) {
        // can't solve it
        return false;
      }
      inBacktrack = true;
    } else {
      column++;
    }
  }
  return true;
}

int main(int argc, char* argv[]) {
  // Read board size from user
  int n = 0;
  cout << "Enter the value of N" << "\n";
  cin >> n;

  // Dynamically allocate array of arrays for chess board 
  Square** board = new Square*[n];
  for (int i = 0; i < n; i++) {
    board[i] = new Square[n];
  }

  // Print out the board if solvable, or an error message
  if (CanSolveWithBackTrack(board, n)) {
    cout << "This combination CAN place the queens!" << "\n";
    PrintChessBoard(board, n);
  } else {
    cout << "This combination CAN'T place the queens." << "\n";
  }

  // Free chess board arrays...MUST use array form "delete[]"!
  for (int i = 0; i < n; i++) {
    delete[] board[i];
  }
  delete[] board;

  return 0;
}

Context

StackExchange Code Review Q#6690, answer score: 10

Revisions (0)

No revisions yet.