N*N queen algorithm

Question

I was just playing around with N queen problems means accommodating N queens on N*N 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 29*29..

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 <iostream>
    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<n || nTempAboveRow>=0)
        {
            if( ((nTempAboveRow>=0)&&(nTempColLeft>=0)&&(Chess_Board[nTempAboveRow][nTempColLeft].bQueen==true))    /*Left Upper Diagonal*/
                ||((nTempBelowRow<n)&&(nTempColLeft>=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(n*sizeof(chess_block *));

        chess_block **Chess_Board= new chess_block *[n];

        for(int i=0;i<n;i++)
        {

            Chess_Board[i]=new chess_block[n];

        }
        for(int nColumn=0;nColumn<n;nColumn++)
        {
            for(int nRow=0;nRow<n; nRow++)
            {

                Chess_Board[nRow][nColumn].bQueen=false;
            }
        }
        return Chess_Board;
    }
    void DestroyTheChessBoard(chess_block **Chess_Board,int n)
    {
        for(int i=0;i<n;i++)
        {
            delete [](Chess_Board[i]);

        }
        delete [](Chess_Board);
    }

    void PrintPositionsOfQueens(chess_block **Chess_Board,int n)
    {

        for(int nColumn=0;nColumn<n;nColumn++)
        {
            for(int nRow=0;nRow<n; nRow++)
            {
                if(Chess_Board[nRow][nColumn].bQueen==true)//Put The Queen Here
                {

                    cout<<"Column No.:   "<<nColumn   <<"               "<<"Row Number:   "<<nRow<<"\n";
                }

            }
        }    

    }
    void ArrangeQueensOnBoard(chess_block **Chess_Board,int n)
    {
        bool bBackTrack=false;
        int nRow=0;
        for(int nColumn=0;nColumn<n;nColumn++)
        {
            for(nRow=0;nRow<n; nRow++)
            {

                if(IsSafeToPutQueen(nRow,nColumn,Chess_Board,n))
                {
                    if(bBackTrack && Chess_Board[nRow][nColumn].bQueen==true)
                    {
                        Chess_Board[nRow][nColumn].bQueen=false;
                        bBackTrack=false;
                        continue;
                    }
                    else if(!bBackTrack)
                    {
                        Chess_Board[nRow][nColumn].bQueen=true;
                        break;//Now Move to Next Col
                    }
                }
            }
            if(nRow ==n && Chess_Board[n-1][nColumn].bQueen==false)//means we need to backtrack
            {
                nColumn--;
                if(nColumn<0)
                {
                    cout<<"THis combination can't place the queen ";
                    break;
                }
                nColumn--;
                bBackTrack=true;
            }

        }

    }
    int _tmain(int argc, _TCHAR* argv[])
    {
        while(1)//Don't be offended for this while loop it is only for keeping the command prompt window on the screen always
        {
            int n=0;
            cout<<"Enter the value of N"<<"\n";
            cin>>n;
            chess_block **Chess_Board=NULL;
            Chess_Board=PrepareTheChessBoard(n);
            if(Chess_Board == NULL)
            {
                return 0;

            }
            ArrangeQueensOnBoard(Chess_Board,n);
            PrintPositionsOfQueens(Chess_Board,n);
            DestroyTheChessBoard(Chess_Board,n);
            Chess_Board=NULL;
        } 

        return 0;
    }

Answer 1

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 <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;
}

Answer 2

Your second for(int nColumn... is decrementing nColumn inside the loop. That opens you up to infinite loops. If you print out the board positions being tried in that loop, you should be able to see the repetition and figure it out from there.

Answer 3

I commented, but here's my observations of your code:

It's more efficient to represent the board as an array of N ints, where B[i] is the location of the queen in the i'th column. This naturally excludes the case where there's two queens in the same column.

Backtracking is often best done using a recursive algorithm, otherwise you end up coding up your own stack to record the search history.

Poor spelling, and huge functions make it difficult for others to understand your code. Perhaps they make them harder for you to debug too? Smaller functions also let you test parts of your code individually when you suspect that something is broken.

Stick to features from either C or C++ and try to avoid mixing the two (malloc from C, struct constructors, bool type and cin/cout from C++). Try to avoid Windows-specific code when it's not necessary and instead stick to standard C or C++ (_tmain, stdafx).

Answer 4

I'm not sure this is what you are looking for, but there is an explicit solution to the n queens problem :) It's due to a paper I can't quite seem to find anymore.

Anyway, here is an implementation of the explicit solution. It returns a list of integers representing the positions of the queens (one on each row):

std::vector<int> solve(int n) {
    std::vector<int> result;
    if (n == 1) {
        result.push_back(1);
        return result;
    }
    if (n < 4) {
        // Impossible, return empty vector.
        return result;
    }

    if (n % 2 == 0) {
        // Explicit solution according to paper.
        if (n % 6 == 2) {
            for (int j = 1; j <= n/2; j++) {
                result.push_back(1 + ((2 * (j-1) + n/2 - 1) % n));
            }
            for (int j = n/2; j > 0; j--) {
                result.push_back(n - ((2*(j-1) + n/2 - 1) % n));
            }
        }
        else {
            for (int j = 1; j <= n/2; j++) {
                result.push_back(2 * j);
            }
            for (int j = 1; j <= n/2; j++) {
                result.push_back(2 * j - 1);
            }
        }
    }
    else {
        // If odd, place in corner and solve even.
        result = solve(n - 1);
        result.push_back(n);
    }

    return result;  
}

Answer 5

I can confirm your program DO work for 30, but take a lot of time. Please be patient in waiting the results. (I didn't check the validity of the result).

The complexity of this kind of algorithm is exponential (or maybe over exponential). That means the time consumed would easily reach the tolerance of the user.

Besides the suggestions by others, in C++, you'd better use new instead of malloc, which will call the constructor. And you can use std::vector instead of raw pointer.

btw, I/O like printing to screen will take A LOT OF time (much more than your real algorithm in your code). Don't print that often even when you are debugging.

Answer 6

N Queens has a O(n) deterministic solution, which was published in a 1969 edition of Mathematics Magazine by Hoffman, Loessi, and Moore. Here is a link to an applet (www.apl.jhu.edu/~hall/java/NQueens.java) that implements a later version of the same approach. In 2001, I had a student in one of my classes solve the 10,000,000 Queens problem in about one minute on a PC of that era (300MHz Pentium II).