Given two different positions on a chess board and the type of piece, output the minimum number of moves it will take for that piece to go from one position to another.

Rules

The given piece can be King,Queen,Rook,Knight and Bishop. (This input can be taken as any 5 unique characters)

The 2 positions can be taken in any convenient format,

Example:
a8 b8 c8 d8 ... h8
a7 b7 c7 d7 ... h7
...
...
a1 b1 c1 d1 ... h1

In case the piece cannot reach there, output anything other than a positive integer.

Examples

i/p ---- o/p
King
a1,a4    3
a1,h6    7
b3,h5    6

Queen
a1,a4    1
a1,h6    2
b3,f7    1

Rook
a1,a4    1
a1,h6    2
h2,c7    2

Knight
a1,a4    3
a1,h6    4
b2,d3    1
b2,c3    2
b3,c3    3
a1,b2    4

Bishop
a1,a4    -1
a1,h6    2
b2,d3    -1
e1,h4    1
  • 1
    Why do King need 12 to a1-h6? Can't King go diag? – l4m2 Nov 26 at 7:40
  • @l4m2, corrected – Vedant Kandoi Nov 26 at 7:43
  • 1
    @ngn, you can use 0 to indicate unreachability, the 2 positions will always be different. – Vedant Kandoi Nov 26 at 11:13
  • 5
    All knight distances – Arnauld Nov 26 at 15:37
  • 1
    Some definitions (such as ISO-80000-2) of natural numbers include 0. Recommend substituting with "positive integer". – Rogem Nov 28 at 13:48

JavaScript (Node.js), 183 180 179 bytes

with(Math)(a,b,c,d,t,x=abs(a-c),y=abs(b-d),v=x<y?y:x,q=0|.9+max(/[18][18]/.test(a+b+9+c+d)-v?x/2:3,y/2,x*y?x*y-4?(x+y)/3:3:2))=>t?t==2&x+y?0:t&1>x*y|t/2&x==y?1:t<4?2:v:q+(q+x+y&1)

Try it online!

So long for edge case, thank Arnauld for checking. Knight test

  • @Arnauld Well corner really cost – l4m2 Nov 26 at 14:02
  • I think you might be able to save a byte by replacing the last max with a ternary. – Shaggy Nov 26 at 14:07
  • 170 bytes (I think. I'm on my phone.) – Shaggy Nov 26 at 14:16
  • @Shaggy was what Arnauld pointn that wrong – l4m2 Nov 26 at 14:18

APL (Dyalog Classic), 117 107 105 103 98 97 95 92 89 87 bytes

{(⍎⍺⊃'⌈/' '≢∘∪~∘0' '+/×' '{⍺∊⍵:0⋄1+⍺∇i/⍨∨⌿2=|×/↑⍵∘.-i←,⍳8 8}/,¨⊂¨↓⍵' '≢∘∪×2=.|⊢')⊣|-⌿⍵}

Try it online!

left arg is piece type: 0=king, 1=queen, 2=rook, 3=knight, 4=bishop; right arg is a 2x2 matrix of coords, each row representing a position; returns 0 for unreachable

|-⌿⍵ computes the pair [abs(∆x),abs(∆y)]

(⍎⍺⊃...)⊣ chooses an expression from the "..." list; if it's a function, it's applied to |-⌿⍵; if it's a value (this happens only for a knight), makes sure to return it instead of |-⌿⍵

  • king: max (⌈/) of the abs ∆-s

  • queen: remove zeroes (~∘0) and count () unique ()

  • rook: sum (+/) of signa (monadic ×; 0 for 0, 1 for positive)

  • knight: {⍺∊⍵:0⋄1+⍺∇i/⍨∨⌿2=|×/↑⍵∘.-i←,⍳8 8}/,¨⊂¨↓⍵ - start with the initial position and recursively compute generations of knight moves until the final position is in the set; return recursion depth

  • bishop: are the parities of the two ∆-s equal? (2=.|⊢, equivalent to =/2|⊢) multiply the boolean result (0 or 1) by the count-unique (≢∘∪)

  • I love the ⍎⍺⊃. Very clever. – J. Sallé Nov 26 at 17:47
  • @J.Sallé thanks – ngn Nov 27 at 6:43

Java (JDK), 229 bytes

(p,a,b,c,d)->{c^=a/4*7;a^=a/4*7;d^=b/4*7;b^=b/4*7;int x=c<a?a-c:c-a,y=d<b?b-d:d-b,z=(x^=y^(y=y<x?y:x))-y;return p<1?x:p<2?z*y<1?1:2:p<3?2-z%2:p<4?x+y<2?3:(a<c?a+b:c+d)+x<2|x==2&z<1?4:z+2*Math.ceil((y-z)/(y>z?3:4.)):z<1?1:~z*2&2;}

Try it online!

Explanations

  • The board is a 0-based board.
  • The returned-value is an integer, represented as a double. There will never be any decimal part.

Code:

(p,a,b,c,d)->{                          // double-returning lambda.
                                        // p is the piece-type (0: king, 1: queen, 2: rook, 3: knight, 4: bishop)
                                        // a is the origin-X
                                        // b is the origin-Y
                                        // c is the destination-X
                                        // d is the destination-Y
 c^=a/4*7;a^=a/4*7;                     // Mirror board if origin is in the top part of the board
 d^=b/4*7;b^=b/4*7;                     // Mirror board if origin is in the left part of the board
 int x=c<a?a-c:c-a,                     // x is the X-distance between a and c
     y=d<b?b-d:d-b,                     // y is the Y-distance between b and d
     z=(x^=y^(y=y<x?y:x))-y;            // z is the delta between x and y
                                        // also, swap x and y if necessary so that x is the greater value.
               //    At this point,
               //     x      cannot be 0 (because the two positions are different)
               //     z<1    means the origin and destination are on the same diagonal
               //     y<1    means the origin and destination are on the same horizontal/vertical line
 return
  p<1?x:                                //  For a king, just take the max distance.
  p<2?z*y<1?1:2:                        //  For a queen, just move once if in direct line, or twice.
  p<3?2-z%2:                            //  For a rook, just move once if on the same horizontal or vertical line, or twice
  p<4?                                  //  For a knight, 
   x+y<2?3:                             //   Hardcode 3 if moving to the next horizontal/vertical square
   (a<c?a+b:c+d)+x<2|x==2&z<1?4:        //   Hardcode 4 if moving 2 cases in diagonal or one case in diagonal in a corner.
   z+2*Math.ceil((y-z)/(y>z?3:4.)):     //   Compute the number of moves necessary for the usual cases
  z<1?1:                                //  For a bishop, hardcode 1 if they are on the same diagonal
   ~z*2&2;                              //   Return 2 if they have the same parity else 0.
}

Credits

  • -2 bytes thanks to Arnauld, as well as for making me realize that I had an issue with all my corner-cases.

Charcoal, 108 bytes

F…β⁸F⁸⊞υ⁺ι⊕κ≔⟦⟦η⟧⟧δW¬№§δ±¹ζ⊞δΦυΦ§δ±¹⁼⁵ΣEμX⁻℅ξ℅§κπ²≔Eη↔⁻℅ι℅§ζκε≡θKI⌈εQI∨∨¬⌊ε⁼⊟ε⊟ε²RI∨¬⌊ε²BI∧¬﹪Σε²∨⁼⊟ε⊟ε²NI⊖Lδ

Try it online! Link is to verbose version of code. Explanation:

F…β⁸F⁸⊞υ⁺ι⊕κ

List all the 64 squares of the board into the predefined empty list variable.

≔⟦⟦η⟧⟧δ

Make a list of lists whose first entry is a list containing the start position.

W¬№§δ±¹ζ

Repeat until the last entry of the list contains the end position.

⊞δΦυΦ§δ±¹⁼⁵ΣEμX⁻℅ξ℅§κπ²

Filter all the board positions that are a knight's move away from any entry in the last entry of the list of lists and push that list to the list of lists. This includes positions previously visited but we weren't interested in them anyway, so we end up with a breadth first search of the board for the end position.

≔Eη↔⁻℅ι℅§ζκε

Calculate the absolute coordinate differences between the start and end positions.

≡θ

Select based on the input piece.

KI⌈ε

If it's a king then print the maximum absolute coordinate difference.

QI∨∨¬⌊ε⁼⊟ε⊟ε²

If it's a queen then print 2 unless the two differences are equal or one is zero.

RI∨¬⌊ε²

If it's a rook then print 2 unless one of the differences is zero.

BI∧¬﹪Σε²∨⁼⊟ε⊟ε²

If it's a bishop then print 0 if the squares are of opposite parity otherwise print 2 unless the two differences are equal.

NI⊖Lδ

If it's a knight then print the number of loops taken to find the end position.

Japt, 67 bytes

®ra
g[_rw}_â è}@=ã ü;@pUÌïVõ á ÈíaY})Ìde[TT]}a Ä}_è}_ra v *Zâ l}]gV

