1
$\begingroup$

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.

$\endgroup$

closed as off-topic by Bobson Dugnutt, Najib Idrissi, Claude Leibovici, hardmath, JonMark Perry Mar 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.

  • $\begingroup$ Something like NP complete problems? $\endgroup$ – Pieter21 Mar 11 '16 at 8:10
  • 7
    $\begingroup$ If your definition of "unsolvable" is that it requires many moves, then just create a big enough Rubik's. $\endgroup$ – Bobson Dugnutt Mar 11 '16 at 8:13
  • 1
    $\begingroup$ 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 $\endgroup$ – reuns Mar 11 '16 at 8:27
  • $\begingroup$ @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. $\endgroup$ – vrugtehagel Mar 11 '16 at 9:37
  • $\begingroup$ @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... $\endgroup$ – Ivan Neretin Mar 11 '16 at 9:39
5
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ One could, however, specify how many positions or sequences the algorithm is allowed to search, and define feasibility that way (which I think might be the kind of thing intended). $\endgroup$ – timtfj Feb 12 at 17:07
  • $\begingroup$ Maybe, but you might have an algorithm that doesn't explicitly search positions or sequences, but rather some encoded version of them. $\endgroup$ – Robert Israel Feb 12 at 18:00
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Yes, it is an encryption problem. Exactly that. $\endgroup$ – Frans Lundberg Mar 11 '16 at 15:34

Not the answer you're looking for? Browse other questions tagged or ask your own question.