On Our Adventures In
2 and 3
With The N-Queens On An N x N (x N) Chessboard Puzzle
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
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.
the chessboard on the right for my original
on this 2-dimensional puzzle.
I've been working
with my son Martin and his younger sharper intellect to extend this
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.
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:
The 11 x 11 x 11
) cube B.
cube and C.
the cube on the right to see these 3-Dimensional
Our search time for the 313 and larger cubes is significantly reduced
thanks to some impressive algorithm
optimisations by Martin.
Catalytic Conversations On N-Queens
written here about some of the programmer's
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.
son Martin has his own series of websites
including two sections on this N-Queens puzzle
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.
explanations are crystal clear, and they include a full board
diagram for each of the 2D First
Solutions that have now been solved.
The boards and their solutions are beautifully rendered using 100%
hand-crafted PHP and html!
most recent work takes us up "Beyond
The 2nd Dimension" into fully populated solutions to the
11x11x11 ( or 113
) cube, the 133 cube, and now - remarkably - the 353
cube and the 373 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'!
to other related sites
calculations while solving the 2D
puzzle, we've had two integer sequences accepted into
Encyclopedia of Integer Sequences
|| 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
our happy co-operation with Matthias.
||I recommend a visit to Walter Kosters' N-Queens
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!
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
The Free Encyclopedia.
web-integration and display of our 3D N-Queens solutions
thanks to the JavaView
Lite 3D geometry viewer
for these free .GIF images goes to -
Humanities Computing and Media Centre
and their associates at Half-Baked Software
chess-board and cube images on this CSP Queens site
are copyright © Colin S Pearson and
copyright © Martin S Pearson
- You may contact me via this feedback
can't promise to respond to every message or question.
updated: 26th January 2012