What is the Probability that a Knight Stays on Chessboard?

Given the size of the chess board and initial position of the knight, calculate the probability that after k moves the knight will be inside the chess board.

Note:

• The knight makes its all 8 possible moves with equal probability.

• Once the knight is outside the chess board it cannot come back inside.

Input

Inputs are comma separated in the form:

l,k,x,y


where l is the length and width of the chess board, k is the number of moves the knight will make, x is the x-position of the initial position of the knight, and y is the y-position of the initial position of the knight. Note that 0,0 is the bottom-left corner of the board and l-1,l-1 is the top-right corner of the board.

Algorithm:

Start with the initial coordinates of the knight. Make all possible moves for this position and multiply these moves with their probability, for each move recursively call the function continue this process till the terminating condition is met. Terminating condition is if the knight is outside the chess board, in this case return 0, or the desired number of moves is exhausted, in this case return 1.

As we can see that the current state of the recursion is dependent only on the current coordinates and number of steps done so far. Therefore we can memorize this information in a tabular form.

Credit

This challenge is originally from a blog post of crazyforcode.com published under the CC BY-NC-ND 2.5 IN licence. It was slightly modified to make it a bit more challenging.

• Why do you prescribe an exact algorithm? I'm not sure if there actually is a more elegant alternative, but requiring a specific algorithm could potentially prevent other clever approaches. Also, I don't think you need to specify the coordinate system in so much detail - it doesn't affect the probability at all. – Martin Ender May 25 '15 at 11:00
• "Inputs are comma separated in the form: l,k,x,y" - so the input is a string that we have to parse? Is it not acceptable to write a function that takes 4 parameters? – Cristian Lupascu May 25 '15 at 12:58
• @Edi Don't mark an answer as 'accepted' if there has been no time for other people to give it a try - marking something as accepted so is basically saying 'The challenge is over' - while most of the world has probably not even had time to look at it! – Sanchises May 25 '15 at 14:42
• @Edi Please stop posting random challenges you find on the web. Plagiarism is frowned on by our community. Challenges from ongoing programming competitions have no business here at all, since they may help someone winning this competition. And are challenges, which are discussed in a blog post, like this chess challenge (original source), will not be well-received here. One reason is, that the original source may have some sort of copyright. – Jakube May 26 '15 at 8:22
• @Edi For instance the source of this challenge allows copying and redistributing, but only if you give appropriate credit. – Jakube May 26 '15 at 8:23

Pyth, 38 bytes

M?smcgtGd8fq5sm^-Fk2C,TH^UhQ2G1g@Q1>Q2


Try it online: Demonstration

Explanation:

                                        implicit: Q = evaluated input
M                                       define a function g(G,H): //G=depth, H=current cell
UhQ              the list [0,1,...,Q[0]-1]
^   2             Cartesian product, gives all cells
f                               filter for numbers numbers T, which satisfy:
C,TH                    zip(T,H)
m                             map the two pairs k to:
-Fk                           their difference
^   2                          squared
s                              sum (distance squared)
q5                               == 5
m                                      map each valid cell d to:
gtHd                                   g(G-1,d)
c    8                                  divided by 8
s                                       return sum
?                           G          if G > 0 else
1           return 1

g@Q1>Q2  call g(Q[1],Q[2:]) and print

• Seems to me that if we're going to create super-concise languages for the sole purpose of golfing, we might as well implement the required algorithm as a primitive. – mc0e May 26 '15 at 6:50
• @mc0e No, that would be a standard forbidden loophole. See here. – Jakube May 26 '15 at 6:56
• can we get the non-golfed code pls ? – YaSh Chaudhary Nov 9 '17 at 6:38
• @YaShChaudhary Do you mean the version with 39 bytes, or the version with 40 bytes. :-P I'm afraid there never existed a truly non-golfed version. I wrote this code directly in Pyth, and Pyth programs are always short. – Jakube Nov 9 '17 at 11:30
• @Jakube ohk np :) – YaSh Chaudhary Nov 9 '17 at 13:04

Ruby 134

->l,m,x,y{!((r=0...l)===x&&r===y)?0:m<1?1:(0..7).map{|i|a,b=[1,2].rotate i[2]
P[l,m-1,x+a*(i[0]*2-1),y+b*(i[1]*2-1)]/8.0}.inject(:+)}


Try it online: http://ideone.com/ZIjOmP

The equivalent non-golfed code:

def probability_to_stay_on_board(board_size, move_count, x, y)
range = 0...board_size
return 0 unless range===x && range===y
return 1 if move_count < 1

possible_new_locations = (0..7).map do |i|
dx, dy = [1,2].rotate i[2]
dx *= i[0]*2-1
dy *= i[1]*2-1

[x+dx, y+dy]
end

