Sliding blocks: Ebony and Ivory

Five months ago, I posted a sliding block puzzle: Exchange pawns (sliding block puzzle)

That puzzle was inspired by the famous Black and White puzzle invented in the 1970s:

BLACK
◼︎ ◼︎ ◼︎
WHITE


The minimal solution of the Black and White puzzle is 85 moves, or 62 moves if you count consecutive moves as one.

If you change all letters to black and white pawns, that is the pawn exchange puzzle.

Now, here is another sliding puzzle.

How many moves are needed to change EBONY/IVORY to IVORY/EBONY?

Clearly the most suitable background music is Ebony and Ivory by Paul McCartney and Stevie Wonder.

PS. Since the minimal solution of B/W is 85 moves, the minimal number of moves for this puzzle is no more than 85.

• I have got a solution, but it takes a while to create an animation for it :) Commented Aug 14, 2023 at 12:20
• In the future, could you create no-computers puzzles? I'm interested in how people would go about without handy BF searches. Commented Aug 14, 2023 at 12:39
• @newQOpenWid I've enjoyed solving a number of puzzles here with a computer. I realise that some users here disapprove but I can assure you that is isn't just as easy as "using a handy BF search" but requires a high degree of involvement and thought about the logic. The solutions I post are hand crafted, with code I write myself. This is quite different from asking an AI or using an online tool (like say, a Sudoku solver). Commented Aug 14, 2023 at 18:05
• @newQOpenWid (re your deleted comment) another view is that you use the skills that you have. If one person is good at shuffling tiles around by hand, but someone else quickly loses interest in that but can sustain another method... I'll add that some of my attempts are exhaustive solutions as you imply, but they do not necessarily better human logic well applied, and they are still a product of my logical powers, not the computer's. None of them contain any computer magic. Commented Aug 14, 2023 at 19:04
• @newQOpenWid you have overlooked the time it takes me to analyse the problem and actually write, debug and test the computer program. There is nothing instant about it, and some of my worse efforts won't find the best solution this side of eternity. It's just another way of going about finding a solution. Commented Aug 14, 2023 at 19:09

The optimal solution uses

68 moves.

Here's the animation showing all moves:

I also share the code at https://pastebin.com/T4C6gUHX

• Is your search exhaustive? Commented Aug 15, 2023 at 0:11
• Could you compress the video to a GIF for i.stack.imgur? Commented Aug 15, 2023 at 0:18
• @newQOpenWid I used bidirectional BFS, which should give optimal solution.
– Jun
Commented Aug 15, 2023 at 0:22
• Good! Thank you for sharing your code and welcome! Commented Aug 15, 2023 at 5:52

I have not the proof that below is the most optimal, but I could do it in

88 moves (or 60 moves if consecutive moves count as one)

See below the animation to do it:

• It looks very nice but how did you arrive at this? Commented Aug 14, 2023 at 18:53
• That is a surprisingly high number - in theory, having double Os and Vs would make the solution much more optimized, yet this is just ~5 steps away from the Black-and-White solution. In fact apparently the original Black and White solution happens to be more optimal if we don't count consecutive moves as one. Commented Aug 14, 2023 at 18:54
• @WeatherVane, with logical thinking, and trying the best I could without using any programming script, using only some scrabble tiles :) Commented Aug 14, 2023 at 18:57
• @newQOpenWid, the main problem is that all other letters are unique. In the black/white solution, it doesn't matter which black/white tile has to go where, as long as they are somewhere in the correct row. In this case, you need to change the order of some of the tiles, which costs many moves. Commented Aug 14, 2023 at 18:59
• Ah, sorry. I had assumed the puzzle had the actual letters black and white and you were supposed to put them in order again (if you change all letters). But that begs the question: if black/white is essentially the same as pawn exchange, then why doesn't OP's post mention Dmitry Kamenetsky's 52 move solution? Commented Aug 14, 2023 at 19:13