# Minimal number of jumps to reach a square

A Knight in chess moves two squares vertically and one square horizontally, or two squares horizontally and one square vertically (with both forming the shape of a capital L)

Given a Knight current square in a chess board and an array of unavailable squares, calculate the minimum number of valid jumps required to reach a target square. If no route is available to reach the required target return 0.

A valid jump is a move that:

• Does not go out of the board (8x8 square board)
• Does not overlap with another piece
• Follows the Knight L shape move pattern

Input

Knight square, array of occupied squares, target square. Input might look like:

f("b3", ["c4", "h7", "g5", "a8"], "b7")

• You can use a set of coordinates instead of chess algebraic notation. It can be 0 or 1-index. Example: b3 -> (2,3) or b3 -> (1,2)

• You can assume that Knight Square != Target Square for every input.

• You can assume every input square is valid and non overlapping

• Input values can be taken in any order you'd like

Output

Minimal number of valid jumps to reach a square, or 0 in case no route can be found

Test Cases

"e3", [], "f5" -> 1
"e3", [], "f6" -> 2
"c4", [], "f6" -> 3
"g1", ["f3", "g3"], "h4" -> 4
"c4", ["d6", "b6", "e5", "e3", "e4"], "f6" -> 5
"a1", [], "h8" -> 6
"g1", ["h3","h5","g2","g3","g6","f3", "e5", "e6", "d4", "d5", "c1", "c3", "c5", "b2"], "b7" -> 7
"h1", ["f2", "g3"], "h3" -> 0
"d4", ["b3", "b5", "c2", "c6", "e2", "e6", "f3", "f5"], "a8" -> 0

• Pretty much related Aug 29 at 13:49
• Can we take input as [x,y] tuples instead of strings? Aug 29 at 13:49
• are you sure about the 6th test-case g1,e2,c1,b3,a5,b7 seems to be a valid path in only 5 jumps Aug 29 at 14:12
• @bsoelch my mistake, I was missing one unavailable square. Should be fine now Aug 29 at 14:17
• b3 should be (2,3) when 1-indexed and (1,2) when 0-indexed. Sep 1 at 2:13

# Python, 154 bytes

-17 bytes, thanks to The Thonnu

