N-Queens Problem Solution With C++


The first meeting I attended at the DePaul University Computer Science Society was all about problem solving. Using one’s programming knowledge to solve some difficult problems programmatically which would be very tedious to solve otherwise, is a skill that is very important to acquire for any programming student. In the end, that’s what programming is all about solving problems, not only correctly, but also, efficiently.

One of the problems we were discussing, was the 8-Queens problem, Which, in order to solve it, you must know where to place your 8 queens on an 8 by 8 chess board, so that they won’t attack each other. This implies that you cannot place two queens on the same row, column, or diagonal.

8 Queens Problem

8 Queens Problem

Afterwards, we started discussing the solution to the more general problem, which is to place any number of queens, say N queens, on N x N chess board. My colleagues at the society, being much more experienced than I am, were able to write solutions to this problem recursively, using Python, or Haskell. I chose to write an iterative solution in C++.

My solution is quite simple. The lower part of the above picture shows a sample output when running the program like this on Linux:

./nqueens 8

Where 8 is the size of your chess board. The numbers in the output are the rows indexes where you should place your queens per each column.

The code implements the method I would follow if I would solve the problem manually by hand. I fill the queens column by column, until I reach a column in which I can’t find a valid place for the queen. At that point I backtrack, going back to the previous column, and change the position of my queen there to the next valid row in that column. If not found, I backtrack more, if found, I go forward and try to fill the rest of the columns.

Please take a look at my code, and feel free to ask any questions. May be if you have suggestions to better improve this solution, I would be also thankful. 🙂

N-Queens Problem Solution in C++ by Ahmed Fakhry

Thank you very much!

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s