I have a question how to solve the following problem.

First, we have a chess board and two pawns located at $a1$ and $a2$. Our goal is to move them to the location $h7$ and $h8$. The rules for a pawn movement are the following:

  1. We can move our pawn regularly just by moving it by one unit up, down, left, or right.
  2. The pawn can jump over another pawn. If there is some space before another pawn, it will jump symmetrically skipping the equal number of empty squares after it lands. For example, if the pawn are located at a1 and a4, then after the jump they will located at a4 and a7.

Question: What is the minimum number of moves we need to perform to move our pawns from the initial to the final destination ?

  • 2
    $\begingroup$ Where did you get this puzzle? $\endgroup$
    – coffeemath
    Mar 30 at 6:51
  • $\begingroup$ I came up with it while I was playing Chinese checkers with friends. $\endgroup$ Mar 30 at 7:24
  • 3
    $\begingroup$ Easy to find a particular solution in 14 moves by hand (if I understand well the problem). But how to prove it is optimal or not? $\endgroup$
    – Damien
    Mar 30 at 8:09
  • 2
    $\begingroup$ @Damien, yeah, I found one with 13 moves. $\endgroup$ Mar 30 at 15:07
  • $\begingroup$ @MaximZubkov Congratulations. I hope you will provide the optimal solution at the end, if no answer provides it. $\endgroup$
    – Damien
    Mar 30 at 15:18

Easy to solve since there are less than 64x64 positions. Let A(n) be the set of positions that can be reached from the start position in n moves, and B(m) the set of positions that can reach the end position in m moves. Calculate A(1), B(1), A(2), B(2) etc. until you find A(n) and B(m) with a common element, then the solution is n+m.

  • 4
    $\begingroup$ So, according to this solution, I can just write a program that will give me the answer. This is a brute force approach, and I wonder if there is a faster way to find a lower bound. $\endgroup$ Mar 30 at 7:22

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.