6
$\begingroup$

The basis of this puzzle, is based on a common 2D chess puzzle, where you try to fit 8 queens on a chessboard without the queens being able to attack each other.

Extend this concept into a 3D cube (8x8x8... like 8 chess boards on each other), but we do analysis on both vertical and horizontal planes. So no queen can attack each other in any vertical plane or in any horizontal plane.

What is the maximum number of queens can you fit into this chess cube without them being able to attack each other. (To describe your solution, feel free to post an image showing each layer in order, or illustrate it with text of x's and o's)

Improve this question
$\endgroup$
8
  • 1
    $\begingroup$ An automated search shows that it is possible to put 16 queens on an 8x8x2, but it is not possible to put 32 queens on an 8x8x4. $\endgroup$
    – f''
    Commented Oct 3, 2015 at 2:26
  • $\begingroup$ en.m.wikipedia.org/wiki/Eight_queens_puzzle shows 92 possible solutions for the 8x8. If you tried all combinations of these in the 8x8x4 and they didn't work then that is very useful info ;) $\endgroup$
    – VenomFangs
    Commented Oct 3, 2015 at 3:47
  • $\begingroup$ It's important to cut the cube in both vertical directions for the testing. So you cut the planes in the direction of each axis. $\endgroup$
    – VenomFangs
    Commented Oct 3, 2015 at 3:48
  • $\begingroup$ Possible variation (maybe as a next question?) would be to see how many queens you can put on 6 8x8 fields on the outside of a cube. $\endgroup$
    – Tim Couwelier
    Commented Oct 3, 2015 at 5:17
  • $\begingroup$ Unless the outside affect each other then it is 48 as you can fit 8 in each side $\endgroup$
    – VenomFangs
    Commented Oct 5, 2015 at 0:52

1 Answer 1

Reset to default
4
$\begingroup$

The maximum I've been able to find is 50.

I started off trying to get solutions by stacking various arrangements of the eight-queen solutions and filling in the leftover spaces optimally, but realized that to be a dreadfully inefficient (and far from optimal) exercise, and instead came up with a fairly straightforward recursive backtracking algorithm to populate an optimal cube.

So anyways, here's my solution:

Layer 1:

Layer 1

Layer 2:

Layer 2

Layer 3:

Layer 3

Layer 4:

Layer 4

Layer 5:

Layer 5

Layer 6:

Layer 6

Layer 7:

Layer 7

Layer 8:

Layer 8

If the pattern isn't clear, here's what the solution would look like from a "top-down" view through all eight layers. Neat stuff.

All together, now

Improve this answer
$\endgroup$
3
  • $\begingroup$ Can Queens only move in two directions in 3D space? Because from layer 1 to layer 2, it looks like L1B1 attacks L2A2 along a diagonal. If this isn't a valid move, I am curious as to why. $\endgroup$
    – question_asker
    Commented Nov 20, 2015 at 14:08
  • 1
    $\begingroup$ The way I interpreted the question, that kind of movement is not possible. I essentially divided the cube into 24 planes (8 planes along each axis) and evaluated each of those planes. So, L1B1 does not share any planes with L2A2, so the two do not interfere with each other. $\endgroup$
    – Steve Eckert
    Commented Nov 20, 2015 at 14:19
  • $\begingroup$ Suppose to consider the 1 horizontal cut and the 2 possible vertical cuts. Gives a total of 24 chess boards to check for validation after placing the Queens. Showing the 8 layers, gives enough info the figure out the rest $\endgroup$
    – VenomFangs
    Commented Nov 20, 2015 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.