The alien quantum-tunnelling hyperking labyrinth escape

Great title, right? Don't worry, I'll explain it.

Here is the story.

The inhabitants of planet Nuri have captured their arch-enemy, the hyperking of a neighboring planet (thus "alien").

They plan to confine him in a labyrinth built out of stone blocks placed on a square grid. They want to take advantage of the curious particularity of how the hyperking can and cannot move. The idea is to prevent him to escape while allowing the Nurians free access to him.

A hyperking moves like a king in chess, except that he moves twice as far (thus "hyper-"). He moves exactly 2 cells in either of the 8 directions. He cannot do otherwise. The spooky thing is that he can do so unhindered by walls, he can tunnel thru solid stone (thus "quantum-tunnelling"). Only the destination cell must be empty.

Unfortunately, Nurian architecture and building technology mandates the following constraints. (Nurikabe-like).

• No 4 blocks in a 2x2 square can all be occupied by rocks. The ground would collapse.
• No 4 blocks in a 2x2 square can all be empty. The ceiling would collapse.
• A solid wall must run around the labyrinth.
• All stone blocks must be connected orthogonally.
• All free cells must form a single orthogonally connected space.

There is a staircase leading down into the labyrinth at each of the 4 corners. The hyperking prison cell connects to the upper left corner. The labyrinth must be designed to prevent the hyperking to move to any other corner of the labyrinth.

Below is a floor plan which fails to prevent the hyperking from escaping. As a warm-up, can you find the path the hyperking can take from the upper left corner to reach another corner?

Your mission now is to fix the labyrinth. Adjust the labyrinth or design a completely new labyrinth on a 19x19 grid, that respects the architectural constraints and prevents the hyperking to travel from his corner to any other corner.

If necessary, you can choose a different size for your labyrinth as long as you have 4 distinct corners inside of the outer wall.

If you think it is impossible, explain why it is so.

Note

• Yes, the hyperking's movement restrictions imply that he can move only to even rows and columns. Or odd rows and columns if you count rows and columns from zero.
• No, the hyperking cannot hyperjump outside of the outer wall. The labyrinth will be built underground, there is compact dirt all around.
• Yes the Nurians could move the exit staircases just one block in either direction to put it out of reach from the hyperking, but no Nurian would accept to build such a horror. Staricases belong to the corners. They have always been there and always will be.
• This is my own creation. The characters and events described in this puzzle are entirely fictious. Any similarity to actual people or incidents is entirely coincidental. No hyperking was harmed in the making of this puzzle.
• "If necessary, you can choose a different size for your labyrinth." Cool, I choose 2×2! (I assume the "different size" must be odd × odd?)
– Deusovi
Jun 18 at 0:21
• Nice try, but either you count the external wall and you have a 2x2 square that is solid stone, or you count only the inner space and you have a 2x2 square that is empty. Not valid. You can experiment with even x odd or even x even sizes. But show me the completed labyrinth. Jun 18 at 0:28
• But ok, given that they want 4 distinct staircases, the Nurians require at least 4x4 cells, external wall included. Jun 18 at 0:33
• Ah, of course, even×even wouldn't work at all. Oh well, it was worth a shot!
– Deusovi
Jun 18 at 0:42
• This very much looks like a math olympiad problem. Very interesting to solve, thank you. Jun 18 at 1:30

impossible.

Let's call a "point" an intersection of horizontal and vertical lines, i.e. a "corner" of a wall.
The condition on the maze means that, if one starts from any point and travels along the walls, then one can visit all points and return to the starting point. Let's call this loop the "main loop".

We may paint the points black and white in a checkerboard pattern, i.e. two adjacent points are painted different colors. This shows that any loop of points has an even length.

In order that the king cannot escape, there must be a "cage" of rocks that encloses the starting point of the king, something like in the picture below:

It is easy to see that the number of points within the cage (including those on the inner boundary of the cage) is always odd.

Now we consider the part of the main loop within the cage.
If there is a "door", i.e. the main loop enters and exits the cage between two rocks, then we "close the door" by directly going from one side of the door to the other side.

After closing the doors, inside the cage we have several loops that go through all the points. This however is impossible because each loop contains an even number of points, while the cage contains an odd number of points.

Note on the existence of the main loop:

We connect two adjacent points with an edge if there is a wall between them, i.e. the two blocks between them are one rock and one empty.

I claim that every point has degree $$2$$.

If a point has degree $$0$$, then the four blocks near it are all rocks or all empty.
If a point has degree $$4$$, then two diagonal blocks near it are rocks and the other two diagonal blocks are empty. Since some orthogonal path connects the two empty blocks, the path must divide the plane into two connected components, and the two rocks are separated into these two components.

Therefore the graph we get is a union of cycles. There must be only one cycle because the empty/rock blocks are connected.

• Congratulations. I checked your answer and it looks correct. I myself couldn't explain what is the reason that makes this puzzle difficult. Thanks for the insight. Jun 18 at 8:24
• That's indeed a difficult problem. It could be of top level difficulty in a math Olympiad contest. My answer is a bit sketchy and many details are still missing. Jun 18 at 16:04
• Yah. "It is easy to see that ..." and "Obviously ..." are dangerous words in a math proof. On the other side, this isn't MSE. Jun 19 at 10:20

As a warm-up, can you find the path the hyperking can take from the upper left corner to reach another corner?

• wow- the warm-up got 2 upvotes?
– JLee
Jun 18 at 1:35
• @JLee well it's a nice picture, everyone can understand ;) Jun 18 at 10:39
• @AndrewSavinykh True, but it's not an answer or a partial answer
– JLee
Jun 18 at 10:42