Magic Maze Puzzle

Question

_{Inspired by the board game, Magic Maze}

Set-up:

Cut out each 4x4 tile, and the four small tokens (orange, yellow, green and purple), from the provided image below. Place tile 1 on a flat surface with surrounding space, and squares 2-10 in a stack (with 2 on top). Place the four small tokens on the four circles on tile 1. (The large red token and action list are there for your convenience, cut them out and use them to keep track of which action is next if you choose.)

Objective:

Move the four tokens to rest on each of the cells with a triangle at the end of some action, then on each cell with a square (at which point the puzzle is complete).

Rules:

Repeatedly perform the sequence of actions once each in the order given: stairs, north, east, search, south, west (after which comes stairs again, etc.). You must perform each action every time: if you cannot perform such an action, you have failed. Also, you may not move a token over a cell it or another token has previously been on or moved over.

Actions:

North, east, south, west - move any token any positive number of cells in the given direction, relative to the arrow on tile 1. You may not move a token off the tiles, or through a grey wall.

Stairs - move any token from one cell at the end of one staircase to the cell at the other end. The token is not considered to have passed over any cells between these two.

Search - consider any token which lies on a cell with a search icon and is adjacent to free space. Take the next tile from the pile and place it, possibly rotated, so that the arrow points away from the search icon. Note that the arrow does not give a new direction of 'north': north is still relative to the arrow on tile 1, no matter how the tile has been rotated.

Complete the objective, while following the rules for which actions you may take. A full answer should have an image of the final layout with paths taken by each piece, perhaps showing move order and deductions of how to reach that path.

^{Thanks very much to the non-user who helped prettify the board!}

Answer 1

Okay. THAT. WAS. INCREDIBLE!

It took me two solid hours of work to solve and even longer to write and draw it all up here - hopefully it'll be worth it! To start us off, here is the final maze layout and routes:

In the following explanation all colours have been abbreviated to their initials as follows: G=Green, O=Orange, P=Purple, Y=Yellow.

An observation to start:

Recall that the order of moves must always be: STAIRS --> NORTH --> EAST --> SEARCH --> SOUTH --> WEST, then looping back round to STAIRS. As we start with 1 tile down, we have only 9 possible SEARCH actions before we end up in an impossible situation, unable to add another tile. This will happen on Move 58 (after 9 complete move cycles and the first 3 moves of cycle 10). This means all pieces must reach the squares by Move 57 at the very latest.

So, let’s begin... 1 tile:

Another observation: Since (i) either P or Y must take the stairs on Move 1, (ii) every piece must reach a search-space in this room in order to exit it, and (iii) pieces are not allowed to cross paths that they themselves or other pieces have already taken, it can be deduced that the room can be divided into 4 quadrants:


Every piece must leave the room through the exit within their quadrant in this diagram. The crucial move in this cycle will turn out to be Move 3 – which piece should move East? Only two pieces might be able to do so and still head in the direction of their exit: O and P. If O moves East, it will then have to perform the Search action; moreover, it will then be the only piece able to move South, which would move it away from its exit. Thus it must be P that moves East. How? It has to take the stairs first. The first few moves therefore go like this:

Move 1 (STAIRS): P.
Move 2 (NORTH): G (only option).
Move 3 (EAST): P, one space to the search-space.
Move 4 (SEARCH): P, adding tile 2, like so:

2 tiles:

Before Move 5, think: How can we get a piece onto a search-space in 6 moves' time? It won't be Y (need Stairs-West but West comes before Stairs in the next 6 moves) or G (need West-South but South comes before West). It also can't be P (at a minimum, we need South-Stairs-West), so it must be O. How do we get O there? Either by East alone, or by South-East-North. This latter option is not possible due to the sequence of terms, so O will travel East in this run and make no other moves. Now the only piece which can go South in Move 5 is P. We end up with the following:

Move 5 (SOUTH): P, but how many spaces? Not sure yet...
Move 6 (WEST): G (only option).
Move 7 (STAIRS): Either Y or P (if P has moved one or three spaces South).
Move 8 (NORTH): The only piece that could go North is P, but only if it took the stairs in Move 7. Therefore, after Move 8 Y is still on its starting spot and P is in one of three possible spots (since all of these can be reached via the bottom stairs, let's assume for now that that's what P did - we can always correct it later if we need the space back...).
Move 9 (EAST): O (as explained above).
Move 10 (SEARCH): O, adding tile 3, like so:

