Hi Non-Twisty Puzzles fans,

Switched Maze is a mechanical maze. The object is to roll the metal ball from "Start" to "Goal". The ball is impeded by gates at several points in the maze. By rolling the ball against the levers, gates can be opened and closed.

This maze is related to Robert Abbott's Sliding Door Maze and Eldon Vaughn's Amaze. The rules of Abbott's puzzle is electronically enforced by the software implementation. The rules of Vaughn's maze is psychologically enforced by the game rule that says not to lift the stylus from the board. The switched Maze is fully mechanically enforced. That is, you cannot cheat without taking the puzzle apart or removing the transparent cover.

Switched Maze implements logical one-way gates, logical crossings and a Chinese-Rings type of passing point. Most likely, one could build a Turing Machine using the Switched Maze concept.

Watch the YouTube video.
Buy the puzzle at my Shapeways Shop.
Read more at the Shapeways Forum.
Check out the photos below.

Enjoy!

Oskar

It is a nice implementation, but the maze is too easy.

That is a rather bold statement for someone who hasn't even tried it. I can tell you that several people tried and failed at a recent local puzzlers event.

Oskar

That's awesome! Great job.

-Doug

It is indeed a very nice puzzle, Oskar.

Starting with the state of the puzzle at the beginning of your video, one needs to make only 11 operations of reversing the state of particular switches in a specific order (to go from IN to OUT). So, not taking into consideration the dexterity aspect, I would agree with Jared that this is a fairly easy version.

I bet there could be a way to make it very difficult (like Panex is to Hanoi).

Peace,

Skarabajo.

I think this is probably right, at least a space-bounded Turing machine. This puzzle ought to be PSPACE-complete. I'm looking at it.

I'm impressed that you could make a challenging puzzle with only three switches!

In fact I was able to solve the maze in my head. I'm pretty sure I didn't mess up either: the order of switches after the ball is at the point pictured above is blue, blue, red, blue, green, blue, red, blue, and then you can get out, right? Along with the three switches to get to that point (red, red, green) that makes the 11 that Skarabajo confirmed.

OK, yeah, I have the gadgets built in my head. I haven't written them down, but I'm pretty confident they work. This type of switch maze is PSPACE-complete, like sliding-block puzzles, Rush Hour, Sokoban, and many others, but unlike ordinary mazes.

Excellent, I am impressed, congratulations! As this challenge is apparently too easy for you, here is a harder one: "design a harder Switched Maze on the same grid size".

Enjoy!

Oskar

Hmm, I've never designed a logic maze before, so I wouldn't know where to begin... Can you have two sets of perpendicular switches in a physical version, or would there be unfortunate lockups?

I think something interesting would be to find some way to combine this with the Irreversible Cube's mechanism for switch blocking.

When you look at the internal parts of this puzzle at Shapeways, I think the mechanics of it are rather intriguing.

And it's a maze of course, so it's by definition interesting

I've been looking forward to this for a while. It looks great!

So, building a Turing machine from this concept, eh? Designing extremely basic and abstract computers is my forte! The only real "issue" that I can see is designating how the ball must move, but using binary switches for a rules table sounds like a great idea. Now the question is if the rules table should be a 4-tuple or 5-tuple. 4-tuple seems easier to implement, but it would require a much larger rules table. Actually, I don't even know if it it's even POSSIBLE to make a 5-tuple rules table with this. I could definitely see 4-tuple working. What do you guys think?

As I posted above, the construction already exists -- in my head. I'm pretty sure it works. I did my Ph.D. on games, puzzles, and computation.

It is an indirect reduction, so you wouldn't see explicit Turing machine mechanics in my construction. But if you are interested I can try to make some figures of the necessary gadgets.

The reduction is polynomial-space-bounded Turing machine acceptance -> Quantified Boolean Formulas -> Nondeterministic Constraint Logic -> Switched Maze. What this means is that, if you give me a (polynomial-space-bounded) Turing machine and an input, I can give you back a Switched Maze, such that the maze is solvable if and only if the Turing machine accepts the input. So effectively, it embodies the identical computation.

Step 2 of this reduction chain (QBF -> NCL) was part of my Ph.D. thesis; step 3 (NCL -> Switched Maze) is what's in my head.

An explicit Turing machine construction would be fascinating as well, however, though significantly more complicated. Most of the work in proving the result has already been done in showing that NCL is PSPACE-hard.

A more interesting question here is, which elements of Switched Maze gadgetry are actually necessary to show PSPACE-hardness (effectively, to build a computer)? My reduction is simplified by the fact that switches can have multiple levers and multiple pairs of blocking arms. Is it still hard if we tighten these restrictions? One pair of blocking arms (or maybe just a single blocking arm), one lever? I don't know. The gadgets I came up with wouldn't work.

It looks like a very fun puzzle, such a simple design. I wish i had one!

You should probably cut the sarcasm.


Also, if many people say the challenge is easy, it has nothing do do with your design, but with the solving, and I agree with them, you can figure out the way to go in your head quite easily. It's implementing that solution that can be tricky for example if the ball doesn't go the right way when you want it to.

I hate it when people interpret a sincere compliment as sarcasm. Not many people can correctly solve such puzzle in their mind. I was impressed, especially as correctness evidence was included.

Oskar

I didn't read your comment as a sarcasm in the first place.
I got a bit uncertain when I read Greg's post and I'm really glad that you clarified this.