A141243 Number of ways to place non-attacking knights on the n X n board.

1, 2, 16, 94, 1365, 55213, 3368146, 394631712, 101693175442, 50929053498909, 48988729226134301, 96325314726538906164, 375615195988659173454092, 2933480442104347575000834468, 45480806737377995771543610802659, 1422902021111889804120495149240353936

Offset: 0

Author

Max Alekseyev, Jun 17 2008

Keywords

• hard
• nonn
• nice

Comments

The maximum number of non-attacking knights is given by A030978.

Also the number of vertex covers and independent vertex sets in the n X n knight graph.

Links

• Vaclav Kotesovec, Non-attacking chess pieces, 6ed, 2013, p. 69-72, 283-285.
• Eric Weisstein's World of Mathematics, Independent Vertex Set
• Eric Weisstein's World of Mathematics, Knight Graph
• Eric Weisstein's World of Mathematics, Vertex Cover

Crossrefs

Cf. A182407, A182408, A201540.

Row sums of A244081.

Programs

Mathematica

b[n_, l_] := b[n, l] = Module[{d, f, g, k}, d = Length[l]/3; f = False; Which[n == 0, 1, l[[1 ;; d]] == Array[f &, d], b[n - 1, Join[l[[d + 1 ;; 3*d]], Array[True &, d]]], True, For[k = 1, ! l[[k]], k++]; g = ReplacePart[l, k -> f];
     If[k > 1, g = ReplacePart[g, 2*d - 1 + k -> f]];
     If[k < d, g = ReplacePart[g, 2*d + 1 + k -> f]];
     If[k > 2, g = ReplacePart[g, d - 2 + k -> f]];
     If[k < d - 1, g = ReplacePart[g, d + 2 + k -> f]];
     Expand[b[n, ReplacePart[l, k -> f]] + b[n, g]*x]]];
a[n_] := Function[p, Sum[Coefficient[p, x, i], {i, 0, Exponent[p, x]}]][ b[n, Array[True &, n*3]]];
Table[an = a[n]; Print["a(", n, ") = ", an]; an, {n, 0, 10}] (* Jean-François Alcover, Mar 29 2016, after Alois P. Heinz's code for A244081 *)

PARI

A141243(n=4, s=n^2-1, bad=0)={ while(s && bittest(bad, s), s--);
   if(s < n, 2^(s+1-hammingweight(bad % (2<A141243(n, s-1, bad), x = s%n);
      x > 1 && bad = bitor(bad, 2^(s-n-2)); x < n-2 && bad = bitor(bad, 2^(s-n+2));
      if( s >= 2*n, x && bad = bitor(bad, 2^(s-2*n-1));
              x < n-1 && bad = bitor(bad, 2^(s-2*n+1))
   ); cnt + A141243(n, s-1, bad))} \\ M. F. Hasler, Mar 18 2025

Python

def A141243(n=4, start=(1,1), forbidden=()):
    if start[0] >= n: return 2**sum((n,y+1) not in forbidden for y in range(n))
    nxt = (start[0],start[1]+1) if start[1]A141243(n, nxt, forbidden)
    if start in forbidden: return cnt
    forbidden = {s for s in forbidden if s >= nxt}
    if start[1]2: forbidden |= {(start[0]+1,start[1]-2)}
    if start[0]1: forbidden |= {(start[0]+2,start[1]-1)}
    return cnt+A141243(n, nxt, forbidden) # M. F. Hasler, Mar 17 2025

Extensions

a(8)-a(13) from R. H. Hardin, Aug 25 2008

a(0) from Alois P. Heinz, Jun 19 2014

a(14) from Hiroaki Yamanouchi, Aug 28 2014

a(15) from Hiroaki Yamanouchi, Aug 29 2014