The N Queens Problem

The N Queens Problem is a very famous mathematics and computer alogorithm problem.

Abstract

It is derived from the 8 queens problem, where the aim is to find the possible ways to place 8 queens on a chessboard so that no queen would attack any other queen. Alternatively, it can also be said that the aim is to palce 8 queens on a 8 times 8 grid so that none of the queens share a common row, column or diagonal.

History

This problem was originally propsed in 1848 by the chess player Max Bazzel, and many mathematicians (like Guass) have worked on these problems over the years. Even better... this problem appeared in an early computer program called The 7th Guest.

Solutions

So instead of 8 queens, consider N queens on a N times N size chessboard (i.e. N times N boxes in a grid)

There are actually many ways to derive the solutions. The trick is to draw a diagonal line. This website offers some interesting insight on getting solutions if someone ever asks you for one.

So why am I talking about this now? The reason is because I spent one whole week trying to figure out a fast algorithm to get the solutions. Apparently, this problem can be coded with simple recursion and brute force alogrithm. And I finally got the time limit under 1 second for N = 13... when I declared char (character) instead of int (integer)!

My solution in c++ is here.

Some interesting statistics: (Note: unique solutions means we disallow rotations/reflections)

Order     < --- Ordinary Queens   --- >    
('N')    Total Solutions   Unique Solutions 
--------------------------------------------
1                      1                  1
2                      0                  0
3                      0                  0
4                      2                  1
5                     10                  2  
6                      4                  1 
7                     40                  6 
8                     92                 12  
9                    352                 46
10                   724                 92
11                 2,680                341
12                14,200              1,787
13                73,712              9,233
14               365,596             45,752
15             2,279,184            285,053 
16            14,772,512          1,846,955    
17            95,815,104         11,977,939 
18           666,090,624         83,263,591
19         4,968,057,848        621,012,754  
20        39,029,188,884      4,878,666,808
21       314,666,222,712     39,333,324,973 
22     2,691,008,701,644    336,376,244,042
23    24,233,937,684,440  3,029,242,658,210

For the mathematics part of it, consider the article on mathworld.