Help:=proc()
print(`functions are DumbCount,DumbCountCanStay, Count, BetterCount, BetterCountCanStay`):
print(`if a function has \`CanStay\` in the name, it allows the king to stay in its current position`):
print(`if the function starts with \`Dumb\` the first argument [0$dimension], otherwise it is just the number of dimensions`):
print(`the second argument is the number of steps you are allowed`):
end:

DumbCount:=proc(offset,steps) local step: option remember:
if(steps=0) then 
if(abs(min(offset))+abs(max(offset))=0) then
return 1:
else
return 0:
fi:
fi:
add(DumbCount(offset+step,steps-1),step in 
(cartProd([({-1,0,1})$nops(offset)]) minus {[0$nops(offset)]})):
end:

DumbCountCanStay:=proc(offset,steps) local step: option remember:
if(steps=0) then 
if(abs(min(offset))+abs(max(offset))=0) then
return 1:
else
return 0:
fi:
fi:
add(DumbCountCanStay(offset+step,steps-1),step in 
(cartProd([({-1,0,1})$nops(offset)]) minus {})):
end:

cartProd:=proc(ListOfSets) local T,t,S,s:
option remember:
if nops(ListOfSets)=1 then
  RETURN({seq(seq([s],s in t),t in ListOfSets)}):
fi:
T:={}:
for t in ListOfSets[1] do
  S:=cartProd(ListOfSets[2..nops(ListOfSets)]):
  T:= T union {seq([t,op(s)],s in S)}:
od:
T:
end:

Count:=proc(dim,steps) local x,j:
x:=`x`:
constTerm((mul((x[j]+1+x[j]^(-1)),j=1..dim)-1)^steps,x,dim):
end:

constTerm:=proc(expr,x,dim)
if(dim=0) then
expr:
else:
constTerm(coeff(expr,x[dim],0),x,dim-1):
fi:
end:

BetterCountCanStay:=proc(dim,steps) local x:
x:=`x`:
#generating function for the central trinomial coefficient
coeff(taylor(1/sqrt(1-2*x-3*x^2),x,steps+1),x,steps)^dim:
end:

#uses the identity that countCanStay= 1 + add(binomial*count)
#and fact that dumbcountcanstay is easy to compute to compute it all
BetterCount:=proc(dim,steps) local i: option remember:
if(steps=1) then 
0:
else
BetterCountCanStay(dim,steps)-1-add(binomial(steps,i)*BetterCount(dim,i),i=1..steps-1):
fi:
end: