Minimal number of jumps to reach a square

Question

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

Answer 1

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

Answer 2

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(' "/3OS`b').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).

Answer 3

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),
        d,TOCOL(IF((b<9)*(c<9),ADDRESS(b,c,4),NA()),2),
        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#.

Answer 4

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.

Answer 5

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

Answer 6

K (ngn/k), 62 bytes

{0^*&~^?[;z]'64{?,/x@y}[i!i@&'(4=*/4#)''i-\:/:i:(+!8 8)^y]\,x}

Try it online!

Answer 7

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.

Answer 8

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)n`mod`n

Attempt This Online!

Answer 9

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
}