48
\$\begingroup\$

Introduction

Aron Nimzowitsch was a leading chess master and a influential chess writer.

In his book 'My System', the first chapter deals about the importance of the center and why you should dominate it. The simple reason is that your pieces have more possible direct next moves when being in the center which again gives the player more power.

This gets very clear when looking at different positions of a knight and its potential next moves (shown in pink) on an empty board:

enter image description here

Objective

Evaluate the number of potential direct next moves of a knight on an empty board based on its position.

Input Specs

The position of the knight.

First the x (column) and then the y (row). 0 0 is the left bottom corner.

For simplicity, I changed the labels of a chess board to numbers only. For our examples and test cases we use a 0-based index, you are free to use a 1-based index though.

You can use any type of possible input formats, an array, function arguments, etc.

Output Specs

The number of potential direct next moves for a knight on an empty board.

Test Cases

3 4 => 8
4 6 => 6
7 7 => 2
1 0 => 3

Test cases are employing a 0-based index. The full grid of values is:

2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2
\$\endgroup\$
  • 9
    \$\begingroup\$ Nice first challenge! :-) \$\endgroup\$ – Luis Mendo Jun 28 '16 at 7:58
  • 14
    \$\begingroup\$ "Knight on the rim is grim" \$\endgroup\$ – user4768 Jun 28 '16 at 8:16
  • 2
    \$\begingroup\$ @stacey Your comment would have been a great title for this puzzle :) \$\endgroup\$ – starcorder Jun 28 '16 at 8:24
  • 6
    \$\begingroup\$ Now for the really hard question: Are the red knights in the above images all the same color? \$\endgroup\$ – mbomb007 Jun 29 '16 at 21:53

17 Answers 17

25
\$\begingroup\$

Python 2, 35 bytes

lambda x,y:50/(8+x*x/7-x+y*y/7-y)-4

Try it online!


Python 2, 39 bytes

lambda x,y:50/(8-x*(7-x)/5-y*(7-y)/5)-4

Try it online!

Takes inputs 0-indexed.

The expression x*(7-x)/5 takes the coordinate values 0..7 to

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

(min(x,7-x,2) does the same, but is longer.) Summing this for x and y gives the right pattern but with the wrong numbers

0 1 2 2 2 2 1 0
1 2 3 3 3 3 2 1
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
1 2 3 3 3 3 2 1
0 1 2 2 2 2 1 0

