The Attack of the Knights

Question

Objective

You have two knights on a standard chessboard labelled 1-8 and A-H, one knight is located at 1C and the other at 2G. You have to write a program in the language of your choosing that accepts a set of coordinates from stdin, like 2C, and then calculates which of the two knights you have to move in order to capture the enemy pawn at the provided coordinates with the least amount of moves assuming it is standing still. The program must also output which are these moves that the knight has to make.

Example Usage

# echo 1C|./faster
Move Knight: 1C
Moves:

Also

# echo 3B|./faster
Move Knight: 1C
Moves: 1C -> 3B

One more

# echo 5A|./faster
Move Knight: 1C
Moves: 1C -> 3B
Moves: 3B -> 5A

Output shall be exactly as shown.

Useful Resources

Knight's Tour

Bonuses

You get -50 Bytes if your program is expandable and works with N knights.

Answer 1

Mathematica 1183 483 bytes (or 190) bytes

Approach 1

240-50 (bonus) = 190 bytes

The knight's tour can be represented as a graph. So the issue becomes simply to find the shortest path from each knight to the pawn. Mathematica offers both KnightTourGraph and FindShortestPath as built-in functions.

w@p_:=Characters@p/.{r_,s_}:>(ToCharacterCode[s][[1]]-65)*8+ToExpression@r
z@v_:=ToString@(v~Mod~8/.{0->8})<>FromCharacterCode[Quotient[v-1,8]+65]
p_~h~k_:=Row[SortBy[(z/@FindShortestPath[8~KnightTourGraph~8,#,w@p])&/@w/@k,Length][[1]],"->"]

Examples

h["5A",{"1C","2G"}]

1C -> 3B -> 5A

h["8G",{"1C","2G"}]

2G -> 3E -> 5D -> 7E -> 8G

---

Approach 2

(533-50 (bonus)= 483 bytes)

Here the knight's tour graph is constructed without using KnightTourGraph.

s@v_:=
Sort[{v,#}]/.{{a_, b_}:>UndirectedEdge[a,b]}&/@(
If[If[#4==1,Greater,Less][Mod[v-1,8]+1,#1]&&If[#5==1,Greater,Less][Quotient[v-1,8]+1,#2],v+#3,Nothing]&@@@{{1,2,-17,1,1},{8,2,-15,0,1},{2,1,-10,1,1},{7,1,-6,0,1},{2,8,6,1,0},{7,8,10,0,0},{1,7,15,1,0},{8,7,17,0,0}})   
w@p_:=Characters[p]/.{r_,q_}:>(ToCharacterCode[q][[1]]-65)*8+ToExpression@r
z@v_:=ToString@(Mod[v,8]/.{0 -> 8})<>FromCharacterCode[Quotient[v-1,8]+65]
p_~f~k_:=Row[SortBy[(z/@FindShortestPath[Graph[Range@64,Union@Flatten[s/@Range@64]],#,w@p])&/@w/@k,Length][[1]],"->"]

---

Explanation

Below are two views of the chessboard. On the left, each chessboard position corresponds to vertex bearing an integer name. On the right, the positions have been labelled according to the convention suggested by the OP.

In both figures, White sits on the right, Black sits on the left.

Legal moves of a knight are paths along a knight tour graph.

The function, s, generates all 512 moves (as if each square allowed for 8 knight moves), eliminates inverses, and then weeds out the moves that would land off the board. There are 168 edges on the graph.

edges consists of a list of elements of the form, UndirectedEdge[a,b]. For instance, the edge, UndirectedEdge[1,11]corresponds to the idea that a knight at vertex 1, that is, at "A1" in standard notation, may jump to vertex 11, or "B3", and vice-versa.

toVertex takes a position (see right board) and returns a vertex (see left board). For instance toVertex["3H"] returns 59.

toChessPosition does the opposing conversion, namely from a vertex to a chess position.

vertexNames is a list of replacements: {1->"1A",2->"2A"...64->"8H"}. This is only needed for the right chessboard figure shown above.

numberedKnightsTouris the graph displayed above on the left.

chessKnightsTouris the graph displayed above on the right.

The graphs are constructed using the above-defined vertices and edges.

findShortestPath receives the position of the pawn and a list of positions of the knights and finds the shortest path along the graph from a knight to the pawn.

    s@v_:=
Sort[{v,#}]/.{{a_, b_}:>UndirectedEdge[a,b]}&/@(
If[If[#4==1,Greater,Less][Mod[v-1,8]+1,#1]&&If[#5==1,Greater,Less]
edges=Union@Flatten[s/@Range@64];
toVertex[p_]:=Characters[p]/.{rank_,file_}:> (ToCharacterCode[file][[1]]-65)*8+ToExpression[rank]
toChessPosition[v_]:=ToString@(Mod[v,8]/.{0->8})<>FromCharacterCode[Quotient[v-1,8]+65]
vertexNames=Thread[Range@64->(toChessPosition[#]&/@Range[64])];
numberedKnightsTour=Graph[Range@64,edges,VertexLabels->"Name",GraphLayout->"SpringEmbedding"];
vertexNames=Thread[Range[64]->(toChessPosition[#]&/@Range[64])];
chessKnightsTour=Graph[Range@64,edges,ImageSize->Large,VertexLabels-> vertexNames,GraphLayout->"SpringEmbedding"];
GraphicsGrid[{{numberedKnightsTour,chessKnightsTour}},PlotLabel->"For each board below, \nWhite sits at Right, Black at Left\nNumbers refers to rank, letters refer to file",ImageSize->Large]
    findShortestPath[pawn_,knights_]:=Row[SortBy[(toChessPosition/@FindShortestPath[chessKnightsTour,#,toVertex@pawn])&/@toVertex/@knights,Length][[1]],"->"]

---