A272445 Numbers of paths for moving a king from a corner to the opposite one in an n X n chessboard, provided that each cell must be reached exactly once.

1, 2, 30, 4942, 5853876, 58039036412, 4458135334234700, 2811002302704446996926, 14204916761279146343474398608, 580077332863329104087361516015280826, 190934226579364879405564404836420471442186330, 507088717315287736410992294230305692212344811974323748

Offset: 1

Author

César Eliud Lozada, Apr 29 2016

Keywords

• nonn
• walk

Examples

			On a 2 X 2 chessboard, the king has 2 paths to go from a corner to the opposite one, standing exactly one time on each cell, so a(2)=2.
On a 3 X 3 chessboard, the king has 30 paths to go from a corner to the opposite one, standing exactly one time on each cell, so a(3)=30.
		

Links

• César Eliud Lozada, Chess king paths
• Eric Weisstein's World of Mathematics, King Graph

Crossrefs

Cf. A001184, A158651, A140518, A288033.

Programs

Maple

ChessKingPaths := proc(N, aUsed:=[1])
  local nLast, nPrev,  nNext,  i, j, i1, j1, i2, j2:
  global aPath, nPaths;
if N=1 then
  aPath:=[[1]]; nPaths:=1; return nPaths;
end if:
  if aUsed=[1] then
    aPath:=[]; nPaths:=0;
  end if;
  nLast:=N^(2);   #`opposite corner`
  nPrev := aUsed[-1] ; #actual position
  #Check all possible next cells
  i1:=`if`(floor((nPrev-1)/N)=0,0,-N); i2:=`if`(floor((nPrev-1)/N)=N-1,0,N);
  j1:=`if`((nPrev-1)mod N=0,0,-1); j2:=`if`((nPrev-1) mod N=N-1,0,1);
  for i from i1 to i2 by N do
    for j from j1 to j2 by 1 do
      if i=0 and j=0 then next fi; #`no move`
      nNext:=nPrev+i+j;
      #`out of bounds or already visited`
      if nNext<1 or nNext>nLast or (nNext in aUsed) then next: fi;
      #`nLast must be the last one`
      if (nNext=nLast and nops(aUsed)<>nLast-1) then next fi:
      if nNext=nLast  and nops(aUsed)=nLast-1 then  #`path completed`
        #comment if list is not required. It will consume all memory for N>=5
        aPath:=[op(aPath), [op(aUsed),nNext]];
        nPaths:=nPaths+1;
        break:
      else
        ChessKingPaths(N,[op(aUsed),nNext]) #move and continue
      end if;
    end do:
  end do:
  return nPaths;
end proc:
#For a(n) call this function with parameter n.
#Examples: ChessKingPaths(2), ChessKingPaths(3),...
#The list of paths is stored in variable aPath.

Extensions

a(5)-a(11) from Andrew Howroyd, Jun 19 2017

a(12) from Ed Wynn, Jul 08 2023