3 tiles:

Move 11 (SOUTH): G (only option).
Move 12 (WEST): P (only option) - but we still don't know which of 3 spots P is in.
Move 13 (STAIRS): Y (only option).
Move 14 (NORTH): P is the only option, but only if it only went North by just one space in Move 8. Since we must avoid leading P into a dead end, P must now be on the search-space.
Move 15 (EAST): O (only option) - but we cannot be sure yet by how many spaces...
Move 16 (SEARCH): We have two choices: G or P. To work out which, we need to look forward in the tile deck at the entry and exit positions on the remaining tiles. Ultimately we will see that this means we cannot go with P here. Consider: if we place Tile 4 next to P, either G or O needs to get to one of the squares in the bottom row of this tile. The wall along the tile top means that G would need to go around this tile, requiring a 'straight-through' followed by two 'left turns' - this would require the use of Tiles 5, 6 and 7 for G, which will be impossible to achieve since Tile 5 cannot be crossed in one move cycle, given the sequence that the moves must follow. Alternatively, O would need to navigate around the already-placed Tile 2, which would require 'straight through', 'right turn', straight through', right turn' - but from Tile 8 onwards (at which point a 'right turn' would be required), all pieces have 'straight through' structure. Thus in Move 16 we have to search with G, by contradiction. Tile 4 goes on, like so:

4 tiles:

Move 17 (SOUTH): O is the only option - but where is it? In order to end up on the triangle and have a free escape route out of the room when needing to pursue the square afterwards, O must be within the central 4 squares of the room. Why not take the shortest route for now and say it is directly above the triangle - that way we now have O ON ITS TRIANGLE. (We will confirm later whether we were correct to do this - see Move 33...)
Move 18 (WEST): We need a piece on the stairs for the next move - move G West. Which staircase to choose (we have two options)? Well, stopping at the first will result in a dead-end after using them, so bypass those and head three spaces West to the second.
Move 19 (STAIRS): G (only option).
Move 20 (NORTH): G (only option). We're going to need to head towards those stairs in the middle for the next cycle if we want to keep the game alive, so move two or three spaces North (one is not an option, since there is no further North move before the next staircase...).
Move 21 (EAST): G (only option, since O must stay on its triangle until all pieces are on their triangles) - two possible positions still.
Move 22 (SEARCH): P, adding tile 5, like so:

5 tiles:

Move 23 (SOUTH): The only piece which could move South is G, but only if it is currently at the top of its room. This finalises Moves 20 and 21.
Move 24 (WEST): Either Y or P goes West. We need someone on a search-space by the end of this move-set, so move Y.
Move 25 (STAIRS): G (only option).
Move 26 (NORTH): G (only option).
Move 27 (EAST): G (only option).
Move 28 (SEARCH): Y, adding tile 6, like so:

6 tiles:

Move 29 (SOUTH): G (only option) - now ON ITS TRIANGLE.
Move 30 (WEST): P (only option).
Move 31 (STAIRS): P (only option - G must stay on its triangle until all others are in position) - now ON ITS TRIANGLE.
Move 32 (NORTH): Y (only option) - now ON ITS TRIANGLE.

So, if we were correct to move O to its triangle in Move 17, we have at this point successfully positioned all counters on their triangles - halfway there! Now to get to those pesky squares... (Note that we can now confirm that we were correct to move O to its triangle in Move 17 - for Move 34 we will need to have a piece on a search-space; since Move 33 is a move East, the only piece that can successfully move East from their triangle to a search-space is O. If in Move 17 we had instead moved O South to the space one to the left of its triangle, Move 33 would need to be used to get it onto its triangle, no piece would then be on a search-space just before Move 34 and our strategy would collapse altogether. Therefore, our Move 17 above is the correct choice...).

Move 33 (EAST): O (only option, since we need to reach a search-square now).
Move 34 (SEARCH): O, adding tile 7, like so:

7 tiles:

At this point, note again that the tiles still to be placed all have the 'straight through' structure (i.e the entry and exit are on opposing walls). This means these pieces can never be used as a way to get from the current positions to one of the four squares, which are all already out in the maze. These tiles will therefore never be entered by a counter - they are purely dead-end pieces which will need to be laid through the search-square moves.

As a result of this, we do not want to move O South at this point, as it will never end up getting to a square if we do! This leaves one viable option for the next move...

