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

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.

## closed as off-topic by Bobson Dugnutt, Najib Idrissi, Claude Leibovici, hardmath, JonMark PerryMar 11 '16 at 13:23

This question appears to be off-topic. The users who voted to close gave this specific reason:

• "This question is not about mathematics, within the scope defined in the help center." – Bobson Dugnutt, Claude Leibovici
If this question can be reworded to fit the rules in the help center, please edit the question.

• Something like NP complete problems? – Pieter21 Mar 11 '16 at 8:10
• If your definition of "unsolvable" is that it requires many moves, then just create a big enough Rubik's. – Bobson Dugnutt Mar 11 '16 at 8:13
• I don't understand why unsolvable would mean "unsolvable by hands for a human", as a human can still create a machine to solve it, that's why human are so special, their capacities are limited only by the maths and the physics – reuns Mar 11 '16 at 8:27
• @Lovsovs, it turns out, the amount of turns you need (at most) for a $n\times n\times n$ cube is asymptotic with $n^2/\log(n)$, so in order to not-be able to solve a cube in less than $100$ million moves, be'd need quite a large $n$, and that puzzle is probably to big to be able to mass-produce for less than $100$ EUR. – vrugtehagel Mar 11 '16 at 9:37
• @Frans You seem to be using the terms "unsolvable" and "algorithm" in the sense different from the generally accepted, thus attracting the ire of mathematicians, hence the downvotes. Other than that, the question is totally legit. In fact, you are asking for a problem without efficient algorithm, so the solution can be checked fast, but can't be found fast, much like it is in NP complete problems. There might be a way... – Ivan Neretin Mar 11 '16 at 9:39