# Solve a Solitaire Chess Puzzle

Recently, I was introduced to a puzzle game known as Solitaire Chess. I'll summarize the rules here:

• The board is a 4x4 checkerboard.
• All pieces are the same color (no teams) and all pieces can capture any other piece.
• Every move must be a capture. No moving to empty squares.
• There must be exactly one piece remaining at the end.
• All pieces move exactly like they do in chess, with one modification: the pawn can capture in any diagonal direction (which technically makes it a ferz). For the benefit of those who may not know, I have included movement diagrams.
• None of the other rules of chess (such as check, castling, etc.) apply here. It's all about captures.

King (K)

K * . . | * K * . | * * * .
* * . . | * * * . | * K * .
. . . . | . . . . | * * * .
. . . . | . . . . | . . . .


Queen (Q)

Q * * * | * Q * * | * * * .
* * . . | * * * . | * Q * *
* . * . | . * . * | * * * .
* . . * | . * . . | . * . *


Rook (R)

R * * * | * R * * | . * . .
* . . . | . * . . | * R * *
* . . . | . * . . | . * . .
* . . . | . * . . | . * . .


Bishop (B)

B . . . | . B . . | * . * .
. * . . | * . * . | . B . .
. . * . | . . . * | * . * .
. . . * | . . . . | . . . *


Knight (N)

N . . . | . N . . | . . . *
. . * . | . . . * | . N . .
. * . . | * . * . | . . . *
. . . . | . . . . | * . * .


Pawn (P)

P . . . | . P . . | * . * .
. * . . | * . * . | . P . .
. . . . | . . . . | * . * .
. . . . | . . . . | . . . .


## Input/output

For reference, the sample puzzle from the Solitaire Chess webpage will be used:

. . . .
. B . .
R P . .
. . . N


The solution is to take the pawn with the knight, then take the knight with the rook, and finally take the bishop with the rook.

Input

Input must be in one of three forms; you are free to pick the one that is most convenient for you.

• A string of characters such as .....B..RP.....N, with or without newlines. The character representing a blank space may be any character that isn't one of KQRBNP.
• A list of lists (or a flattened list) where the elements are either characters or numbers, like so: [['.', '.', '.', '.'], ['.', 'B', '.', '.'], ['R', 'P', '.', '.'], ['.', '.', '.', 'N']] or [[0, 0, 0, 0], [0, 4, 0, 0], [3, 6, 0, 0], [0, 0, 0, 5]]. For the former, the character that represents a blank space may be anything that isn't one of KQRBNP. For the latter, I've given pieces the number that corresponds to their rank in my earlier list of moves (1 is a king, 4 is a bishop, 6 is a pawn, etc.). You are free to change the numbering.
• A list of coordinates where each element has the form [x, y, 'c'], like so: [[1, 2, 'B'], [0, 1, 'R'], [1, 1, 'P'], [3, 0, 'N']].

If you pick one of the list-based input formats, the separators and delimiters may be any reasonable and understandable characters.

Output

Output must be a sequence of moves or a sequence of board states. Some puzzles have more than one solution; you may output one or all of them. If you choose to output a sequence of board states, each board must be in one of the three input formats, with a reasonable separator (such as newlines) between them.

If you choose to output a sequence of moves, they must be expressed as a list of pairs of coordinate pairs, like so: [[[3,0], [1,1]], [[0,1], [1,1]], [[1,1], [1,2]]]. [0,0] represents the bottom left corner, and again, separating and delimiting characters may be any reasonable choice.

If a given board cannot be solved, output any falsy value (0, empty string, etc.). If a given board has fewer than two pieces, behavior is undefined.

## Test Cases

