Checkers: King Me?

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.

• Shouldn't the second test case be 2, since you can double/triple jump? Sep 26, 2016 at 16:23
• Is a state array of arrays of integers as input OK? Sep 26, 2016 at 16:23
• 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.
– orlp
Sep 26, 2016 at 16:44
• @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. Sep 26, 2016 at 16:50
• ooooooooh, you don't have to choose just one red piece, they can team up! I get it Sep 26, 2016 at 21:00

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));
});

• 99 is probably fine, I can't imagine a real solution taking 99 moves on an 8x8 board. Nice job! Sep 28, 2016 at 14:53