Beyond Two Dimensions
You can get n Queens onto an n×n chessboard, so how many Queens can you fit into an n×n×n "chess-cube"? That's the question my Dad, Colin first pondered when he proposed this extension to the old problem. Also, where do you start? Our two-dimensional investigations took each row in turn, with each Queen progressing along its row until it found a safe column. But in a cube there's a third dimension – layers – which could only serve to complicate matters.
After a little thought, I wondered whether we were asking the wrong question. Instead of trying to fit as many Queens as possible into this cube, why not aim for n×n Queens? After all, we'd increased the available squares – or perhaps more accurately now, cells – by a power of one (from n² to n³), so surely it made sense to increase the number of Queens in the same way (i.e. from n¹ to n²). And as it turned out, that gave us a remarkably simple method of Searching for 3D Solutions.
Our investigations didn't look promising to begin with. Cube after cube simply refused to reveal any solutions at all, leaving us wondering if we'd ever find any, and whether perhaps we should have stuck with cramming in as many Queens as possible. But we persevered, until finally one cube presented us with more than two hundred solutions! Which left just one question: how do we keep track of them all? So just like with our two-dimensional solutions, we devised a simple but effective notation for Describing 3D Solutions.
The 3D Solutions So Far page reveals the total number of solutions found in each cube we've searched, and I also explain how Taking a Shortcut allowed me to generate at least some of the many solutions in even bigger cubes based on those we've already found.
All of which got me thinking – if there are solutions to the puzzle in two dimensions, and in three dimensions, what about FOUR dimensions? Or even more? My incredible brain sprang into action once more, and I found myself embarking on a strange but fascinating journey into The Fourth Dimension.
Dad's own pages On The 3-Dimensional N-Queens Puzzle offer a fascinating insight into the mind of the programmer, and include fully-interactive Java models of the first possible 11³ and 13³ cube solutions.
And for just one example of the earlier research on this subject take a look at Three Dimensional Queens Problems by Lloyd Allison, Chut N Yee and M McGaughey of Monash University in Australia which was published as long ago as 15th November 1988.