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.
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:
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. 🙂
Thank you very much!