9
$\begingroup$

Two possible moves from A

You are doing a knight's tour, but this time, it's on the surface of a cube with chessboard faces.

If you move to a square on the same face you started, everything works just like on a normal chessboard. You can go to neighbour face by crossing the edge between the two faces, but move like both the starting and end face were on one plane. This is how you would get from A to B in the picture. You can also cross two edges, then the knight would travel from A, over the face B is on (while imagining A's and B's faces were in a plane) and then over to C (while imagining B's and C's faces were on the same plane. I hope I described it well enough so you can see how the knight still does its characteristic "2squares in one direction, 1 square perpendicular to that direction" move.

Note that if you only cross one edge, the color of the square does not change. Just ignore that and the color of the squares, this is all about hitting them exactly once.

1) Is it possible to do a knight's tour on a cube with chess faces?

2) If yes, what is the smallest cube you can do it on with edge length > 1?

3) What about open and closed tours?

Improve this question
$\endgroup$
7
  • $\begingroup$ But you can not go from $B$ to $C$, they are on 2 squares in one direction and there is not 1 square perpendicular to that direction. $\endgroup$
    – Seyed
    Dec 14, 2017 at 17:53
  • $\begingroup$ Exactly. What I tried to describe was the way from A to C, over the face B is on. $\endgroup$
    – Tweakimp
    Dec 14, 2017 at 17:55
  • 2
    $\begingroup$ When on a cube, the exact definition of the knight's move is surprisingly important. There are squares that cannot be reached by "2 squares in one direction, and then 1 in a perpendicular direction", but can be reached by "1 square in one direction and then 2 in a perpendicular direction". For example, the white square on B-side's edge towards A fits the bill, if you try to reach it from A. This distinction does not exist on a 2D board, so we cannot borrow a sensible definition from chess. $\endgroup$
    – Bass
    Dec 14, 2017 at 18:00
  • $\begingroup$ @Bass I think you go me wrong. When moving, imagine the faces you move over in one plane, as if the edge wasnt there. With "perpendicular" I always meant "perpendicular to the direction but still on the same plane". It's a bit difficult to talk about that in 3D $\endgroup$
    – Tweakimp
    Dec 14, 2017 at 18:07
  • 2
    $\begingroup$ I'd lean towards allowing both orders being allowed: otherwise we lose the symmetric property of the knight's move; there could be strictly one-directional routes between a pair of squares. That goes against my intuition of the knight's move, but that's probably personal; a xiangqi player might be more accustomed to the idea of a knight threatening another knight, and not being threatened back. Of course, since we're on PSE, we would do well to pick the rule that makes for a better puzzle. So it's only a matter of deciding which one does :-) $\endgroup$
    – Bass
    Dec 14, 2017 at 18:29

4 Answers 4

Reset to default
6
$\begingroup$

2x2x2 is easily solved like this:

Split the cube into three pieces of two adjacent sides. Solve each piece independently like this: 

       1   7 | 4  8 
       3   5 | 2  6
Then repeat for the other pieces, which are trivially reachable from 8. This solution only uses "first 2, then 1" type moves.

Behold my mighty Gimp skillz:

(Moves happening entirely within the piece being solved were omitted to preserve what little clarity there is left.)
enter image description here
From 8, it's possible to reach 3 different squares on either of the rear sides, so even a closed loop shouldn't pose any problem. Here's an example: enter image description here
What the image above is trying to represent is the fact that the pattern in the upper picture (or its mirror image, if needed) completely fills two sides, starting from a square on the far edge of the piece, and ending at the lengthwise opposite square. Confirming that the jumps B-C, D-E and F-A are indeed valid knight moves is therefore enough to prove that the three pieces can indeed be connected to form a loop.

For the general case of a $N^3$ cube,