Move 35 (SOUTH): P (only option).
Move 36 (WEST): P (only option), but only if P moved only one space in Move 35 (or it will have ended up on a staircase).
Move 37 (STAIRS): P - although G is an option, we need a counter on a search-space for the Search action in a few moves' time...
Move 38 (NORTH): Y or O. Which one? Well, in Move 39 one of these two pieces will need to move East. If O moves North now, that will be impossible as both would have a wall to their right. Thus Y must move North now.
Move 39 (EAST): Either Y or O - we can't be sure which just yet...
Move 40 (SEARCH): P, adding tile 8, like so:

8 tiles:

Before Move 41 we need to ask ourselves: Who can move West in Move 42? Well, G and Y can't, and we don't want P to go West - that way leads to a dead-end. So O is our only option. That means that on Move 41, O must move South from its current position... which means that O (not Y) must have moved East in Move 39. In order to be able to move West in Move 42, O must be at the far end of its tile, giving us the following sequence of moves:

Move 41 (SOUTH): O - but by one or two spaces? Not sure yet...
Move 42 (WEST): O again - but do we send it to its square or to the bottom row of the tile? Again, not sure yet...
Move 43 (STAIRS): G (only option) - now ON ITS SQUARE.

Considering the moves remaining to us before the next Search action must be carried out, only O could realistically do it - and only if we have not sent it to its square in Move 42, tempting as it was... Therefore, O is on the bottom row of its tile and must already be sitting on the search-square. We do not want to move it North and away from this square just yet, so instead we have:

