N-Queens Puzzle

This is my solution to the famous 8-Queens Puzzle (and more general N-Queens Puzzle).  “So, what’s the 8-Queens Puzzle?”  you say. “Good question!” I say.  Wikipedia has a ton of information about this and summarizes as follows:

“The eight queens puzzle is the problem of placing eight chess queens on an 8×8 chessboard so that no two queens attack each other. Thus, a solution requires that no two queens share the same row, column, or diagonal. The eight queens puzzle is an example of the more general n-queens problem of placing n queens on an n×n chessboard, where solutions exist for all natural numbers n with the exception of 2 and 3″

Solutions to N-Queens Puzzles

In the program below, solutions are outputted to the text file in the following form:

 

For the 8-Queen Puzzle, the program will export all 92 solutions to the “8-Queen.txt” file almost instantaneously.  The file itself will occupy 56kb (58,503 bytes) of disk space.  For the 14-Queen Puzzle, all solutions are exported in roughly 3 minutes. That’s pretty quick considering that there are 365,596 distinct solutions and the file size required to represent them is a whopping 612mb (642,241,067 bytes)!

 

Initially, my solution relied on recursion and was similar to others you may find online. Recursive approaches to this problem are intuitive, but they tend to be slow and will result in stack overflow errors when N is large.  For these reasons my current algorithm avoids recursion altogether.  The C++ code is heavily commented but if you need clarification about how it works, feel free to leave me a comment below.

 

 

Leave a Reply

You are allowed to enter 1 URL(s) in the comment area.

3 × 2 =