Note: outputs are only given as a list of pairs of coordinates since the other formats should be fairly easy to check for correctness (and I didn't feel like typing out all the possible output formats). Also, for the puzzles that have more than one solution, only one possibility is provided.

Input 1:

. . . N
. . . .
. R . .
. . B .

...N.....R....B.

[['.', '.', '.', 'N'], ['.', '.', '.', '.'], ['.', 'R', '.', '.'], ['.', '.', 'B', '.']]

[[0, 0, 0, 5], [0, 0, 0, 0], [0, 3, 0, 0], [0, 0, 4, 0]]

[[3, 3, 'N'], [1, 1, 'R'], [2, 0, 'B']]


Output 1:

[[[2,0], [1,1]], [[1,1], [3,3]]]


Input 2:

. . . .
. B . .
R P . .
. . . N

.....B..RP.....N

[['.', '.', '.', '.'], ['.', 'B', '.', '.'], ['R', 'P', '.', '.'], ['.', '.', '.', 'N']]

[[0, 0, 0, 0], [0, 4, 0, 0], [3, 6, 0, 0], [0, 0, 0, 5]]

[[1, 2, 'B'], [0, 1, 'R'], [1, 1, 'P'], [3, 0, 'N']]


Output 2:

[[[3,0], [1,1]], [[0,1], [1,1]], [[1,1], [1,2]]]


Input 3:

. N R .
B . . .
N . . B
. . P .

.NR.B...N..B..P.

[['.', 'N', 'R', '.'], ['B', '.', '.', '.'], ['N', '.', '.', 'B'], ['.', '.', 'P', '.']]

[[0, 5, 3, 0], [4, 0, 0, 0], [5, 0, 0, 4], [0, 0, 6, 0]]

[[1, 3, 'N'], [2, 3, 'R'], [0, 2, 'B'], [0, 1, 'N'], [3, 1, 'B'], [2, 0, 'P']]


Output 3:

[[[2,0], [3,1]], [[0,1], [1,3]], [[0,2], [1,3]], [[2,3], [1,3]], [[3,1], [1,3]]]


Input 4:

. . . N
. . . R
R B B .
N P P .

...N...RRBB.NPP.

[['.', '.', '.', 'N'], ['.', '.', '.', 'R'], ['R', 'B', 'B', '.'], ['N', 'P', 'P', '.']]

[[0, 0, 0, 5], [0, 0, 0, 3], [3, 4, 4, 0], [5, 6, 6, 0]]

[[3, 3, 'N'], [3, 2, 'R'], [0, 1, 'R'], [1, 1, 'B'], [2, 1, 'B'], [0, 0, 'N'], [1, 0, 'P'], [2, 0, 'P']]


Output 4:

[[[2,1], [3,2]], [[1,1], [3,3]], [[3,2], [1,0]], [[3,3], [0,0]], [[0,1], [0,0]], [[0,0], [1,0]], [[1,0], [2,0]]]


Input 5:

P . . .
. R . .
R . R .
. R . .

P....R..R.R..R..

[['P', '.', '.', '.'], ['.', 'R', '.', '.'], ['R', '.', 'R', '.'], ['.', 'R', '.', '.']]

[[6, 0, 0, 0], [0, 3, 0, 0], [3, 0, 3, 0], [0, 3, 0, 0]]

[[0, 3, 'P'], [1, 2, 'R'], [0, 1, 'R'], [2, 1, 'R'], [1, 0, 'R']]


Output 5:

[[[0,3], [1,2]], [[1,2], [2,1]], [[2,1], [1,0]], [[1,0], [0,1]]]


Input 6:

. P . N
K . . .
. . B .
. . R Q

.P.NK.....B...RQ

[['.', 'P', '.', 'N'], ['K', '.', '.', '.'], ['.', '.', 'B', '.'], ['.', '.', 'R', 'Q']]

[[0, 6, 0, 5], [1, 0, 0, 0], [0, 0, 4, 0], [0, 0, 3, 2]]

[[1, 3, 'P'], [3, 3, 'N'], [0, 2, 'K'], [2, 1, 'B'], [2, 0, 'R'], [3, 0, 'Q']]


Output 6:

[[[3,0], [2,0]], [[2,0], [2,1]], [[3,3], [2,1]], [[2,1], [1,3]], [[0,2], [1,3]]]

• there is a little mistake in output 1, it should be [[[2,0], [1,1]], [[1,1], [3,3]]] Aug 19, 2016 at 8:33
• Also, as an additional note, the king is really a Mann (can be captured, but has the same move rules) (Fairy chess nomenclature is fun) Aug 19, 2016 at 9:21
• @Damien: Good spot! Thanks. Aug 19, 2016 at 12:31
• Is it OK to include the piece symbol in the output? Such as: [["R", [2, 0], [1, 1]], ["N", [1, 1], [3, 3]]] Aug 19, 2016 at 20:44
• @Arnauld: Yes, that would be okay. Somewhat strange though since you're listing the piece that's captured, not the capturing piece. Aug 19, 2016 at 21:38

Returns a list of all solutions. Each solution is a list of moves. Returns an empty list if there is no solution.

Saved 4 bytes Thanks to Lynn.

Try it online

m"P"=[2]
m"N"=[5]
m"K"=[1,2]
m"R"=[1,4,9]
m"B"=[2,8,18]
m _=m"B"++m"R"
l%x=[z|z<-l,fst z/=x]
f[_]=[[]]
f l=[(i,j):r|(i@(s,t),a)<-l,(j@(u,v),_)<-l,(s-u)^2+(t-v)^2elemm a,r<-f$(j,a):l%i%j]  Usage: main = do print$ f [((3, 3), "N"), ((1, 1), "R")]
putStrLn""
mapM_ print $f [((3, 3), "N"), ((1, 1), "R"), ((2, 0), "B")] putStrLn"" mapM_ print$ f [((1, 2), "B"), ((0, 1), "R"), ((1, 1), "P"), ((3, 0), "N")]
putStrLn""
mapM_ print $f [((1, 3), "P"), ((3, 3), "N"), ((0, 2), "K"), ((2, 1), "B"), ((2, 0), "R"), ((3, 0), "Q")]  Output: [] [((2,0),(1,1)),((1,1),(3,3))] [((3,0),(1,1)),((0,1),(1,1)),((1,1),(1,2))] [((1,3),(0,2)),((3,3),(2,1)),((2,1),(0,2)),((3,0),(2,0)),((2,0),(0,2))] [((1,3),(0,2)),((3,3),(2,1)),((3,0),(2,1)),((2,1),(2,0)),((2,0),(0,2))] [((1,3),(0,2)),((3,3),(2,1)),((3,0),(2,0)),((2,0),(0,2)),((2,1),(0,2))] [((1,3),(0,2)),((3,3),(2,1)),((3,0),(2,0)),((2,1),(0,2)),((2,0),(0,2))] [((1,3),(0,2)),((2,0),(2,1)),((3,0),(2,1)),((3,3),(2,1)),((2,1),(0,2))] [((1,3),(0,2)),((3,0),(2,1)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(0,2))] [((1,3),(0,2)),((3,0),(2,0)),((2,0),(0,2)),((3,3),(2,1)),((2,1),(0,2))] [((1,3),(0,2)),((3,0),(2,0)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(0,2))] [((1,3),(0,2)),((3,0),(2,0)),((3,3),(2,1)),((2,1),(0,2)),((2,0),(0,2))] [((1,3),(0,2)),((3,0),(2,0)),((3,3),(2,1)),((2,0),(0,2)),((2,1),(0,2))] [((3,3),(2,1)),((2,1),(1,3)),((3,0),(2,0)),((2,0),(0,2)),((0,2),(1,3))] [((3,3),(2,1)),((2,1),(0,2)),((1,3),(0,2)),((3,0),(2,0)),((2,0),(0,2))] [((3,3),(2,1)),((2,1),(0,2)),((3,0),(2,0)),((2,0),(0,2)),((0,2),(1,3))] [((3,3),(2,1)),((2,1),(0,2)),((3,0),(2,0)),((2,0),(0,2)),((1,3),(0,2))] [((3,3),(2,1)),((2,1),(0,2)),((3,0),(2,0)),((1,3),(0,2)),((2,0),(0,2))] [((3,3),(2,1)),((1,3),(0,2)),((2,1),(0,2)),((3,0),(2,0)),((2,0),(0,2))] [((3,3),(2,1)),((1,3),(0,2)),((3,0),(2,1)),((2,1),(2,0)),((2,0),(0,2))] [((3,3),(2,1)),((1,3),(0,2)),((3,0),(2,0)),((2,0),(0,2)),((2,1),(0,2))] [((3,3),(2,1)),((1,3),(0,2)),((3,0),(2,0)),((2,1),(0,2)),((2,0),(0,2))] [((3,3),(2,1)),((3,0),(2,1)),((2,1),(2,0)),((2,0),(0,2)),((0,2),(1,3))] [((3,3),(2,1)),((3,0),(2,1)),((2,1),(2,0)),((2,0),(0,2)),((1,3),(0,2))] [((3,3),(2,1)),((3,0),(2,1)),((2,1),(2,0)),((1,3),(0,2)),((2,0),(0,2))] [((3,3),(2,1)),((3,0),(2,1)),((1,3),(0,2)),((2,1),(2,0)),((2,0),(0,2))] [((3,3),(2,1)),((3,0),(2,0)),((2,0),(0,2)),((0,2),(1,3)),((2,1),(1,3))] [((3,3),(2,1)),((3,0),(2,0)),((2,0),(0,2)),((2,1),(0,2)),((1,3),(0,2))] [((3,3),(2,1)),((3,0),(2,0)),((2,0),(0,2)),((2,1),(1,3)),((0,2),(1,3))] [((3,3),(2,1)),((3,0),(2,0)),((2,0),(0,2)),((1,3),(0,2)),((2,1),(0,2))] [((3,3),(2,1)),((3,0),(2,0)),((2,1),(1,3)),((2,0),(0,2)),((0,2),(1,3))] [((3,3),(2,1)),((3,0),(2,0)),((2,1),(0,2)),((2,0),(0,2)),((0,2),(1,3))] [((3,3),(2,1)),((3,0),(2,0)),((2,1),(0,2)),((2,0),(0,2)),((1,3),(0,2))] [((3,3),(2,1)),((3,0),(2,0)),((2,1),(0,2)),((1,3),(0,2)),((2,0),(0,2))] [((3,3),(2,1)),((3,0),(2,0)),((1,3),(0,2)),((2,0),(0,2)),((2,1),(0,2))] [((3,3),(2,1)),((3,0),(2,0)),((1,3),(0,2)),((2,1),(0,2)),((2,0),(0,2))] [((0,2),(1,3)),((2,1),(3,0)),((2,0),(3,0)),((3,0),(3,3)),((3,3),(1,3))] [((0,2),(1,3)),((2,0),(2,1)),((3,0),(2,1)),((3,3),(2,1)),((2,1),(1,3))] [((0,2),(1,3)),((3,0),(2,1)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(1,3))] [((0,2),(1,3)),((3,0),(2,0)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(1,3))] [((2,1),(3,0)),((0,2),(1,3)),((2,0),(3,0)),((3,0),(3,3)),((3,3),(1,3))] [((2,1),(3,0)),((2,0),(3,0)),((3,0),(3,3)),((3,3),(1,3)),((0,2),(1,3))] [((2,1),(3,0)),((2,0),(3,0)),((3,0),(3,3)),((0,2),(1,3)),((3,3),(1,3))] [((2,1),(3,0)),((2,0),(3,0)),((0,2),(1,3)),((3,0),(3,3)),((3,3),(1,3))] [((2,0),(2,1)),((1,3),(0,2)),((3,0),(2,1)),((3,3),(2,1)),((2,1),(0,2))] [((2,0),(2,1)),((0,2),(1,3)),((3,0),(2,1)),((3,3),(2,1)),((2,1),(1,3))] [((2,0),(2,1)),((3,0),(2,1)),((1,3),(0,2)),((3,3),(2,1)),((2,1),(0,2))] [((2,0),(2,1)),((3,0),(2,1)),((3,3),(2,1)),((2,1),(1,3)),((0,2),(1,3))] [((2,0),(2,1)),((3,0),(2,1)),((3,3),(2,1)),((2,1),(0,2)),((1,3),(0,2))] [((2,0),(2,1)),((3,0),(2,1)),((3,3),(2,1)),((1,3),(0,2)),((2,1),(0,2))] [((2,0),(2,1)),((3,0),(2,1)),((3,3),(2,1)),((0,2),(1,3)),((2,1),(1,3))] [((2,0),(2,1)),((3,0),(2,1)),((0,2),(1,3)),((3,3),(2,1)),((2,1),(1,3))] [((3,0),(3,3)),((3,3),(1,3)),((1,3),(0,2)),((0,2),(2,0)),((2,0),(2,1))] [((3,0),(2,1)),((2,1),(2,0)),((2,0),(0,2)),((0,2),(1,3)),((1,3),(3,3))] [((3,0),(2,1)),((1,3),(0,2)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(0,2))] [((3,0),(2,1)),((0,2),(1,3)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(1,3))] [((3,0),(2,1)),((2,0),(2,1)),((1,3),(0,2)),((3,3),(2,1)),((2,1),(0,2))] [((3,0),(2,1)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(1,3)),((0,2),(1,3))] [((3,0),(2,1)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(0,2)),((1,3),(0,2))] [((3,0),(2,1)),((2,0),(2,1)),((3,3),(2,1)),((1,3),(0,2)),((2,1),(0,2))] [((3,0),(2,1)),((2,0),(2,1)),((3,3),(2,1)),((0,2),(1,3)),((2,1),(1,3))] [((3,0),(2,1)),((2,0),(2,1)),((0,2),(1,3)),((3,3),(2,1)),((2,1),(1,3))] [((3,0),(2,0)),((2,0),(0,2)),((0,2),(1,3)),((3,3),(2,1)),((2,1),(1,3))] [((3,0),(2,0)),((2,0),(0,2)),((1,3),(0,2)),((3,3),(2,1)),((2,1),(0,2))] [((3,0),(2,0)),((2,0),(0,2)),((3,3),(2,1)),((2,1),(0,2)),((1,3),(0,2))] [((3,0),(2,0)),((2,0),(0,2)),((3,3),(2,1)),((2,1),(1,3)),((0,2),(1,3))] [((3,0),(2,0)),((2,0),(0,2)),((3,3),(2,1)),((0,2),(1,3)),((2,1),(1,3))] [((3,0),(2,0)),((2,0),(0,2)),((3,3),(2,1)),((1,3),(0,2)),((2,1),(0,2))] [((3,0),(2,0)),((2,0),(2,1)),((1,3),(0,2)),((3,3),(2,1)),((2,1),(0,2))] [((3,0),(2,0)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(1,3)),((0,2),(1,3))] [((3,0),(2,0)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(0,2)),((1,3),(0,2))] [((3,0),(2,0)),((2,0),(2,1)),((3,3),(2,1)),((1,3),(0,2)),((2,1),(0,2))] [((3,0),(2,0)),((2,0),(2,1)),((3,3),(2,1)),((0,2),(1,3)),((2,1),(1,3))] [((3,0),(2,0)),((2,0),(2,1)),((0,2),(1,3)),((3,3),(2,1)),((2,1),(1,3))] [((3,0),(2,0)),((1,3),(0,2)),((2,0),(0,2)),((3,3),(2,1)),((2,1),(0,2))] [((3,0),(2,0)),((1,3),(0,2)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(0,2))] [((3,0),(2,0)),((1,3),(0,2)),((3,3),(2,1)),((2,1),(0,2)),((2,0),(0,2))] [((3,0),(2,0)),((1,3),(0,2)),((3,3),(2,1)),((2,0),(0,2)),((2,1),(0,2))] [((3,0),(2,0)),((3,3),(2,1)),((2,1),(1,3)),((2,0),(0,2)),((0,2),(1,3))] [((3,0),(2,0)),((3,3),(2,1)),((2,1),(0,2)),((2,0),(0,2)),((0,2),(1,3))] [((3,0),(2,0)),((3,3),(2,1)),((2,1),(0,2)),((2,0),(0,2)),((1,3),(0,2))] [((3,0),(2,0)),((3,3),(2,1)),((2,1),(0,2)),((1,3),(0,2)),((2,0),(0,2))] [((3,0),(2,0)),((3,3),(2,1)),((2,0),(0,2)),((0,2),(1,3)),((2,1),(1,3))] [((3,0),(2,0)),((3,3),(2,1)),((2,0),(0,2)),((2,1),(0,2)),((1,3),(0,2))] [((3,0),(2,0)),((3,3),(2,1)),((2,0),(0,2)),((2,1),(1,3)),((0,2),(1,3))] [((3,0),(2,0)),((3,3),(2,1)),((2,0),(0,2)),((1,3),(0,2)),((2,1),(0,2))] [((3,0),(2,0)),((3,3),(2,1)),((1,3),(0,2)),((2,1),(0,2)),((2,0),(0,2))] [((3,0),(2,0)),((3,3),(2,1)),((1,3),(0,2)),((2,0),(0,2)),((2,1),(0,2))] [((3,0),(2,0)),((0,2),(1,3)),((2,0),(2,1)),((3,3),(2,1)),((2,1),(1,3))]  • Beautiful solution! Inlining ! saves a few bytes: f l=[(i,j):r|(i@(s,t),a)<-l,(j@(u,v),_)<-l%i,r<-f$(j,a):l%i%j,(s-u)^2+(t-v)^2elemm a]
– Lynn
Aug 18, 2016 at 16:18
• Nice! What does the output look like? Aug 18, 2016 at 17:00
• [[((2,0),(1,1)),((1,1),(3,3))]]. A list of solutions, where a solution is a list of moves, where a move is ((x1,y1),(x2,y2)).
– Lynn
Aug 18, 2016 at 18:21
• m"P"=[1] Shouldn't it be 2?
– ngn
Aug 20, 2016 at 12:37
• Yes, of course! Thanks Aug 21, 2016 at 8:19

## Javascript (ES6), 372361 358 bytes

It (still) needs some optimizing. But here is a first 2nd 3rd attempt.

b=>{for(n=-4,b=[...b];n<36;b.splice(n+=8,0,0,0,0,0));l=[];(M=(P,u,Z,z,L)=>{for(P=u=n;u--;)
for((z=[640,164928,641,259,899,898]["PNBRQK".indexOf(b[u])])&&P++,L=1,s=z&1;z>>=1;L++)for(Z
=u;z&1&!((Z+=L)&n)&&(b[Z]<'A'||!(M(l.push([b[Z],[u&3,31-u>>3],b[u],[Z&3,31-Z>>3]]),b[Z]=b[u
],b[u]='.'),b[u]=b[Z],b[Z]=l.pop()[0]))&&s||(L=-L,Z=u,L<0););P-37||console.log(l)})()}


Output format:

// Puzzle #1
[["B", [2, 0], "R", [1, 1]], ["B", [1, 1], "N", [3, 3]]]


Example:

let F =
b=>{for(n=-4,b=[...b];n<36;b.splice(n+=8,0,0,0,0,0));l=[];(M=(P,u,Z,z,L)=>{for(P=u=n;u--;)for((z=[640,164928,641,259,899,898]["PNBRQK".indexOf(b[u])])&&P++,L=1,s=z&1;z>>=1;L++)for(Z=u;z&1&!((Z+=L)&n)&&(b[Z]<'A'||!(M(l.push([b[Z],[u&3,31-u>>3],b[u],[Z&3,31-Z>>3]]),b[Z]=b[u],b[u]='.'),b[u]=b[Z],b[Z]=l.pop()[0]))&&s||(L=-L,Z=u,L<0););P-37||console.log(l)})()}

console.log("Puzzle #1");
F("...N.....R....B.");
console.log("Puzzle #2");
F(".....B..RP.....N");