Move 44 (NORTH): P (only viable option).
Move 45 (EAST): P or Y (can't be sure which yet).
Move 46 (SEARCH): O, adding tile 9, like so:

9 tiles:

Note at this point that G is home and we do not want O or P to go South any more. This means only Y must be allowed to travel South from now on, which in turn means that in Move 45 we must have moved Y to a position from which it may move South in Move 47. The moves proceed as follows:

Move 47 (SOUTH): Y (only option).
Move 48 (WEST): O (only option).
Move 49 (STAIRS): Y (only option).
Move 50 (NORTH): O (only option).
Move 51 (EAST): P (we need a counter on the stairs for the next cycle).
Move 52 (SEARCH): Y, adding the final tile 10, like so:



(Note that although its South wall blocks off a search-space on an older tile, this is a perfectly legitimate tile placement by the rules of the game as specified in the question.)

10 tiles:

Now it's the home straight! Five moves left, all vital:

Move 53 (SOUTH): Y.
Move 54 (WEST): Y - now ON ITS SQUARE.
Move 55 (STAIRS): P.
Move 56 (NORTH): P - now ON ITS SQUARE.
Move 57 (EAST): O - now ON ITS SQUARE.

HOORAY! All pieces are now on their squares, the puzzle is solved, there is nothing further to do and I need to go get a drink and rock quietly backwards and forwards to myself in a corner somewhere! Phew! Epic puzzle – huge congrats to the setter for this truly fantastic accomplishment!

Answer 2

Wrap-up: The Making Of Magic Maze Puzzle

This is not a solution to the puzzle, but provides notes from its poser. This type of answer has been approved by the community.

Caution: This post may contain spoilers.

---

Inspiration

This puzzle originates from a competition to invent a new genre of logic puzzle which involved moving objects. I initially asked whether a chess puzzle would count, but obviously there's a wide literature of chess puzzles so it would be hard to guarantee my genre was indeed new.

At the time of making this puzzle, I had recently been to a board game store with friends and played Magic Maze, which I found fun. After thinking for a while about possible board games out of which I could make a puzzle, I settled on that.

Initial thoughts

To start with, I needed to work out a suitable subset of the rules to implement, since Magic Maze has a lot of rules, and then some as you play the harder 'levels' of the game. Obviously a key part of the game was the revealing of tiles, so some sort of revealing was required. But since a logic puzzle has to have perfect information, it was important that all tiles were visible. As a result, I decided to make a custom set of tiles, with the stack in a predetermined order (you aren't able to choose the order of tiles in the game, and allowing for that would have made the logic of which tile to choose next almost impossible).

It also quickly became clear that allowing arbitrary moves wasn't a possibility. So I had two options: choose a fixed order of tokens, or choose a fixed order of move types. Given that you could break a long move in one direction into shorter moves, a fixed order of tokens seemed infeasible, so I chose a fixed order of move types - given that different directions and searching new tiles were split up among different players in the base game, I decided that the moves would be N, E, S, W and search. Also, I decided pieces couldn't occupy the same space twice as this would have been too difficult for me to picture.

At this stage it was probably possible to construct a similar puzzle to what I have now, but there were still limitations in that one could relatively easily reorder the movement stages of tokens among several "cycles". As a result, I chose to include "stairs" (in the base game I believe they're escalators, but I didn't want to make detailed drawings) - these would provide more constraints on where tokens were at particular times. I decided on the order at this stage up to cyclic rearrangement, spacing out each pair of stairs/search, N/S and E/W.

Finally, I decided to adopt the premise of the game that you have to move all the tokens to "shops" (triangles) at the same time, and then to "exits" (squares) - this seemed like it would be constraining enough while still being interesting.

Creation

Obviously, to easily draw things, I needed some sort of grid. To account for the endless backtracking that looked like it would be necessary at the time, I decided to do this on my computer, and thus I needed the ability to stroke-erase and undo a lot. My choices were some Adobe product or OneNote, and being more familiar with the latter (which I do a lot of online puzzles on as well), I chose that.

It was time to design the first tile. In accordance with Magic Maze, it would be 4 by 4, and the exits would be on the right-middle edge of each side. Also, stairs seemed quite necessary with the move ordering constraint, and all four exits need to be open (I didn't want a triangle or square on this tile). I also chose to have a symmetrical layout on each tile. Finally, in accordance with the game, I decided that the tokens should initially occupy the central 4 squares. So I made a first draft:

Once I had settled on this design, I finally had the motivator that would get me going. Logic proceeded smoothly, until around tile 4 where I was a bit stuck. To get the last two pieces out of the centre tile required a few moves in a certain order which was "backwards" compared to the cycle I had arranged, so I needed places to dump a lot of moves. This was tile 4, and that's why it looked so crazy.

There was also an ambiguity over which of tile 4 and 5 would be placed in which place. As a result, I made one of my first "deeper" arguments in this puzzle, which was that with tiles 8, 9 and 10 closed except for moving "straight", it would be impossible for two tokens to get to the two squares on tile 4.

As I got more familiar with the movement of the pieces, I was able to foresee somewhat deeper consequences of some moves. I also realised the final move-counting argument seen by Dr Xorile at this stage, and as a result I found that the ending was actually quite constrained even with few walls (e.g. see tile 7), so I only had to make sure some set of moves actually allowed for the finish. (Of course, tiles 8, 9 and 10 were necessarily inconsequential, as determined back at tile 4.)

^{(Click for better resolution)}

After a couple of rounds of testsolving, I edited a bit for uniqueness (some extra variations I hadn't seen caused me some trouble, but luckily they were "far enough away" from the main line that I could mostly add one wall and remove them), and then removed some unnecessary walls in the first 7 tiles. Reasonably convinced that it was unique, I prettified it and sent it off to the competition.

^{(I sent off the light version because it's easier on printers, but I like the dark version better...)}

Reception

The puzzle was much better received in the competition than I initially thought it would be given its complexity, though it did take a couple of people solving it and recommending it for it to kick off (the competition had anonymous submissions for voting purposes, so I couldn't endorse it). One solver used LaTEX to tidy my rough scribbles up, which made it look a lot more presentable - thanks for that! It also seems to have been popular here on Puzzling.

In terms of solving methods, some people printed it out (with, I think, one laminating the LaTEXed version). Others used tools such as GIMP and I am really impressed with the pair that did it in Google Sheets!

^{(Click for better resolution... doesn't this look like fun to set up!)}

Afterthoughts

I guess I wish I could have made a better title - I wanted "Magic Maze" and thought appending "Puzzle" seemed a bit artificial, but "Magic Maze" doesn't meet the 15 character limit. I initially thought that the rules were too convoluted to understand anyway, even after simplifying, but it appears not. Hopefully a few more people have actually tried solving it - and if you did so, I hope you liked it! (With this format, it's pretty tempting to click on the solution, I guess...)

It would be pretty interesting to try this with a different set of actions: a few more are available in the base game, and yet more with expansion packs. Portals, anyone? I also wonder whether an interesting puzzle could be made without stairs: as mentioned above, they were somewhat of a convenience measure for me as the puzzlewright.