cp's OEIS Frontend

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.

%I A272445 #31 Feb 16 2025 08:33:34
%S A272445 1,2,30,4942,5853876,58039036412,4458135334234700,
%T A272445 2811002302704446996926,14204916761279146343474398608,
%U A272445 580077332863329104087361516015280826,190934226579364879405564404836420471442186330,507088717315287736410992294230305692212344811974323748
%N 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.
%H A272445 César Eliud Lozada, <a href="/A272445/a272445.pdf">Chess king paths</a>
%H A272445 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/KingGraph.html">King Graph</a>
%e A272445 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.
%e A272445 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.
%p A272445 ChessKingPaths := proc(N, aUsed:=[1])
%p A272445   local nLast, nPrev,  nNext,  i, j, i1, j1, i2, j2:
%p A272445   global aPath, nPaths;
%p A272445 if N=1 then
%p A272445   aPath:=[[1]]; nPaths:=1; return nPaths;
%p A272445 end if:
%p A272445   if aUsed=[1] then
%p A272445     aPath:=[]; nPaths:=0;
%p A272445   end if;
%p A272445   nLast:=N^(2);   #`opposite corner`
%p A272445   nPrev := aUsed[-1] ; #actual position
%p A272445   #Check all possible next cells
%p A272445   i1:=`if`(floor((nPrev-1)/N)=0,0,-N); i2:=`if`(floor((nPrev-1)/N)=N-1,0,N);
%p A272445   j1:=`if`((nPrev-1)mod N=0,0,-1); j2:=`if`((nPrev-1) mod N=N-1,0,1);
%p A272445   for i from i1 to i2 by N do
%p A272445     for j from j1 to j2 by 1 do
%p A272445       if i=0 and j=0 then next fi; #`no move`
%p A272445       nNext:=nPrev+i+j;
%p A272445       #`out of bounds or already visited`
%p A272445       if nNext<1 or nNext>nLast or (nNext in aUsed) then next: fi;
%p A272445       #`nLast must be the last one`
%p A272445       if (nNext=nLast and nops(aUsed)<>nLast-1) then next fi:
%p A272445       if nNext=nLast  and nops(aUsed)=nLast-1 then  #`path completed`
%p A272445         #comment if list is not required. It will consume all memory for N>=5
%p A272445         aPath:=[op(aPath), [op(aUsed),nNext]];
%p A272445         nPaths:=nPaths+1;
%p A272445         break:
%p A272445       else
%p A272445         ChessKingPaths(N,[op(aUsed),nNext]) #move and continue
%p A272445       end if;
%p A272445     end do:
%p A272445   end do:
%p A272445   return nPaths;
%p A272445 end proc:
%p A272445 #For a(n) call this function with parameter n.
%p A272445 #Examples: ChessKingPaths(2), ChessKingPaths(3),...
%p A272445 #The list of paths is stored in variable aPath.
%Y A272445 Cf. A001184, A158651, A140518, A288033.
%K A272445 nonn,walk
%O A272445 1,2
%A A272445 _César Eliud Lozada_, Apr 29 2016
%E A272445 a(5)-a(11) from _Andrew Howroyd_, Jun 19 2017
%E A272445 a(12) from _Ed Wynn_, Jul 08 2023