2
$\begingroup$

I'm creating a new puzzle: two sliding blocks 8-puzzle, one on top of the other. Several pieces are covered and cannot be moved until the covering piece moves away. The objective is to pair colors, no matter the final positions.

enter image description here The Puzzle (by now it is not random, I'm testing yet)

enter image description here Objective is to pair colors

enter image description here It consists of two layers (thanks GIMP...)

http://www.puzzlopia.com/puzzles/overlapped-8/play

The fact is that the puzzle can always be solved moving only the upper layer.

The question is: if the initial position is random on both layers, the shortest solution involves moving pieces from bottom layer or it always consists of moves only from upper layer?

If optimal consists always only of upper pieces, then this puzzle reduces to an 8-puzzle and then I have to redesign it!

Improve this question
$\endgroup$
10
  • 1
    $\begingroup$ What rules do you understand by saying "Several pieces are covered and cannot be moved until the covering piece moves away" - which pieces, when are they "covered" necessarily, can you only move a bottom piece to the empty space when the piece to be moved is not covered by the top layer? Can you move the top layer without any restrictions? (Btw I haven't actually checked, but if the bottom and top layer have random start, then I think a parity needs to be equal for it to be possible) $\endgroup$
    – Piotr Pytlik
    Feb 17, 2016 at 11:22
  • $\begingroup$ Both layers move independently like any sliding block puzzle. But the top layer covers the bottom, so the only piece from bottom layer that you are allowed to move at each instant is the one that is at the same position as the top layer hole (or free cell). Of course, that piece can be moved only to a free adjacent cell. By random I mean random valid movements, so parity is not an issue, although it could be interesting to check! $\endgroup$
    – Edgar G.
    Feb 17, 2016 at 11:42
  • $\begingroup$ My first thought is that moving the bottom layer probably doesn't help with shortening the solution. The only thing to check would be that the parity of both layers is the same ;) If you always start from a solution and do random valid movements, the parity of a layer doesn't change. $\endgroup$
    – Piotr Pytlik
    Feb 17, 2016 at 11:59
  • $\begingroup$ It is incredibly simple, I completed it quite fast, maybe you could anchor certain squares of either layer, so that they couldn't be moved (you have to move around them). Just a thought. $\endgroup$
    – Daedric
    Feb 17, 2016 at 12:22
  • $\begingroup$ Thanks for your opinion @Daedric! Ok, I will think about how to transform it into an actual puzzle (at least one different from the classic 8-problem), maybe adding restriction on pieces as you suggest. $\endgroup$
    – Edgar G.
    Feb 17, 2016 at 12:55

1 Answer 1

Reset to default
3
$\begingroup$

The optimal solution will involve only one layer.

Lets assume that you have an optimal solution involving both layers. The initial state of the top layer is $X$ and the initial state of the bottom layer is $Y$. The optimal solution is a sequence of moves for the top layer $S_t=\{f_0, f_1, ... , f_n\}$ and a sequence of moves for the bottom layer $S_b=\{g_0, g_1, ... , g_m\}$.

Let $S(A)=B$ be the application of the sequence of moves $S$ on the state $A$ and the resulting state is $B$. Thus, $S_t(X)=W$ and $S_b(Y)=W$ since this is a solution.

Let $m^r$ be the reverse move of $m$. If you reverse a move, you can undo the move. For example, if applying move $m$ on state $A$ results in state $B$, then applying move $m^r$ on state $B$ results in state $A$. Furthermore, if $S=\{a_0, ..., a_k\}$, then we will define a reversed sequence $S^r=\{a_k^r, ..., a_0^r\}$. If $S(A)=B$, then we can easily see that $S^r(B)=A$.

Therefore, we know that $S_b^r(W)=Y$

Also, if you have two sequences of moves where $S_0(A)=B$ and $S_1(B)=C$, then $S_1(S_0(A))=C$ and if $S=S_0 + S_1$, then $S(A)=C$.

So, let us construct a new sequence of moves $S_{t1}=S_t + S_b^r = \{f_0, ..., f_n, g_m^r, ..., g_0^r\}$. We know that $S_t(X)=W$, and $S_b^r(W)=Y$. Thus, $S_{t1}(X)=S_b^r(S_t(X))=S_b^r(W)=Y$. Thus, $S_{t1}$ is also a solution, but only in the top layer. It is also optimal since it has the same number of total moves as both $S_b$ and $S_t$.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Written that way seems very simple! You've convinced me; there's no need to move bottom pieces. $\endgroup$
    – Edgar G.
    Feb 17, 2016 at 16:41
  • 3
    $\begingroup$ @EdgarG. My answer has a lot of terminology... the condensed version is "do the opposite on the other layer backwards" and you end up in the same spot. $\endgroup$
    – Trenin
    Feb 17, 2016 at 17:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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