A272469 Numbers of n-step paths of a king moving on an n X n chessboard, starting at a corner and not visiting any cell twice.

0, 6, 50, 322, 1874, 10558, 58716, 325758, 1808778, 10068548, 56213606, 314785072, 1767660604, 9951449844, 56151698716, 317484868212, 1798343124800, 10203031413894

Offset

1,2

Links

Table of n, a(n) for n=1..18.

Example

On an n X n chessboard, a king in a corner is allowed to have n moves. For n=2, let's name the cells A1,A2,B1,B2 with the king at A1. Two moves, without repeating cells, can be done in the following 6 different ways: {A1-A2-B1, A1-A2-B2, A1-B1-A2, A1-B1-B2, A1-B2-A2, A1-B2-B1}. So a(2)=6.

Maple

pathCount := proc (N)
local g1, g2, nStep, gg, nCells, nPrev, i1, i2, j1, j2, i, j, nNext;
    nCells := N^2; g1 := [[1]];
    if N = 1 then return nops(g1) fi; #forced value for N=0
    for nStep to N do
        g2 := [];
        for gg in g1 do
            nPrev := gg[-1];
            i1 := `if`(floor((nPrev-1)/N) = 0, 0, -N);
            i2 := `if`(floor((nPrev-1)/N) = N-1, 0, N);
            j1 := `if`(`mod`(nPrev-1, N) = 0, 0, -1);
            j2 := `if`(`mod`(nPrev-1, N) = N-1, 0, 1);
            for i from i1 by N to i2 do
                for j from j1 to j2 do
                    if i = 0 and j = 0 then next fi;
                    nNext := nPrev+i+j;
                    if nNext < 0 or nCells < nNext or (nNext in gg) then next fi;
                    g2 := [op(g2), [op(gg), nNext]]
                end do
            end do
        end do;
        g1 := g2
    end do;
    return nops(g1);
end proc:
[seq(pathCount(n), n = 1 .. 6)];

Crossrefs

Cf. A272445.

Sequence in context: A220887 A213807 A241781 * A223816 A180880 A308860

Adjacent sequences: A272466 A272467 A272468 * A272470 A272471 A272472

Keyword

nonn,walk,more

Author

César Eliud Lozada, Apr 30 2016

Extensions

a(9)-a(16) from Alois P. Heinz, May 01 2016

a(17)-a(18) from Bert Dobbelaere, Jan 08 2019

Status

approved