(See Neil's solution for better reasoning as to why this gives about the right pattern.)

Finally, the mapping a -> 50/(8-a)-4 with floor-division gives the right values

2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

An alternative equally-long solution with 1-indexed inputs:

lambda x,y:(x*(9-x)/6+y*(9-y)/6)**2/6+2
\$\endgroup\$
  • \$\begingroup\$ (7-a)*a/5 is 3 bytes shorter than min(a,7-a,2). \$\endgroup\$ – Neil Jun 28 '16 at 9:37
  • 1
    \$\begingroup\$ *l actually costs you a byte overall, lambda a,b:"23468"[(7-a)*a/5+(7-b)*b/5] is only 41 bytes. \$\endgroup\$ – Neil Jun 28 '16 at 9:39
  • \$\begingroup\$ @Neil I had just found the same thing with x*(9-x)/6, one-indexed. \$\endgroup\$ – xnor Jun 28 '16 at 9:41
  • 1
    \$\begingroup\$ Why don't you use <strike> like everyone else to show golfing progress? \$\endgroup\$ – Insane Jun 28 '16 at 17:11
  • 4
    \$\begingroup\$ @Insane I think it looks ugly and doesn't actually help. The code is the important thing, and anyone who wants to see its evolution still need to look in the edit history. When my old code is different enough to be worth showing, I show the versions like here. But on this question, it's all minor improvements to the same strategy, so I found it cleaner just to mention the different possibilities. \$\endgroup\$ – xnor Jun 28 '16 at 21:45
17
\$\begingroup\$

MATL, 17 14 13 12 bytes

Thanks to @Neil for 1 byte off!

8:HZ^ZP5X^=s

Input is 1-based.

Try it online!

Explanation

This computes the Euclidean distance from the input to each of the 64 positions in the chessboard, and finds how many of those values equal the square root of 5.

Since the coordinates are integer values, we can be sure that the two floating-point values representing the square root of 5 (that computed from the coordinates and that computed directly) are indeed the same.

8:      % Push array [1 2 ... 8]
H       % Push 2
Z^      % Cartesian power. Gives 2D array [1 1; 1 2; ... 1 8; 2 1; ... 8 8]     
ZP      % Implicit input. Compute Euclidean distances, considering each row as a point
5X^     % Square root of 5
=s      % Compute how many squared distances equal sqrt(5). Implicit display
\$\endgroup\$
  • 1
    \$\begingroup\$ Impressive and thanks for the explanation \$\endgroup\$ – starcorder Jun 28 '16 at 7:54
  • 1
    \$\begingroup\$ If comparing the square of the square root of 5 to 5 fails due to rounding errors, can you not at least compare the square root of 5 to the square root of 5? \$\endgroup\$ – Neil Jun 28 '16 at 10:56
  • \$\begingroup\$ @Neil Thanks for the idea! Yes, since computations are with integers, I can be sure that the two "roots of 5" are the same double number. Ant it saves a byte \$\endgroup\$ – Luis Mendo Jun 28 '16 at 11:08
15
\$\begingroup\$

Mathematica 63 43 bytes

With 20 bytes saved thanks to suggestions by Martin Ender!

EdgeCount[8~KnightTourGraph~8,#+1+8#2/<->_]&

The above finds the number of squares that are 1 hop away from the given cell on the complete knights tour graph.


g=KnightTourGraph[8,8,VertexLabels->"Name",Axes->True]

displays the complete knight's tour graph, with vertex names and coordinates. Note that Mathematica defaults to one-based indexing for the coordinates.

graph


#+1+8#2&[r,f] converts returns the vertex corresponding to square at rank (row), r, and file (column), f, using zero-based values as input.

For example #+1+8#2&[2,1] returns 11.


EdgeCount gives the number of edges in the neighborhood graph.


The edges for rank 2, file 1 (square 11):

IncidenceList[8~KnightTourGraph~8, 8 #2 + # + 1] &[2, 1]

(*{1 <-> 11, 5 <-> 11, 11 <-> 17, 11 <-> 21, 11 <-> 26, 11 <-> 28}*)

The highlighted edges:

HighlightGraph[g, {1, 5, 11, 17, 21, 26, 28, Style[1 <-> 11, Thick, Blue], Style[5 <-> 11, Thick, Blue], Style[11 <-> 17, Thick, Blue], Style[11 <-> 21, Thick, Blue], Style[11 <-> 26, Thick, Blue], Style[11 <-> 28, Thick, Blue]},GraphHighlightStyle -> "DehighlightFade", PlotRangePadding -> .5]

highlight


Method 2: Euclidean distance

70 bytes

This method is longer, but possibly of some interest. The approach is to check the Euclidean distance between the center of the chessboard and the cell of interest.

Which[(x=Sqrt@Tr[({3.5, 3.5}-#)^2])<2.2,8,x<3,6,x<4,4,x<4.6,3,x>4.6,2]&

Exemplifying

Which[(x=Sqrt@Tr[({3.5, 3.5}-#)^2])<2.2,8,x<3,6,x<4,4,x<4.6,3,x>4.6,2]&@{0, 0}
Which[(x=Sqrt@Tr[({3.5, 3.5}-#)^2])<2.2,8,x<3,6,x<4,4,x<4.6,3,x>4.6,2]&@{3, 3}

2

8


To help visualize how the distance from the center of the chessboard is sufficient for assigning a value.

values={{2,3,4,4,4,4,3,2},{3,4,6,6,6,6,4,3},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{4,6,8,8,8,8,6,4},{3,4,6,6,6,6,4,3},{2,3,4,4,4,4,3,2}};
f[x_]:=Text[x,#]&/@Position[values,x]r_~w~p_:=RegionMember[{3.5`,3.5`}~Disk~r,p]
h@y_:=Which[2.2~w~y,8,3~w~y,6,4~w~y,4,4.6~w~y,3,2<3,2]

Graphics[{Circle[{4.5, 4.5}, 2.3], Circle[{4.5, 4.5}, 3], 

Circle[{4.5, 4.5}, 4],

Circle[{4.5, 4.5}, 4.6], Flatten[f /@ {2, 3, 4, 6, 8}, 1]}, Axes -> True, AxesOrigin -> {-1, -1}]


The numbers 2.2, 3, 4, and 4.6 are the radii of the circles.

image

\$\endgroup\$
  • 1
    \$\begingroup\$ Great tour graph \$\endgroup\$ – starcorder Jun 28 '16 at 13:49
  • 20
    \$\begingroup\$ KnightTourGraph Mathematica and its builtins... :-) \$\endgroup\$ – Luis Mendo Jun 28 '16 at 13:56
  • \$\begingroup\$ I think there's a stray # at the end of your source code (just before the ]). You should be able to use IncidenceList instead of EdgeList@NeighborhoodGraph though. (Alternatively, there's also EdgeCount, but I think that ends up being longer.) \$\endgroup\$ – Martin Ender Jun 28 '16 at 14:08
  • 1
    \$\begingroup\$ Oh wait, it's actually shorter: EdgeCount[8~KnightTourGraph~8,#+1+8#2<->_]& \$\endgroup\$ – Martin Ender Jun 28 '16 at 14:10
  • \$\begingroup\$ EdgeCount is very cool! \$\endgroup\$ – DavidC Jun 28 '16 at 14:32
12
\$\begingroup\$

JavaScript (ES6), 38 bytes

(x,y)=>+"23468"[((7-x)*x+(7-y)*y)/5|0]

Takes 0-indexed inputs. Explanation: Look at the squares of the distances to the centre:

24.5 18.5 14.5 12.5 12.5 14.5 18.5 24.5
18.5 12.5  8.5  6.5  6.5  8.5 12.5 18.5
14.5  8.5  4.5  2.5  2.5  4.5  8.5 14.5
12.5  6.5  2.5  0.5  0.5  2.5  6.5 12.5
12.5  6.5  2.5  0.5  0.5  2.5  6.5 12.5
14.5  8.5  4.5  2.5  2.5  4.5  8.5 14.5
18.5 12.5  8.5  6.5  6.5  8.5 12.5 18.5
24.5 18.5 14.5 12.5 12.5 14.5 18.5 24.5

The number of reachable squares falls into five bands:

8    0-5
6    5-10
4   10-15
3   15-20
2   20-25

I actually calculate 24.5 - (3.5 - x) ** 2 - (3.5 - y) ** 2 = (7 - x) * x + (7 - y) * y as it's a shorter calculation, but all it does is reverse the order of the bands.

\$\endgroup\$
  • \$\begingroup\$ Super concise and very nice approach, so I don't have to start my own JS solution anymore :) \$\endgroup\$ – starcorder Jun 28 '16 at 10:00
  • \$\begingroup\$ Good point about the formula being equivalent about radius squared. I had thought of x*(7-x) as just an operation that looks like a downward arc on 0..7 and happens to curve fit, but this explains why it produces such a nice pattern when summed for x and y. \$\endgroup\$ – xnor Jun 28 '16 at 10:04
11
\$\begingroup\$

Jelly, 10 bytes

8ṗ2_³²S€ċ5

1-indexed. Takes a single argument of the form [x,y]. Try it here.

8ṗ2          Cartesian square [[1,1],[1,2]…[8,8]]
   _³        Subtract the input
     ²S€     Compute the norm of each vector
        ċ5   Count fives

Dennis saved a byte!

\$\endgroup\$
  • \$\begingroup\$ Just eleven bytes, wow! \$\endgroup\$ – starcorder Jun 28 '16 at 12:00
  • \$\begingroup\$ I saw this question in the morning and this is the exact algorithm I thought I'd implement in Jelly when I had time. :P \$\endgroup\$ – PurkkaKoodari Jun 28 '16 at 12:09
8
\$\begingroup\$

Mathematica, 44 40 bytes

I've currently got three solutions at the same byte count:

2[3,4,6,8][[Tr@⌊3.2-.8Abs[#-4.5]⌋]]&
Tr@⌈.85(4-Abs[#-4.5])⌉/.{5->6,6->8}&
⌊Tr@⌈.85(4-Abs[#-4.5])⌉^1.1608⌋&

All of those are unnamed functions that take pair of coordinates like {3, 4}, which are 1-based.

I tried coming up with a somewhat explicit formula. The general pattern on the entire board looks like this:

enter image description here

The actual values of those colours (from lightest to darkest) are 2, 3, 4, 6, 8. That is:

2 3 4 4 4 4 3 2
3 4 6 6 6 6 4 3
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
4 6 8 8 8 8 6 4
3 4 6 6 6 6 4 3
2 3 4 4 4 4 3 2

We first exploit the symmetry by shifting the origin to the centre, taking the absolute value and subtracting the result from 4. This gives us coordinates 0.5 to 3.5 increasing from each corner. In order to make the centre coordinates the same we need to map 0.5 and 1.5 to different values and 2.5 and 3.5 to the same value. This is easily done by multiplying by 0.8 (gives{0.4, 1.2, 2., 2.8}) and flooring the result. So now we've got {0, 1, 2, 2} as distances from the centre. If we add up the coordinates in each cell, we get this table:

0 1 2 2 2 2 1 0
1 2 3 3 3 3 2 1
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
2 3 4 4 4 4 3 2
1 2 3 3 3 3 2 1
0 1 2 2 2 2 1 0

This has unique values for all the different possible results, so we simply use it as an index into 2[3,4,6,8].

In the second version we use ceiling instead floor. This way, 2, 3 and 4 are already correct, but we get 5 and 6 instead of 6 and 8, so we correct those manually with a substitution rule.

Finally, in the third version, we extend 5 and 6 upwards to 6 and 8 by means of exponentiation, followed by another floor operation.

\$\endgroup\$
  • \$\begingroup\$ I like very much the approach using the board's general pattern, great! \$\endgroup\$ – starcorder Jun 28 '16 at 7:56
6
\$\begingroup\$

APL, 21 chars

{+/,5=+/¨×⍨(⍳8 8)-⊂⍵}

In English:

  • (⍳8 8): 8x8 rank-2 array containing the coordinates of all the cells;
  • +/¨×⍨(⍳8 8)-⊂⍵: square of the euclidean distances of the given cell with respect to every cell on the board;
  • 5=: matrix of 0/1, where the 1s appear at squared distances equal 5;
  • +/,: sum the flattened matrix

Test (in origin 1):

    f←{+/,5=+/¨×⍨(⍳8 8)-⊂⍵}
    f¨1+(3 4)(4 6)(7 7)(1 0)
8 6 2 3

In this form:

f←{+/,5=+/¨×⍨(⍳⍺)-⊂⍵}

the left argument can specify the dimensions of the board. Hence 8 8 f will work for the standard square chessboard. But on a larger and rectangular board, the test cases would give different results. For instance, on a 12x10 board:

    g←(10 12)∘f
    g¨1+(3 4)(4 6)(7 7)(1 0)
8 8 8 3
\$\endgroup\$
  • \$\begingroup\$ In APL jargon, a matrix is an array of rank 2, nothing said about the content of the cells. Years of (ab)use of the terms made me insensitive to it. I'll update the description for the more traditionally inclined readers. Thank you. \$\endgroup\$ – lstefano Jun 28 '16 at 11:04
  • \$\begingroup\$ @Istefano That use of "rank" as "number of dimensions" seems to suffer from the same affliction :-P \$\endgroup\$ – Luis Mendo Jun 28 '16 at 11:16
  • \$\begingroup\$ I'll be... You are right! You can see that it's been a while since I took Linear Algebra. I give up :-) \$\endgroup\$ – lstefano Jun 28 '16 at 11:23
  • 1
    \$\begingroup\$ Full program, 27: ≢⍸5=+/¨×⍨-∘⎕¨⍳8 8 Try it online! \$\endgroup\$ – Adám May 7 at 13:13
  • \$\begingroup\$ @Adám you mean 17 \$\endgroup\$ – ngn May 8 at 17:26
6
\$\begingroup\$

Java - 160 150 bytes

int m(int r,int c){int m=0,i,j;for(i=0;i<3;i+=2)for(j=0;j<3;j+=2){m+=r+i>0&r+i<9&c+2*j>1&c+2*j<11?1:0;m+=r+2*i>1&r+2*i<11&c+j>0&c+j<9?1:0;}return m;}

Ungolfed:

public static int m(int r, int c) {
    int m=0;
    for(int i=-1;i<2;i+=2)
        for(int j=-1;j<2;j+=2){
            m += r+i>-1 && r+i<8 && c+2*j>0 && c+2*j<8 ? 1:0;
            m += r+2*i>0 && r+2*i<8 && c+j>1 && c+j<8 ? 1:0;
        }
    return m;
}

The ungolfed code is identical except for changing the bounds of the for loop to save 4 bytes. Works by iterating through each possible move and performing a bounds check (>0 and <8). Uses the fact that the offsets are (1, 2), (2, 1), (-1, 2), (-2, 1), etc. and is able to check 2 moves for each value of i and j.

Edit: 10 bytes saved thanks to suggestions by Leaky Nun and u902383.

\$\endgroup\$
  • \$\begingroup\$ This was also fast, nice! \$\endgroup\$ – starcorder Jun 28 '16 at 6:09
  • \$\begingroup\$ Had an error in there, it has been fixed. \$\endgroup\$ – ejaszewski Jun 28 '16 at 6:22
  • 1
    \$\begingroup\$ int m=0,i=-1,j; to save some bytes \$\endgroup\$ – Leaky Nun Jun 28 '16 at 7:23
  • 1
    \$\begingroup\$ change logical AND to bitwise AND and that will allow you to remove additional 6 characters \$\endgroup\$ – user902383 Jun 28 '16 at 9:43
6
\$\begingroup\$

C, 44 Bytes

f(x,y){return "23468"[((7-x)*x+(7-y)*y)/5];}

But this is better:

f(x,y){return "2344443234666643468888644688886446888864468888643466664323444432"[x*8+y];}
\$\endgroup\$
  • 1
    \$\begingroup\$ Missing ;. Won't compile. \$\endgroup\$ – ugoren Jun 28 '16 at 18:51
  • \$\begingroup\$ @GiacomoGarabello See: meta.codegolf.stackexchange.com/a/1146/55729 \$\endgroup\$ – Jacajack Jun 28 '16 at 20:23
  • 1
    \$\begingroup\$ It's not a snippet, it's a function and it's not forbidden post functions. Sorry for the missing semicolon. Fixed. \$\endgroup\$ – Giacomo Garabello Jun 28 '16 at 20:28
5
\$\begingroup\$

Haskell, 49 48 bytes

w=[0..7]
x%y=sum[1|a<-w,b<-w,(a-x)^2+(b-y)^2==5]
\$\endgroup\$
  • 1
    \$\begingroup\$ You can save [0..7] to a variable for 1 byte. \$\endgroup\$ – xnor Jun 28 '16 at 11:18
5
\$\begingroup\$

Java, 81 characters (113 bytes)

int r(int a,int b){return "⍄䐲㑦晃䚈衤䚈衤䚈衤䚈衤㑦晃⍄䐲".codePointAt(a*2+b/4)>>(3-b%4)*4&15;}

Encode the whole result table as unicode table and then get appropriate bytes doing bitwise operations.

You can see it online here: https://ideone.com/K9BojC

\$\endgroup\$
3
\$\begingroup\$

Python, 94 bytes

lambda x,y,a=[2,1,-1,-2,-2,-1,1,2]:list((9>x+a[i]>0)&(9>y+a[5-i]>0)for i in range(8)).count(1)

Uses 1 based indexing.

Demo at https://repl.it/C6gV.

\$\endgroup\$
2
\$\begingroup\$

Pyth - 33 15 bytes

Thanks to @LeakyNun for reducing my size by half.

Rearranging the maps and V's will probably lemme golf a little off.

/sM*Fm^R2-Rd8Q5

Test Suite.

\$\endgroup\$
  • 1
    \$\begingroup\$ This was fast, nice! \$\endgroup\$ – starcorder Jun 28 '16 at 5:56
  • 2
    \$\begingroup\$ 15 bytes \$\endgroup\$ – Leaky Nun Jun 28 '16 at 7:21
2
+200
\$\begingroup\$

APL (Dyalog Unicode), 15 bytesSBCS

≢⍸2=|×.-∘⎕¨⍳8 8

Try it online!

\$\endgroup\$
2
\$\begingroup\$

J, 23 bytes

1#.1#.5=[:+&*://]-/i.@8

Try it online!

Homage to Lynn's method, converted to J

\$\endgroup\$
1
\$\begingroup\$

Actually, 18 bytes

`;7-2km`MΣ8-:50\¬¬

Try it online!

This implements the same formula that many other answers have been using: 50/(8-x*(7-x)//5+y*(7-y))//5)-4. Input is taken as a list: [x,y] (or any iterable literal in Python, like (x,y) or x,y).

Explanation:

`;7-2km`MΣ8-:50\¬¬
`;7-2km`M           for each value in input:
 ;7-                  make a copy, subtract from 7
    2                 push 2
     km               minimum of the three values (x, 7-x, 2)
         Σ          sum
          8-        subtract from 8
            :50\    integer divide 50 by the value
                ¬¬  subtract 2 twice
\$\endgroup\$
0
\$\begingroup\$

Perl 6, 44 bytes

{+grep {5==[+] $_>>²},((^8 X, ^8)XZ-(@_,))}

Try it online!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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