# Thread: Question on a puzzle

1. ## Question on a puzzle

Concerns the current puzzle here (Chess Codes):
PUZZLEUP - Weekly Puzzle Competition (a problem and games site)

Seems to me it can be worded this way:
.................................................. ...........

An 8by8 array is filled at random with numbers 1 to 64.

A "move" consists of swapping an odd with an even number.

The aim is to end up with:

01 02 03 04 05 06 07 08
16 15 14 13 12 11 10 09
.....
49 50 51 52 53 54 55 56
64 63 62 61 60 59 58 57

Minimum moves = ?
.................................................. ...........
Any comments? Thank you.
Not looking for solution...only if I interpreted correctly.

2. ## Re: Question on a puzzle

Your formulation is different, Denis. You are using odd/even to represent the colour of the square (black/white), but that means that you swap the colours as well as the codes. In the original problem the colours are attached to the squares, not the codes.

I think, Romsek, that the target is to find the maximum, over all starting positions, of the minimum number of moves required. So one inefficient way to proceed would be to find, for each possible start position, the minimum number of moves required and then find the greatest of each of those numbers.

3. ## Re: Question on a puzzle

Thanks Archie; I see the fault in my assumption;
but easier to use as "code numbers"...less typing!

What I assumed is equivalent to saying you can swap
any number in an odd position with any number in an
even position....a goof!

Of course, worst case is where all odd numbers are in even
positions and all even numbers are in odd positions.

You mention Romsek: where d'hell is he?!

4. ## Re: Question on a puzzle

He obviously thought better of a comment about what number we were looking for. I didn't know we could delete posts here.

5. ## Re: Question on a puzzle

Originally Posted by Archie
I didn't know we could delete posts here.
Yeah but I can see all of them regardless, so behave.

-Dan

6. ## Re: Question on a puzzle

I think solution is 64 or 65. How bout you Archie/Romsek?

7. ## Re: Question on a puzzle

If every piece is on the right colour but the wrong square you need at least 64 swaps to get them right. The question is whether you can guarantee that the first set of swaps leaves every piece such that the square it is now on belongs to the piece that is now on it's own square.

You can consider each arrangement to consist of a number of cycles $a \to b \to c \to d \to \ldots \to a$ such that $a$ is on $b$'s square, $b$ is on $c$'s square, etc.. Can we guarantee to break all those cycles into 2-cycles such that each 2-cycle contains one black square and one white?

8. ## Re: Question on a puzzle

For an $n$ piece problem:
• if there is an even on an odd square, the pigeonhole principle says that there is also an odd on an even square. We can move both pieces home in 2 moves (at most) reducing the problem to an $n-2$ piece problem.
• if there is no even on an odd square, there is also no odd on an even. We can swap any even with any odd and then apply the previous case.

Thus $\max{(2n)} \le 3+\max{(2n-2)}$. And $\max{(2)}=1$. We therefore have $\max{(2n)} \le 3n-2$ and $\max{(64)} \le 94$

But, I think that, if we have no even on odd with $n$ pieces, then when we make the three moves to get to the $(2n-2)$ case, parity dictates that we now have a one even on odd and one odd on even.

Thus $\max{(2n)} \le 5+\max{(2n-4)}$. And $\max{(4)}=4$. We therefore have $\max{(4n)} \le 5n-1$ and $\max{(64)} \le 79$

9. ## Re: Question on a puzzle

But since had only 1 odd on even and only 1 even on odd, there are only two possible cases.

Either they are on each other's squares or the are not. If they are, it takes only one change to take two more from the size of the puzzle in which case we are back to no odd on even and no even on odd. Or, the odd, being the only odd on even must swap with another odd to get home and the even must swap with an even. In either case we get $\max{(2n)} \le 4+\max{(2n-4)}$ and so $\max{(4n)} \le 4n$ and $\max{(64)} \le 64$.

Now we have $64 \le \max{(64)} \le 64$ so

$\max{(64)} = 64$

10. ## Re: Question on a puzzle

Thanks Archie.
Say instead we have a 2 by 4:
you'd then expect 8 as answer; but 9 is needed.
Seems to be because we're not dealing with a square.
Is that correct?

11. ## Re: Question on a puzzle

I thought I had 8 for 8 (as I'd expect). What's your starting position that needs 9?

For example:
$$3\color{red}{4} 5\color{red}{6} 7\color{red}{8} 1\color{red}{2} \\ 3\color{red}{4} 5\color{red}{6} \color{blue}{8}\color{blue}{7} 1\color{red}{2} \\ 3\color{red}{4} 5\color{red}{6} \color{blue}{2}\color{red}{7} 1\color{blue}{8} \\ 3\color{red}{4} 5\color{red}{6} 2\color{blue}{1} \color{blue}{7}\color{red}{8} \\ \color{blue}1\color{red}{4} 5\color{red}{6} 2\color{blue}{3} 7\color{red}{8} \\ 1\color{blue}{2} 5\color{red}{6} \color{blue}{4}3 7\color{red}{8} \\ 1\color{red}{2} \color{blue}3\color{red}{6} 4\color{blue}{5} 7\color{red}{8} \\ 1\color{red}{2} 3\color{blue}{4} \color{blue}{6}5 7\color{red}{8} \\ 1\color{red}{2} 3\color{red}{4} \color{blue}{5}\color{blue}{6} 7\color{red}{8}$$

12. ## Re: Question on a puzzle

(3, 4, 1, 6, 7, 8, 5, 2)
(1,3) and (5,7) for the odds; and (2,4,6,8) for the evens.

Also 9 needed if above is a 1 by 8.

So seems answer = (2n)^2 if we're dealing with a 2n by 2n array.

13. ## Re: Question on a puzzle

I'm not convinced about that. I've missed a case in my analysis. Where there is one odd on even and one even on odd, you can have either the even is on the odd's square but not vice versa. Or you can have the odd on the even's square, but not vice-versa.

This creates a problem that requires at least one additional move to unpick.

Do we first have to join all the cycles and then start the process to reduce $n$? Or is it just a case of adjusting the parity at some point? But then the question is how and when?

A quick application of my algorithm gave me 19 for (2, 3, 4, 1, 6, 7, 8, 5, A, D, C, 9, E, F, 0, D) where zero must come first in the ordered array. Whether that is optimal or not, I don't know.