8
$\begingroup$

We have a different type of puzzle which consists of 4x4 board with numbers on it;

enter image description here

Your task is to put numbers in the correct order as given in the diagram above.

In each step, you can take one number from a color and one number from another color and interchange them. In other words, if you take a number from yellow square, you can interchange that number with only white backgrounded numbers.

So what is the minimum number of steps to obtain the correct order given above for the question below?

enter image description here

$\endgroup$
  • $\begingroup$ You accepted Sconibulus's answer. Does that mean that you know that his answer is optimal? Can you prove it? $\endgroup$ – Peregrine Rook Dec 15 '16 at 23:44
  • $\begingroup$ @PeregrineRook yes i can, but i didnt ask for it for this part of the question. $\endgroup$ – Oray Dec 16 '16 at 4:50
3
$\begingroup$

You should be able to do it in

14 steps

Because the grid contains

2 cycles of length 8: 4 11 12 8 7 16 15 3 4 and 1 2 9 10 6 5 14 13 1

And each

cycle is correctable in length-1 swaps. e.g. Swap 4 with 3, then with 15, then with 16, then with 7, then with 8, then with 12, then finally with 11, and that cycle is entirely correct.

$\endgroup$
  • $\begingroup$ I can see how your approach gives an upper bound to the minimum that we look for, but why is it also proven that you cannot do it in fewer steps? $\endgroup$ – elias Dec 15 '16 at 18:21
  • $\begingroup$ I mean, I can see that it works, but don't fully understand why. $\endgroup$ – elias Dec 15 '16 at 18:23
  • 1
    $\begingroup$ @elias This actually gives the lower bound, rather than the upper bound. The upper bound would additionally have some of the swaps in the 'ideal' solution being illegal, which I have not worked out yet. $\endgroup$ – Sconibulus Dec 15 '16 at 18:25
  • 1
    $\begingroup$ To understand how it works, consider shorter cycles, if there is a cycle of two, then each tile points at the spot occupied by the other, and one swap fixes it. If there is a cycle of three, than after one swap you have one correct tile (cycle of one) and a cycle of two. $\endgroup$ – Sconibulus Dec 15 '16 at 18:27
  • $\begingroup$ Showing a solution which needs $n$ steps is an upper bound of $n$ if we are looking for a solution with the minimal number of steps. Isn't it? $\endgroup$ – elias Dec 15 '16 at 18:40
1
$\begingroup$

Partial answer:

(But more than the other answers posted so far.    :-)    )

I can do it in 14 moves:

 1 ↔ 2,  2 ↔ 13,  2 ↔ 9,  4 ↔ 11,  3 ↔ 11,  5 ↔ 14,  6 ↔ 14,  7 ↔ 16,  8 ↔ 16,  9 ↔ 14,  9 ↔ 10,  12 ↔ 16,  11 ↔ 16,  15 ↔ 16

It can’t possibly be done in fewer than

eight (8) steps

because

all of the numbers are in the wrong cell.  Trivially, the most you can do in one step is to fix two numbers/cells.  Therefore, 7 or fewer steps cannot fix more than 14 numbers/cells, so there cannot be a solution with fewer than 8 steps.

I’m still working on finding a better (lower) solution and/or increasing the provable lower bound.

$\endgroup$
  • $\begingroup$ What do you mean by $2\to 13$ ? Both 2 and 13 are in a white cell and both cell #2 and cell #13 are orange. $\endgroup$ – FrodCube Dec 15 '16 at 18:02
  • $\begingroup$ Oops; brain freeze.  I’ve fixed it (I think). $\endgroup$ – Peregrine Rook Dec 15 '16 at 18:11
  • $\begingroup$ I probably won’t be doing anything more on this in the next few hours, because I have something else I need to work on right now. $\endgroup$ – Peregrine Rook Dec 15 '16 at 18:12
  • 1
    $\begingroup$ Also, #1 is in a wrong cell just like all the other numbers. $\endgroup$ – elias Dec 15 '16 at 18:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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