5
$\begingroup$

Checkers
Checkers, also called draughts, is an interesting game. all pieces are placed on black tile and are all pawns at the start. When a pawn reach the final line, a powerful piece is created: the Queen. It can move multiple tiles on the same move.

Question
On a 10*10checkers field, with international checkers rule. If you can place one white queen anywhere on the checker,
What is the maximum number of black pawn you can take in a row?
Can you prove that this number is optimal?

Some reminders
I want to remind that queen can go back, stop anywhere behind the pawn taken. Pawn won't disapear until the end of the whole move (so their tile will remain inaccessible for the queen) and you can't eat the same pawn twice!

Good luck!
Source: diophante.fr

$\endgroup$
  • $\begingroup$ Do you have a tool to manually place pawns? $\endgroup$ – Saeïdryl Apr 26 '18 at 12:12
  • $\begingroup$ I'm strugling to find this sorry! If anyone encounter one, post it here, I will incorporate it in my question! $\endgroup$ – Untitpoi Apr 26 '18 at 12:20
  • $\begingroup$ Is it necessary for the position to be reachable by a theoretically legal game of checkers? $\endgroup$ – Bass Apr 26 '18 at 12:42
  • $\begingroup$ Well no. No need for the position to be reachable. $\endgroup$ – Untitpoi Apr 26 '18 at 13:10
6
$\begingroup$

I found a possible solution with

19 captured pieces

..so the answer that proved that the maximum is three less probably needs some work. :-)

enter image description here

I tried to fit more black pieces in while making sure that each piece is "jumpable", that is, it has two empty spaces on opposite sides of it. The likely arrangement of filling alternating diagonals surprisingly doesn't fit all that many pieces, and out of all the arrangements I tried, only one has more pieces than the solution above:

enter image description here

That one doesn't have a path to capture all the pieces though: the marked squares near the corners have exactly one way to enter or exit them, and there's no way to capture the neighbouring pieces without visiting those squares. Therefore, each marked square would need to be an endpoint for the path, and given that there are four such squares, this is clearly impossible.

Although this does not constitute a formal proof on any kind, I myself am convinced that the above answer is the best one I'm ever going to find.

$\endgroup$
  • $\begingroup$ Apparently, this position is reachable. $\endgroup$ – noedne Apr 27 '18 at 6:41
  • $\begingroup$ @noedne, No way, out of all the possible symmetries and starting positions for the white king (there are many), that answer has chosen the exact same ones as I did! $\endgroup$ – Bass Apr 27 '18 at 6:46
  • $\begingroup$ It is a fairly natural spot. Unfortunate that that answer lacks any justification for the minimum. $\endgroup$ – noedne Apr 27 '18 at 6:54
  • $\begingroup$ the question you just link seems to agree Bass for the maximum number of pawn taken. In fact my question seems to be a duplicate of this question... $\endgroup$ – Untitpoi Apr 27 '18 at 11:08
2
$\begingroup$

I'm probably not right, as I've just been doodling during a meeting, but the longest contiguous path I could make captured

16

I'm not sure how to prove it mathematically, but the path runs:

0) A3
1) C5
2) A7
3) C9
4) E7
5) C5
6) E3
7) G1
8) I3
9) G5
10) I7
11) G9
12) E7
13) G5
14) E3
15) C1
16) A3

$\endgroup$
0
$\begingroup$

I can prove that UselessInfoMine's solution is optimal. Divide the black squares of the checkerboard into two groups, A and B, as shown. Every capturing hop is between two squares of the same group, hopping over a square of the opposite group. This means that all the captured pieces must be on squares of the same group. Furthermore, captured pieces cannot be on the edge. Since there are only sixteen internal squares in each group, a queen can only capture sixteen pieces in a single turn, which is achieved by UselessInfoMine's solution.

A   A   A   A   A
  B   B   B   B   B
A   A   A   A   A
  B   B   B   B   B
A   A   A   A   A
  B   B   B   B   B
A   A   A   A   A
  B   B   B   B   B
A   A   A   A   A
  B   B   B   B   B
$\endgroup$
  • $\begingroup$ You are using American Checkers rules, not International Checkers. $\endgroup$ – Acccumulation Apr 26 '18 at 20:21
  • $\begingroup$ @Acccumulation I see! I learned something new today. $\endgroup$ – Mike Earnest Apr 27 '18 at 0:12
  • $\begingroup$ Seiriously? There are rules that allow you to move extra empty squares after captures? I have never heard that before. $\endgroup$ – UselessInfoMine Apr 27 '18 at 9:14

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.