Skip to: 
LyndenleaThe n Queens Problem
Where mathematics and logic meet over a friendly board game.
I blame my Dad, Colin, for this. Since he first started writing computer programs way back in 1975 he's been intrigued by the age-old Eight Queens Puzzle of how to get eight chess Queens onto a standard 64-square (8×8) chessboard such that no Queen can attack any other using the standard chess Queen's moves. Put simply, no two Queens may share the same horizontal row, vertical column, or diagonal.
Actually, that wasn't enough for my Dad. He'd also been extending that puzzle onto different sized "chessboards", both bigger and smaller (but always square), hunting for solutions to the more general n Queens problem of placing n non-attacking Queens on an n×n chessboard. Dad later began focusing on finding just the first possible solution to the problem for the various sizes of chessboard – and then I caught the bug too (darn it).
What's more, neither of us actually plays chess!
We used a very simple algorithm to identify the first possible solution to the problem on any size of chessboard. It's essentially trial-and-error, taking each row of squares at a time and placing a Queen to see if it's safe. However, while Dad's original algorithm would search all the preceding rows for attacking Queens each time he tried to place a new Queen, I developed my own variation that marked "at-risk" squares in advance, so that any newly-placed Queen only needed to consult a look-up table to see if she could safely occupy a new square. The iteration through the other rows of the chessboard was thus reduced from happening every time a Queen was placed, to only happening when a Queen was safely placed. From then on, it was this more efficient variation that we used when Seeking the First Solution.
Having found all these solutions, we then needed a way of keeping track of them so we came up with this even simpler notation for Describing Solutions. I've used this notation in my list of The First Solutions, and each solution also has a link to a chessboard diagram. Also given is the number of Queens placed on each size of chessboard whilst seeking that first solution, an interesting by-product of our algorithm.
Whilst we had no particular upper limit of chessboard size in mind for our research, it eventually became clear that the problem was becoming too big for the processing power we had available to us, and that more efficient algorithms would produce the first solutions for larger chessboards more quickly, albeit at the expense of counting the numbers of Queens placed throughout an exhaustive search such as ours. The first such example was the 46×46 chessboard, for which the first solution was offered to us whilst our program was taking a surprisingly long time over it (after we'd already discovered the first solutions for some larger chessboards in shorter periods). I therefore wondered just how far off our program was from achieving the same result, and My Estimate for 46×46 reveals my surprising conclusions.
Another extension that Dad has always been keen to investigate is how to take the problem Beyond Two Dimensions – specifically, to find out how many Queens you could get into a three-dimensional n×n×n (or n³) "chess-cube". My ability to mentally picture and manipulate such things not only helped us to come up with an ingenius way of finding solutions to the 3D problem, but also inspired me to delve even further into the fourth dimension and beyond.
Take a look at Dad's own CSP Queens website to read his thoughts on our investigations into this problem. Amongst his Counting N-Queen Puzzle Queen-placements pages he offers a free, downloadable "demo" program that you can use to generate some of our results yourself. It employs the same algorithm as the program he uses to find new solutions, but it's limited to chessboard sizes only up to 32×32.