How to create a Rubik's cube type of puzzle that is infeasible to solve?

Question

Is it possible to create a mechanical puzzle, something like the Rubik's cube, that is infeasible to solve in general, but still demonstrably solvable if one knows the scrambling moves.

By "infeasible to solve", we mean that there is no general algorithm to solve a scrambled puzzle in less than 100 million moves. The puzzle starts at "the solved state", then a long enough sequence of random moves (the scrambling) will make the puzzle unsolvable if the sequence of moves is forgotten. Each move is reversible, so a scrambling is easy to reverse if one knows the scrambling moves.

Notation:

$$S_1 = S_0 | m_0$$

is used to denote that state $S_1$ is the result of appying move $m_0$ to state $S_0$.

Each move, m, has a corresponding inverse move, m' such that: $S = S | m m'$.

The puzzle has one particular state called the solved state, $S_{solved}$. Solving the puzzle is equivalent to finding a move sequence $m_1$, $m_2$, ...$m_n$, that transforms the current state, S, to the solved state:

$$S_{solved} = S | m_1, m_2, ...m_n$$

A scrambling of the puzzle is a random sequence of moves starting from the solved state. At each state, the next move is chosen randomly. Each possible next-move has the same probability of being chosen. A random scrambling of size n, is a random scrambling with n moves.

Let's define an F-puzzle:

• The puzzle has a finite number of states.
• One puzzle state is called the solved state, $S_{solved}$.
• Each puzzle state has a set of next possible moves. Each such set is finite and has a size of at least two.
• For any state, S, and any move, m, there is an inverse move, m', such that: $S = S | m m'$.
• A scrambling is a random sequence of moves starting from the solved state. The state after a scramble of size N is: $S_{scrambled} = S_{solved} | m_1 m_2 m_3 ... m_N$. A scrambling is trivial to unscramble given that the scramble sequence is known, $S_{solved} = S_{solved} | m_1 m_2 m_3 ... m_N m'_{N} m'_{N-1} ... m'_3 m'_2 m'_1$.

The Rubiks cube is an example of an F-puzzle, but it is solvable within 20 moves (half-turn metrics).

1. Can we create a mathematical F-puzzle that is infeasible to solve?

2. Can we create a mechanical F-puzzle that is infeasible to solve?

3. Can we create a practical mechanical F-puzzle that is infeasible to solve and can be mass-produced with a unit cost below 100 Euro?

Preferably, we would like a solution that does not involve explicit symbols (like a code lock, or a general mechanical computer), but is elegant like the Rubik's cube. The length of the scrambling sequence should not be too long either.

I realize that this question involves more than mathematics. Actually, a purely mathematical solution is not that hard to find. It is harder to find a mathematical solution that has a corresponding mechanical realization. Sorry, if this is off-topic.

I wrote about this in a blog post too, http://blog.franslundberg.com/2016/02/the-unsolvable-rubriks-cube.html.

Answer 1

If the number of possible moves in any state is finite, there is an algorithm to find a shortest possible solution if one exists: enumerate all possible sequences of one move, then of two moves, etc., until you find one that works. It's not an efficient algorithm, but it is an algorithm.

Answer 2

This looks like an encryption problem. Decryption is easy when you know the key, but exponentially-difficult if you don't. If you can encode such a problem in a mechanical puzzle, you can make something that is not algorithmically solvable within a reasonable amount of time.

In fact I wonder if this might be the kind of thing you're looking for. That is a white jigsaw puzzle, it has no picture on it. There are still some hints in the shape of the pieces, e.g. you can probably find the edge pieces and start from there. But imagine such a puzzle in 3D, say on the surface of a sphere. The only way of solving it would be brute-force trying all possibilities.