14
\$\begingroup\$

Challenge:

Given a checkerboard, output the smallest amount of moves it would take (assuming black does not move at all) to king a red piece, if possible.

Rules:

Red's side will always be on the bottom, however their pieces may start in any row (even the king's row they need to get to). Black pieces are stationary, meaning they do not move in between red's movements, but they are removed from the board when captured. Note that pieces can start on any space on the board, including right next to each other. This is not how normal checkers is played, but your program must be able to solve these. (See input 5) However, checker pieces must only move diagonally (see input 3). Backward-capturing is allowed if the first capture is forward in the chain (see input 7).

Input:

An 8x8 checkerboard, with board spaces defined as the following characters(feel free to use alternatives as long as they're consistent):

. - Empty

R - Red piece(s)

B - Black piece(s)

Output:

The smallest number of moves it would take a red piece to be 'kinged' by entering the king's row on the top row of the board (black's side), 0 if no moves are required (a red piece started on king's row), or a negative number if it is impossible to king a red piece (ie black occupies it's entire first row).

Input 1:

. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .

Output 1:

7

Input 2:

. . . . . . . .
. . . . . . . .
. . . . . B . .
. . . . . . . .
. . . B . . . .
. . . . . . . .
. B . . . . . .
R . . . . . . .

Output 2:

2

Input 3:

. B . B . B . B
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .

Output 3:

-1

Input 4:

. . . . . . . R
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
R . . . . . . .

Output 4:

0

Input 5:

. . . . . . . .
. . . . . . . .
. . . . . . . .
. B . . B . . .
B . . . . B . .
. B . B . . . .
. . B . . B . .
. . . R R . . .

Output 5:

4

Input 6:

. . . . . . . .
. . . . . . . .
. B . . . . . .
. . B . . . . .
. B . B . . . .
. . . . R . . .
. . . B . . . .
. . . . R . . .

Output 6:

2

Input 7:

. . . . . . . .
. . . . . . . .
. . B . . . . .
. . . . . . . .
. . B . . . . .
. B . B . B . .
. . . . B . . .
. . . . . R . R

Output 7:

4

Scoring:

This is , so shortest code in bytes wins.

\$\endgroup\$
  • 1
    \$\begingroup\$ Shouldn't the second test case be 2, since you can double/triple jump? \$\endgroup\$ – DJMcMayhem Sep 26 '16 at 16:23
  • \$\begingroup\$ Is a state array of arrays of integers as input OK? \$\endgroup\$ – Jonathan Allan Sep 26 '16 at 16:23
  • 1
    \$\begingroup\$ I added another testcase that should prove difficult. It involves multiple jumps, multiple pieces and jumping backwards in order to achieve the best possible solution. \$\endgroup\$ – orlp Sep 26 '16 at 16:44
  • 1
    \$\begingroup\$ @orlp Hm, I was going to say none of the red pieces are allowed to move backwards since none of them are kings (hence the point of the challenge), but it appears some people play with rules where capturing backwards is allowed by non-kinged pieces if the first capture was forward. I'll add that to the rules since I was not aware of this before. \$\endgroup\$ – Yodle Sep 26 '16 at 16:50
  • 1
    \$\begingroup\$ ooooooooh, you don't have to choose just one red piece, they can team up! I get it \$\endgroup\$ – Greg Martin Sep 26 '16 at 21:00
4
\$\begingroup\$

JavaScript (ES6), 354 322 bytes

Takes an array as input with:

  • 0 = empty square
  • 1 = red piece
  • 2 = black piece

Returns the optimal number of moves, or 99 if there's no solution.

It's very fast but could be golfed much more.

F=(b,n=0,C=-1,i)=>b.map((v,f,X,T,x=f&7,y=f>>3)=>v-1||(y&&n<m?[-9,-7,7,9].map(d=>(N=c=X=-1,r=(d&7)<2,T=(t=f+d)>=0&t<64&&(x||r)&&(x<7||!r)?(!b[t]&d<0)?t:b[t]&1?N:b[t]&2&&(d<0&y>1|d>0&C==f)?(X=t,x>1||r)&&(x<6|!r)&&!b[t+=d]?c=t:N:N:N)+1&&(b[f]=b[X]=0,b[T]=1,F(b,n+!(C==f&c>N),c,1),b[f]=1,b[X]=2,b[T]=0)):m=n<m?n:m),m=i?m:99)|m

var test = [
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,2,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,2,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,2,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,2,0,2,0,2,0,2,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,0,0,0,0,0,0,1,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    1,0,0,0,0,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,2,0,0,2,0,0,0,
    2,0,0,0,0,2,0,0,
    0,2,0,2,0,0,0,0,
    0,0,2,0,0,2,0,0,
    0,0,0,1,1,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,2,0,0,0,0,0,0,
    0,0,2,0,0,0,0,0,
    0,2,0,2,0,0,0,0,
    0,0,0,0,1,0,0,0,
    0,0,0,2,0,0,0,0,
    0,0,0,0,1,0,0,0
  ],
  [ 0,0,0,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,2,0,0,0,0,0,
    0,0,0,0,0,0,0,0,
    0,0,2,0,0,0,0,0,
    0,2,0,2,0,2,0,0,
    0,0,0,0,2,0,0,0,
    0,0,0,0,0,1,0,1
  ]
];

test.forEach((b, n) => {
  console.log("Test #" + (n + 1) + " : " + F(b));
});

\$\endgroup\$
  • \$\begingroup\$ 99 is probably fine, I can't imagine a real solution taking 99 moves on an 8x8 board. Nice job! \$\endgroup\$ – Yodle Sep 28 '16 at 14:53

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.