Reverse Puzzling 4

Question

[This continues prior Reverse Puzzling here, here and here]

George rubbed his hands together with glee. "So this is Andrea's puzzle, is it?"

"Yes," I answered. "It's the first of them, anyway."

"It's not very big, so it shouldn't be too hard. How does it work?"

I explained the concept to him, and after a few false starts a frown furrowed his brow.

"Let me see," he muttered to himself, as he got out a pen and paper.

After a little while, following his usual systematic (and somewhat laborious) approach, he had drawn the following:

I knew what he was drawing, so I think I can say that the lines are all meant to be arrows (either single or double-headed). He occasionally didn't draw them in properly, but you shouldn't let that put you off.

It was remarkable to me how complicated it looked, when the original puzzle looked so simple and elegant.

What was the original puzzle?

Edit: After George saw the puzzle, he was embarrassed and insisted I update the diagram to show all the arrows more clearly.

Answer 1

This is Andrea Gilbert's first handmade

Orientation Maze (http://clickmazes.com/orient/g4g5.htm), made for Gathering For Gardner 5.

The rules are simple:

You enter the maze on the lowest tile facing north. You may follow any direction on the tiles in front of you. The goal is the top right tile.

How it relates to the diagram:

Each group of 4 (or 1) in the diagram represents a square, and the positions in those groups represent directions that you face. Arrows represent valid moves.

Answer 2

So, some observations. (Nothing close to a solution.)

Obviously the diagram shows the state space of a puzzle and (some of?) the available moves from state to state.

The state space seems to be four-dimensional: 4x4x2x2. (Two size-4 dimensions for which group-of-four. Two size-2 dimensions for which blob within a group-of-four.) Every move changes just one of the four components, by just 1. This feels a bit like a sliding-block puzzle -- perhaps the four components of the state are two pairs of coordinates, or something. (But see below for one reason to dislike the sliding-block-puzzle hypothesis.)

There are a few places where a sequence of moves has no overall effect, but startlingly few. On the whole, any move you make is a permanent commitment and if you make a wrong one you will eventually find yourself out of moves and having to start again. I find this odd in combination with the absence of any sort of "directionality" apparent in the state-graph: it suggests that the nearly-one-way-ness of the puzzle is just a matter of clever state-graph design, rather than emerging from some physical feature like an ever-tightening screw or a gradually-dropping ball or whatever.

There appear to be separate start and end states. E.g., if this is a sliding-block puzzle then maybe it has gaps at the sides and the challenge is to get one piece in at one side and out at the other.

Obviously red is being used to mark the shortest path between start and end. It looks initially as if there's some redundancy in the northeast corner, but if those arrowheads are correctly drawn then indeed we need to use all the red states. Note that this means that the available moves really truly are often irreversible, which is strong evidence that this is not a sliding-block puzzle.

The "short" edges -- within the 2x2 clusters -- have no arrowheads. This may just be because there isn't space for them, but another possibility is that whatever process changes state within a cluster is always reversible. [EDITED to add:] After Dr Xorile's update with the clearer diagram, it's apparent that actually the short edges are frequently unidirectional. So ignore this paragraph.

Earlier "Reverse Puzzling" puzzles have featured specific rather famous puzzles. This one isn't ringing any bells for me yet, though.

Answer 3

More items of note:

All outside edges of the state map are either untranslated (no action) or a dead state (acted upon but no further translations). Hence, none of them are red (red must have a continuous line of uninterrupted action).

The path of the red circle is as follows with (1,1) being the upper left set (increasing to the left and down) and labeling the positions as A-D from the left going clockwise:

(2,4) B [ENTRY]
(2,3) B
(1,3) B,C,D
(1,2) D
(1,1) D,C
(2,1) C
(3,1) C
(3,2) C,B
(4,2) B
(4,3) B,A,D
(4,2) D,A
(4,1) A
(3,1) A,D [EXIT]

Answer 4

After working hard on this 3-D directed graph, I guess it's the:

Hat-guessing problem, with $4$ logicians and $6$ hats, 3 red and 3 green.

The reason that it feels that way is,

At each level (or say row), there are two arrows emanating from one of the spheres(or simply circles) which represent the two possibilities of the colour of hat on his head. And the single arrow at the same level represents that one logician is either looking at their hats or thinking from their perspective(trying to deduce the color of his hat using inductive logic).