possible_new_locations.map do |new_x, new_y|
probability_to_stay_on_board(board_size, move_count-1, new_x, new_y) / 8.0
end.inject :+
end


Implements a function f with parameters l k x y

import Data.List
g[]=[]
g((a,b):r)=[(a+c,b+d)|(c,d)<-zip[-2,-1,1,2,-2,-1,1,2][1,2,-2,-1,-1,-2,2,1]]++g r
h _ 0 a=a
h l a b=h l(a-1)$filter(\(a,b)->(elem a[0..l])&&(elem b[0..l]))$g b
f l k x y=(sum$map(\x->1.0) (h l k [(x,y)]))/(8**k)  Matlab, 124 119 Exactly implements the described algorithm. I was able to shorten it by 5 bytes with some help of @sanchises, thanks! function s=c(l,k,x,y);m=zeros(5);m([2,4,10,20])=1/8;s(l,l)=0;s(l-y,x+1)=1;for i=1:k;s=conv2(s,m+m','s');end;s=sum(s(:))  Expanded: function s=c(l,k,x,y); m=zeros(5); m([2,4,10,20])=1/8; s(l,l)=0;s(l-y,x+1)=1; for i=1:k; s=conv2(s,m+m','s'); end; s=sum(s(:))  Old version function s=c(l,k,x,y); m =zeros(5);m([1:3,5,8,10:12]*2)=1/8; s=zeros(l); s(l-y,x+1)=1; for i=1:k s=conv2(s,m,'s'); end s=sum(s(:));  • One hint: s is initialized by MATLAB, so you can just do s(l,l)=0; Too bad MATLAB does not have fibonnaci as a built-in function, that would be a great optimization for m. – Sanchises May 25 '15 at 15:33 • That is a super awesome trick, thanks! I am still tryting to find a shorter way of creating m by a matrix decomposition... – flawr May 25 '15 at 15:44 • Yeah, I was looking at it for a while too. Perhaps some smart logical indexing, but I can't think of anything. m+m'+fliplr(m+m') seems to be an increase in bytecount, and so are all my other options. – Sanchises May 25 '15 at 20:29 Mathematica - 137 q = # {1, 2} & /@ Tuples[{-1, 1}, 2] q = Reverse /@ q~Union~q g[l_, k_, x_, y_] := Which[ k < 1, 1, !0 <= x < l || ! 0 <= y < l, 0, 0<1, Mean[g[l, k - 1, x + #[[1]], y + #[[2]]] & /@ q] ]  Usage: g[5,5,1,2]  Output: 9/64  MATLAB - 106 function s=c(l,k,x,y);m(5,5)=0;m([2,4,10,20])=1/8;s=ones(l);for i=1:k;s=conv2(s,m+m','s');end;s=s(l-y,x+1)  Improves on @flawr's solution by being more MATLAB-y. Expanded: function s=c(l,k,x,y) m(5,5)=0; m([2,4,10,20])=1/8; s=ones(l); for i=1:k s=conv2(s,m+m','s'); end s=s(l-y,x+1)  ><> - 620 (not counting whitespace) Initial stack should be l,k,x,y {:a2*0p v vp0*3a*}:{< >{1+&a3*0g}v > > > >~~01-01-v > > > >~~01-01-v > > > >~~01-01-v > > > >~~01-01-v >&1-:&?!v>:@@:@@:0(?^:a2*0g1-)?^2-$:0(?^:a2*0g1-)?^1-      >}}$:@@:@@:0(?^:a2*0g1-)?^2-$:0(?^:a2*0g1-)?^1+      >}}$:@@:@@:0(?^:a2*0g1-)?^2+$:0(?^:a2*0g1-)?^1-      >}}$:@@:@@:0(?^:a2*0g1-)?^2+$:0(?^:a2*0g1-)?^1+      >}}$:@@:@v v1 ^} ^!?=g0*3a:~~}}< +2v?)-1g0*2a:v?(0:$+1v?)-1g0*2a:v?(0:@@:@@:$}}< -2v?)-1g0*2a:v?(0:$+1v?)-1g0*2a:v?(0:@@:@@:$}}< +2v?)-1g0*2a:v?(0:$-1v?)-1g0*2a:v?(0:@@:@@:$}}<-2 v?)-1g0*2a:v?(0:$-1v?)-1g0*2a:v?(0:@<
>a3*0g=   ?^\      &              ^-10-10~~<          <       <          <             ^-10-10~~<          <       <          <             ^-10-10~~<          <       <          <             ^-10-10~~<          <       <          <
\         :{/
v                  >~{~l2,&0
>@:0(?v:a2*0g1-)?v\$:0(?v:a2*0g1-)?v1>@~~+l1=?v
>          >     >          >0^        >&,n;


Test it out