I believe the answer is 643888. Here's how I arrived at this number:
- Let $C_k$ be the set of $4 \times 4$ $(0,1)$-matrices with $k$ 1's for which there do not exist two neighbouring 1's.
- Let $B_k$ be the set of $4 \times 4$ $(0,1)$-matrices with $k$ 1's for which there exists two neighbouring 1's, and for which deletion of some 1 implies membership in $C_{k-1}$.
- For any two (0,1)-matrices, $L$ and $M$, let $\chi(L,M)=1$ if $L$ and $M$ do not have a 1 in the same position and $0$ otherwise.
We need the sets $B_k$ and $C_k$ to avoid multiple win situations.
The number you seek is given by \[\sum_{k=0}^{n^2/2} \Big(\sum_{L \in B_k} \sum_{M \in C_{k-1}} \chi(L,M) + \sum_{L \in C_k} \sum_{M \in B_k} \chi(L,M)\Big).\] The first term counts when player 1 wins, and the second term counts when player 2 wins. I implemented this formula in GAP with the code below.
This function determines if a (0,1)-matrix has n/2 lines in a horizontal or vertical line.
user3740Win:=function(L,n)
local m,i,j;
if(n mod 2=1) then return fail; fi;
m:=n/2;
for i in [1..n] do for j in [1..m+1] do
if(ForAll([0..m-1],k->L[i][j+k]=1)) then return true; fi;
if(ForAll([0..m-1],k->L[j+k][i]=1)) then return true; fi;
od; od;
return false;
end;;
This function determines if a (0,1)-matrix has n/2 lines in a horizontal or vertical line, and that deletion of one of the 1's results in falsifying user3740Win(L,n).
user3740StrongWin:=function(L,n)
local M,i,j;
if not(user3740Win(L,n)) then return false; fi;
M:=List([1..n],i->List([1..n],j->L[i][j]));
for i in [1..n] do for j in [1..n] do
M[i][j]:=0;
if(user3740Win(M,n)=false) then return true; fi;
M[i][j]:=L[i][j];
od; od;
return false;
end;;
This function generates the (0,1)-matrices with at most n^2/2 1's.
user3740MatricesStep1:=function(n)
local A,B,L,M,i,j;
A:=Filtered(Tuples([0,1],n^2),i->Sum(i)<=n^2/2);
B:=[];
for L in A do
M:=List([1..n],i->List([1..n],j->0));
for i in [1..n] do for j in [1..n] do
M[i][j]:=L[n*(i-1)+j];
od; od;
Append(B,[M]);
od;
return B;
end;;
Starting from A (the set of (0,1)-matrices with at most n^2/2 1's), I run through k=0..n^2/2. B is $B_k$ above. C1 is $C_{k-1}$ above. C2 is $C_k$ above.
user3740Count:=function(n)
local A,B,C1,C2,S,i,j,k,L,M;
A:=user3740MatricesStep1(n);
S:=[];
for k in [0..n^2/2] do
B:=Filtered(A,L->user3740StrongWin(L,n) and Sum(Sum(L))=k);
C1:=Filtered(A,L->(not user3740Win(L,n)) and Sum(Sum(L))=k-1);
C2:=Filtered(A,L->(not user3740Win(L,n)) and Sum(Sum(L))=k);
Print("k=",k," ",Size(B)," ",Size(C1)," ",Size(C2),"\n");
for L in B do for M in C1 do
if(not 2 in Union(L+M)) then Append(S,[L+2*M]); fi;
od; od;
for L in C2 do for M in B do
if(not 2 in Union(L+M)) then Append(S,[L+2*M]); fi;
od; od;
Print("count=",Size(S),"\n");
od;
return S;
end;;
Just so the reader can independently confirm these calculations, here is the output:
gap> S:=user3740Count(2);;
k=0 0 0 1
count=0
k=1 4 1 0
count=4
k=2 0 0 0
count=4
gap> S:=user3740Count(4);;
k=0 0 0 1
count=0
k=1 0 1 16
count=0
k=2 24 16 96
count=2072
k=3 284 96 276
count=58808
k=4 1200 276 405
count=315836
k=5 2276 405 304
count=571892
k=6 2032 304 114
count=638352
k=7 848 114 20
count=643752
k=8 156 20 2
count=643888
gap> Random(S);
[ [ 0, 0, 0, 0 ], [ 2, 0, 1, 2 ], [ 0, 1, 1, 0 ], [ 1, 2, 0, 0 ] ]
gap> Random(S);
[ [ 2, 0, 2, 1 ], [ 1, 1, 0, 2 ], [ 0, 0, 1, 0 ], [ 1, 2, 0, 0 ] ]
gap> Random(S);
[ [ 0, 1, 1, 0 ], [ 1, 2, 0, 2 ], [ 0, 0, 0, 1 ], [ 2, 1, 0, 2 ] ]
gap> Random(S);
[ [ 0, 2, 1, 0 ], [ 0, 0, 0, 0 ], [ 1, 1, 1, 2 ], [ 2, 0, 0, 0 ] ]
gap> Random(S);
[ [ 0, 2, 0, 2 ], [ 1, 1, 2, 0 ], [ 1, 0, 0, 1 ], [ 0, 1, 2, 0 ] ]
gap> Size(Filtered(S,L->Sum(Sum(L))=4));
336
gap>
The numbers are k (as in the above formula), |B|, |C1|, |C2|, then "count" is the running sum.