The problem is similar to the regular knight's tour on a chessboard, and can be solved similarly, by considering each square a vertex in a graph, and each possible move as an edge. In the cube version's graph, there are always 8 inbound and 8 outbound edges at each vertex. The incoming and outgoing edges are not always coincident with each other. (As long as we only allow "first 2, then 1" type of moves. See my comments on the question itself). The problem of finding a Hamilton circuit for a given graph is NP-complete, so a brute force approach isn't likely to help us. Having solved dozens of knight's tour problems by hand though, experience tells that both the high edge count and having distinct entry and exit edges should make it comparatively easier to find a Hamiltonian cycle for the graph.

On the regular, 8x8 two-dimensional board, the vertices representing the corners only have 2 non-directional edges connected to them, and only 16 of the 64 squares have the full 8 edges, but even then, a Hamiltonian cycle exists.

Since there is nothing making the problem intrinsically more difficult in the 3D version, and the "lack of corners" actually makes it much easier, it stands to reason that a closed loop will always exist for a cube of any size.

Rigorous proof for the above claim will have to be supplied by someone more proficient in graph theory, I'm afraid.

Improve this answer
$\endgroup$
1
$\begingroup$

Partial answer here:

  1. Yes
  2. You can do it on a 1x1 cube - from any position, the knight can reach every face except the face it started on and the opposite face. Then it's just a matter of walking around the cube by choosing the appropriate path.
  3. This can be made either a closed or open tour (closed: 1, 3, 6, 5, 4, 2, 1open: 1, 3, 2, 4, 5, 6)

I haven't yet evaluated whether it's possible on larger cubes however.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Ah, I didnt think of the "trivial" n=1 solution...Good job though. $\endgroup$
    – Tweakimp
    Dec 14, 2017 at 17:29
1
$\begingroup$

If we ignore the colours of the titles then I managed to get it to work for a 3 x 3 x 3 cube:

A 3x3 solution

The outer squares are reflections of the hidden side that's closest to them

Sadly, I couldn't make it a closed tour.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Great! Now do it on a 2x2x2 :p $\endgroup$
    – Tweakimp
    Dec 14, 2017 at 18:45
0
$\begingroup$

EDIT: Argh! In my hubris, I forgot about the condition for lengths X and Y not both being odd, which would appear to preclude any odd unit size cube...

BUT, I think we can work around this; after all the set of 6 N by N squares around the cube can be reinterpreted as a set of 3 N by 2N rectangles (each wrapping around two faces apiece), which IS solvable.

This suggests that even if we have an odd dimension cube, the extra faces added by the 3 dimensions removes that condition for success. (Conceptionally, i'd guess any N unit cube is equivalent in solvability a N by 6N rectangle for solvability, even if the actual solution we end up with wouldn't work when 'wrapped around a cube'; and since 6 is even, any unit length counted across six faces is also even, and thus solvable)

===========================================================================

ORIGINAL POST:

Building on the previous answers, not a rigorous proof but an attempt at a logical one:

  • each side of the cube is an N x N 2d knights tour; thus we can solve each face as long as it meets the normal rules (which are simplified because theyre always square in dimension)
  • We can step off one board on to the next at any point which is within a knights move of the edge. Of course a knights tour covers every square, so we can pick any arbitrary edge square to transition, and any square we reach can be a starting point.
  • Because we can traverse the 6 faces of a cube in a single loop, we can chain the solutions for the faces, either visiting each face once (A » B » C » D » E » F), or more likely twice (A » B » C » D » E » F » E » D » C » B » A)

  • (I'm at work and can't draw a nice diagram, but conceptually similar to solving a 'draw a figure in a continuous line puzzle - solve each shell once, dipping into the next shell at the last opportunity, before returning to the upper shell to complete it; recurse as needed; e.g. as below)

    enter image description here

  • From the above, this means we can solve any puzzle with a cube size thats not 1, 2, or 4 - EXCEPT the other answers have solved cube size 1 and 2 already!

Thus all we're looking for is a solution of 4 unit sizes and we've covered all the special cases!

Improve this answer
$\endgroup$

Your Answer

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

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