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

Improve this question
$\endgroup$
2
  • $\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, 2016 at 23:44
  • $\begingroup$ @PeregrineRook yes i can, but i didnt ask for it for this part of the question. $\endgroup$
    – Oray
    Dec 16, 2016 at 4:50

2 Answers 2

Reset to default
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.

Improve this answer
$\endgroup$
7
  • $\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, 2016 at 18:21
  • $\begingroup$ I mean, I can see that it works, but don't fully understand why. $\endgroup$
    – elias
    Dec 15, 2016 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, 2016 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, 2016 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, 2016 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.

Improve this answer
$\endgroup$
4
  • $\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, 2016 at 18:02
  • $\begingroup$ Oops; brain freeze.  I’ve fixed it (I think). $\endgroup$
    – Peregrine Rook
    Dec 15, 2016 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, 2016 at 18:12
  • 1
    $\begingroup$ Also, #1 is in a wrong cell just like all the other numbers. $\endgroup$
    – elias
    Dec 15, 2016 at 18:18

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.