CSP Queens - Analysis Of The N-Queens Puzzle

On Our Adventures In 2 and 3 Dimensions
With The N-Queens On An N x N (x N) Chessboard Puzzle

N-Queens In 2-Dimensions

Here I stake my claim to being the first person to find the guaranteed, algorithmically first-possible solutions (in other words, not the only solutions) for most of the larger boards in this puzzle, up to 49 x 49 squares, and I explain the basis of my claim in detail.

I show the exact queen arrangements for each of these first possible solutions, and I invite you to muse with me on their fascinating lack of predictability.

Click the chessboard on the right for my original notes on this 2-dimensional puzzle.

N-Queens In 3-Dimensions

I've been working with my son Martin and his younger sharper intellect to extend this puzzle into the 3rd Dimension (3D). We use the word 'cube' to mean an N-high stack of notional N x N chessboards, and a key feature of these 3D cube solutions is that they are maximally populated. They're maximally populated because under the rules of this puzzle, no additional queens can be placed anywhere inside the cubes.

I've written our main solution-search program in C++, and Martin writes PHP programs for his interim searches and analyses, but I've used the free and versatile JavaView Lite utility here to show you three interactive solutions for the following cubes:

A. The 11 x 11 x 11 ( or 11³ ) cube B. The 13³ cube and C. The 31³ cube.
Click on the cube on the right to see these 3-Dimensional solutions.

Our search time for the 31³ and larger cubes is significantly reduced thanks to some impressive algorithm optimisations by Martin.

Catalytic Conversations On N-Queens

I've written here about some of the programmer's catalytic conversations that Martin and I shared on this project, and on some of our developmental roller-coaster rides as we nudged our algorithm into its current state.

My son Martin has his own series of websites
including two sections on this N-Queens puzzle

Click the board on the right to visit Martin's 2D related Queens On A Chessboard web site, where he describes his work on this puzzle and offers his own insights into its solutions.

His explanations are crystal clear, and they include a full board diagram for each of the 2D First Possible Solutions that have now been solved.

The boards and their solutions are beautifully rendered using 100% hand-crafted PHP and html!

Martin's most recent work takes us up "Beyond The 2nd Dimension" into fully populated solutions to the 11x11x11 ( or 11³ ) cube, the 13³ cube, and now - remarkably - the 35³ cube and the 37³ cube!

As he examines progressively larger cubes, he maintains a daily updated counter showing the extent of his current search.

Martin explains why some cubes will never yield any fully populated solutions, and he invites us to consider possible solutions for 4 dimensional or even higher-dimensional 'boards'!

Links to other related sites

OEIS From our calculations while solving the 2D puzzle, we've had two integer sequences accepted into
The On-Line Encyclopedia of Integer Sequences ...

Our count of Tentative Queen Placements (See A140450)

Our list of First Possible Solutions (See A141843)

Matthias R. Engelhardt has been intrigued by this puzzle for as many years as myself! His studies of the many enigmas in this puzzle have been wider than both mine and Martin's, and he has brought significant mathematical prowess to his solution searches, particularly on torus-related aspects of the puzzle. He recently adapted his torus-based search to focus on this "First Solution" search, and - to our delight and applause - he rapidly uncovered the First Solution to the very tough 46 x 46 board! The little icon to the left is a miniature of Matthias's own picture of his 46 x 46 solution, and I say a little more on my Table Of First-Solutions page about our happy co-operation with Matthias.

I recommend a visit to Walter Kosters' N-Queens bibliography.
His list of references shows the huge variety of contexts from which this N-Queens puzzle has been studied, from as long ago as the mid-19th Century!

I hope you've enjoyed reading about our work on the N-Queens puzzle.
You will find a wealth of further information about this puzzle, especially in its original form as
The 8 Queens Puzzle, on a dedicated page on
Wikipedia, The Free Encyclopedia.

Credits And Acknowledgements

The web-integration and display of our 3D N-Queens solutions is possible
thanks to the JavaView Lite 3D geometry viewer by Konrad Polthier

Thanks for these free .GIF images goes to -
UVic Humanities Computing and Media Centre
and their associates at Half-Baked Software

Other chess-board and cube images on this CSP Queens site
are copyright © Colin S Pearson and
copyright © Martin S Pearson

Contact:

You may contact me via this feedback page, although I can't promise to respond to every message or question.

Page updated: 26th January 2012