Try it online!

That was quite an experience. I took a lot of inspiration from the excellent APL Answer. I suspect there is a lot of golfing still possible especially in the Knight code.

The positions are the first input, in the form [[x1,x2],[y1,y2]]. It should work fine on [[y1,y2],[x1,x2]] as well. Piece selection is the second input, with 0=king, 1=queen, 2=knight, 3=rook, 4=bishop. Note that Knight and Rook are swapped compared to the APL answer.

Explanation:

®ra         :Turn absolute positions into relative movement and store in U
®           : For each of X and Y
 ra         : Get the absolute difference between the start position and the end position

g[...]gV    :Apply the appropriate function
 [...]      : A list of functions
      gV    : Get the one indicated by the second input
g           : Apply it to U

_rw}        :King function
 rw         : Get the maximum of X and Y

_â è}       :Queen function
 â          : Get unique elements
   è        : Count non-zero elements

@=ã ü;@pUÌï2õ á ÈíaY})Ìde[TT]}a Ä}  :Knight function
 =ã ü;                              : Wrap U twice (U -> [[U]])
      @                      }a Ä   : Repeat until True; return number of tries:
        UÌ                          :  Get the previous positions
          ï                         :  Cartesian product with:
           2õ                       :   The range [1,2]
              á                     :   All permutations, i.e. [[1,2],[2,1]]
                ÈíaY})              :  Apply each move to each position
       p                            :  Store the new positions
                      Ìde[TT]       :  True if any are at the destination

_è}         :Rook function
 è          : Count non-zero elements

_ra v *Zâ l}    :Bishop function
 ra             : Absolute difference between X and Y
    v           : Is divisible by 2? (returns 1 or 0)
      *         : Times:
       Zâ       :  Get the unique elements
          l     :  Count them
  • @ETHproductions Good suggestions. While I was putting them in I found out that á worked to shorten [[1,2][2,1]] considerably. – Kamil Drakari Nov 28 at 23:56
  • Wow, never would have thought to use á, nice one! – ETHproductions Nov 29 at 1:52
  • A couple more suggestions: U is implicit after @, so you can save two bytes in the knight function. You can also start it out with @=ã ü; to save another. (The ã trick is clever too :-) ) – ETHproductions Nov 29 at 2:09
  • @ETHproductions Good find, the times when U is implied are one of the things I haven't fully grasped yet. – Kamil Drakari Nov 29 at 3:11

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.