def f(s,b,t,k=0):
p=s,
while(t in p)*64<64>k:p=[[u,v]for i in range(64)if([u:=i//8,v:=i%8]in b)<any((x-u)**2+(y-v)**2==5for x,y in p)];k+=1
return k%64


Attempt This Online!

Goes through all reachable fields until target is reached, aborts after 64 steps and returns 0

• 163 bytes Aug 29 at 15:52
• 64 steps are more than needed but I guess cutting this by a few doesn't help with golfing as long as it is still a 2-digit number and one can create examples where the minimal number of jumps is bigger than 10. Aug 30 at 7:03

# JavaScript (Node.js), 143 bytes

Expects [source, target, occupied_0, occupied_1, ...] where each square is a pair of 0-indexed coordinates.

f=(a,n)=>(g=(n,s)=>(i=b.indexOf(s))>1|s&136?0:i>0|Buffer(' "/3OSb').some(v=>n&&g(n-1,s+v-65)))(n,...b=a.map(([x,y])=>x|y<<4))?n:n>9?0:f(a,-~n)


Try it online!

### How?

This is internally using the 0x88 encoding. Converting the input to this format is a bit costly, but it makes basically everything else easier and shorter (moves, square comparisons and out-of-board detections).

• Out of curiosity: is this really shorter than using your answer to the other challenge for the first input and then indexing with the second input? Aug 30 at 10:31
• @LuisMendo Good question. :-) I'll have a look later. Aug 30 at 11:42

# Excel, 236 bytes

Define z as:

=LAMBDA(p,q,
LET(
a,OFFSET(
INDIRECT(p),
{-2,-2,-1,-1,1,1,2,2},
{-1,1,-2,2,-2,2,-1,1}
),
b,ROW(a),
c,COLUMN(a),
e,FILTER(d,ISNA(XMATCH(d,$B1#))), IF(SUM(N(e=$C1))>0,q+1,z(e,q+1))
)
)


Within the worksheet:

=IFERROR(z($A1,),)  Knight square in cell A1, target square in cell C1 and occupied squares in spilled, vertical range B1#. # Charcoal, 59 bytes Ｆ…β⁸Ｆ⁸⊞υ⁺ι⊕κ≔⟦θ⟧θＷ∧¬№θζΦ⁻υ⁺θη⊙θ⁼⁵ΣＸＥμ⁻℅ξ℅§κπ²«→≔⁺θιθ»Ｉ∧№θζⅈ  Try it online! Link is to verbose version of code. Explanation: Ｆ…β⁸Ｆ⁸⊞υ⁺ι⊕κ  Create a list of all valid chess board squares. ≔⟦θ⟧θ  Start with one reachable square. Ｗ∧¬№θζΦ⁻υ⁺θη⊙θ⁼⁵ΣＸＥμ⁻℅ξ℅§κπ²«  While the target has not been reached and there are still more squares that can be reached... →  ... increment the count of jumps, and... ≔⁺θιθ  ... append the newly reachable squares to the list of reachable squares. »Ｉ∧№θζⅈ  Output the count of jumps or 0 if the target was not reached. 51 bytes by taking input as Gaussian integers: ≔⟦θ⟧θＷ∧¬№θζΦ⁻ΣＥ⁸Ｅ⁸⁺κ×μＩ1j⁺θη⊙θ⁼₂⁵↔⁻μκ«→≔⁺θιθ»Ｉ∧№θζⅈ  Attempt This Online! Link is to verbose version of code. # Scala, 378 336 bytes Port of @bsoelch's Python answer in Scala. Saved 42 bytes thanks to the comment of @Kjetil S Golfed version. Try it online! def f(s:(Int,Int),b:Seq[(Int,Int)],t:(Int,Int),K:Int=0)={var p=Seq(s);var k=K;while(!p.contains(t)&&k<64){p=(for(i<-0 until 64;u=i/8;v=i%8;if !b.contains((u,v))&&p.exists{case(x,y)=>(x-u)*(x-u)+(y-v)*(y-v)==5})yield(u,v)).toList;k+=1};k%64} def C(s:String)=(s(0)-97,s(1)-49) def h(a:String,b:List[String],c:String)=f(C(a),b.map(C),C(c))  Ungolfed version. Try it online! object Main { def f(s: (Int, Int), b: List[(Int, Int)], t: (Int, Int), k: Int = 0): Int = { var p = List(s) var kVar = k while (!p.contains(t) && kVar < 64) { p = (for (i <- 0 until 64; u = i / 8; v = i % 8; if !b.contains((u, v)) && p.exists { case (x, y) => (x - u) * (x - u) + (y - v) * (y - v) == 5 }) yield (u, v)).toList kVar += 1 } kVar % 64 } def coord(s: String): (Int, Int) = { ("abcdefgh".indexOf(s.charAt(0)), s.charAt(1).asDigit - 1) } def helper(a: String, b: List[String], c: String): Int = { f(coord(a), b.map(coord), coord(c)) } def main(args: Array[String]): Unit = { println(helper("e3", List(), "f5")) //-> 1 println(helper("e3", List(), "f6")) //-> 2 println(helper("c4", List(), "f6")) //-> 3 println(helper("g1", List("f3", "g3"), "h4")) //-> 4 println(helper("c4", List("d6", "b6", "e5", "e3", "e4"), "f6")) //-> 5 println(helper("a1", List(), "h8")) //-> 6 println(helper("g1", List("h3","h5","g2","g3","g6","f3", "e5", "e6", "d4", "d5", "c1", "c3", "c5", "b2"), "b7")) //-> 7 println(helper("h1", List("f2", "g3"), "h3")) //-> 0 println(helper("d4", List("b3", "b5", "c2", "c6", "e2", "e6", "f3", "f5"), "a8")) //-> 0 } }  • You can shave off 24 bytes by replacing "abcdefgh".indexOf(s(0)) with s(0)-97 and s(1).asDigit-1 with s(1)-49 Sep 1 at 20:17 • ...and 18 bytes by removing return type :(Int,Int) and :Int twice. Sep 1 at 20:29 # K (ngn/k), 62 bytes {0^*&~^?[;z]'64{?,/x@y}[i!i@&'(4=*/4#)''i-\:/:i:(+!8 8)^y]\,x}  Try it online! # J, 59 bytes 1 :'1{.[:I.[e."1(u-.~,j./~i.8)(]~.@,&;[<@#~2j1=&|-/~)^:a:]'  Attempt This Online! Takes input as complex numbers. To handle all 3 args, we use a J adverb which modifies the list of illegal positions, and takes the target and start positions as the left and right args, respectively. • (u-.~,j./~i.8) Generate the full board minus the illegal spaces • (]~.@,&;[<@#~2j1=&|-/~)^:a:] Collecting each step's results until you reach a fixed point, starting the initial square, find all legal spaces that are $$\\sqrt{5}\$$ away from the current positions. In this way, we spider out stepwise to every reachable position • [e."1 For each steps results, is the target position in that list? Now our list of lists (the step results) will become a single 0-1 list, with the first 1 representing the index we seek • [:I. All 1 indexes. Returns empty list for no matches. • 1{. Take the first. Exactly what we need, and since taking 1 from the empty list returns 0, it also handles the no match case. # Haskell, 192 bytes n=99 q=[-1,1] (#)=elem g a b p c=last$last(1+g[w|s<-a,x<-[1,2],y<-q,z<-q,w<-[zipWith(+)s[y*x,z*(3-x)]],all(elem[0..7])w&&not(w#b)]b(p++a)c:[n|all(#p)a]):[0|c#a]
f a b c= min(g[a]b[]c)nmodn


Attempt This Online!

# Perl 5, 166 bytes

sub{($s,$e,%o)=@_;@w=(0,$s);while(($n,$s,@w)=@w){$s-$e||last,push@w,map{$n+1,$_}grep{($a,$b,$c,$d)=map{$_>>3,$_%8}$s,$_;!(($a-$c)**2+($b-$d)**2-5||$o{$_}++)}0..63}$n}


Try it online!

sub steps {
($s,$e,%o)=@_;        #start, end, occupied set as hash from input args in @_
@w=(0,$s); #initial work (steps,square) while(($n,$s,@w)=@w){ #while work left to be done$s-$e||last, #bail if current square$s equals $e end square push@w, #register new work/new squares to be checked map{$n+1,$_} # (new steps, new square) grep{ #filter ($a,$b,$c,$d) #coords of current square ($a,$b) =map{$_>>3,$_%8}$s,$_; #...and potential new square ($c,$d) !(($a-$c)**2+($b-$d)**2-5 #pythagorean horsyness check of new vs current ||$o{$_}++) #...non-occupied new squares #...and register new square as occupied #...with ++ to not enter it again } 0..63 #loop through potential new squares }$n                              #return n steps from last work
}
`