Content on this CSP Queens site by Colin S Pearson and Martin S Pearson is licensed under a
Creative Commons Attribution-Non-Commercial-Share Alike 2.0 UK: England & Wales License.
Permissions beyond the scope of this license may be available via the feedback page.

Credits And Acknowledgements
	The web-integration and display of our 3D N-Queens solutions is possible thanks to the JavaView Lite 3D geometry viewer by Konrad Polthier
	Thanks for these free .GIF images goes to - UVic Humanities Computing and Media Centre and their associates at Half-Baked Software
	Other chess-board and cube images on this CSP Queens site are copyright © Colin S Pearson and copyright © Martin S Pearson

N-Queens In 2-Dimensions Here I stake my claim to being the first person to find the guaranteed, algorithmically first-possible solutions (in other words, not the only solutions) for most of the larger boards in this puzzle, up to 49 x 49 squares, and I explain the basis of my claim in detail. I show the exact queen arrangements for each of these first possible solutions, and I invite you to muse with me on their fascinating lack of predictability. Click the chessboard on the right for my original notes on this 2-dimensional puzzle.
N-Queens In 3-Dimensions I've been working with my son Martin and his younger sharper intellect to extend this puzzle into the 3rd Dimension (3D). We use the word 'cube' to mean an N-high stack of notional N x N chessboards, and a key feature of these 3D cube solutions is that they are maximally populated. They're maximally populated because under the rules of this puzzle, no additional queens can be placed anywhere inside the cubes. I've written our main solution-search program in C++, and Martin writes PHP programs for his interim searches and analyses, but I've used the free and versatile JavaView Lite utility here to show you three interactive solutions for the following cubes: A. The 11 x 11 x 11 ( or 11³ ) cube B. The 13³ cube and C. The 31³ cube. Click on the cube on the right to see these 3-Dimensional solutions. Our search time for the 31³ and larger cubes is significantly reduced thanks to some impressive algorithm optimisations by Martin.
Catalytic Conversations On N-Queens I've written here about some of the programmer's catalytic conversations that Martin and I shared on this project, and on some of our developmental roller-coaster rides as we nudged our algorithm into its current state.

My son Martin has his own series of websites including two sections on this N-Queens puzzle
Click the board on the right to visit Martin's 2D related Queens On A Chessboard web site, where he describes his work on this puzzle and offers his own insights into its solutions. His explanations are crystal clear, and they include a full board diagram for each of the 2D First Possible Solutions that have now been solved. The boards and their solutions are beautifully rendered using 100% hand-crafted PHP and html!
Martin's most recent work takes us up "Beyond The 2nd Dimension" into fully populated solutions to the 11x11x11 ( or 11³ ) cube, the 13³ cube, and now - remarkably - the 35³ cube and the 37³ cube! As he examines progressively larger cubes, he maintains a daily updated counter showing the extent of his current search. Martin explains why some cubes will never yield any fully populated solutions, and he invites us to consider possible solutions for 4 dimensional or even higher-dimensional 'boards'!

Links to other related sites
OEIS	From our calculations while solving the 2D puzzle, we've had two integer sequences accepted into The On-Line Encyclopedia of Integer Sequences ... Our count of Tentative Queen Placements (See A140450) Our list of First Possible Solutions (See A141843)
	Matthias R. Engelhardt has been intrigued by this puzzle for as many years as myself! His studies of the many enigmas in this puzzle have been wider than both mine and Martin's, and he has brought significant mathematical prowess to his solution searches, particularly on torus-related aspects of the puzzle. He recently adapted his torus-based search to focus on this "First Solution" search, and - to our delight and applause - he rapidly uncovered the First Solution to the very tough 46 x 46 board! The little icon to the left is a miniature of Matthias's own picture of his 46 x 46 solution, and I say a little more on my Table Of First-Solutions page about our happy co-operation with Matthias.
	I recommend a visit to Walter Kosters' N-Queens bibliography. His list of references shows the huge variety of contexts from which this N-Queens puzzle has been studied, from as long ago as the mid-19th Century!
	I hope you've enjoyed reading about our work on the N-Queens puzzle. You will find a wealth of further information about this puzzle, especially in its original form as The 8 Queens Puzzle, on a dedicated page on Wikipedia, The Free Encyclopedia.

On Our Adventures In 2 and 3 Dimensions With The N-Queens On An N x N (x N) Chessboard Puzzle

On Our Adventures In 2 and 3 Dimensions
With The N-Queens On An N x N (x N) Chessboard Puzzle