Peaceable coexisting armies In the game of chess, there is piece called the queen that may attack any other piece that is on the same row, column or diagonal. In chess there are typically two sides, black and white, with each piece belonging to one of the teams. Pieces may not attack pieces belong to the same team.  

Your goal is to find out the largest peaceable coexisting armies for a square board. That is the largest number of black and white queens that can fit on the board such that no two queens can attack each other and the number of black queens is equal to the number of white queens.

You will receive as input the side length of a square board, and should output the number of size of the largest peaceable coexisting armies that can fit on that board.

This is code-golf so standard rules for the tag apply.

OEIS A250000

These test cases encompass all known answers. Your solution should be a generalized answer that, given enough computing power and time, can compute the solution for any input value.


1: 0
2: 0
3: 1
4: 2
5: 4
6: 5
7: 7
8: 9
9: 12
10: 14
11: 17
12: 21
13: 24
C, 476 bytes, DFS iterating white queens, O(2n2)

#define R return
#define Z(q)for(j=q;j&lt;I;j++)
#define Q(q)memset(q,0,4*J);
#define U(q)S(w[k]/I q j,w[k]%I+j)
int*c,*w,*Y,j,k,r,I,J,m;T(i,j){R i*I+j;}S(x,y){x&gt;=0&amp;&amp;x&lt;I&amp;&amp;y&gt;=0&amp;&amp;y&lt;I?Y[T(x,y)]=1:0;}g(l){int i;if(l==m){Q(Y)for(k=m;k--;){Z(0)Y[T(w[k]/I,j)]=Y[T(j,w[k]%I)]=1;Z(-I)U(+),U(-);}for(r=k=J;k--;)r-=Y[k];R r&gt;=m;}for(i=!l?0:w[l-1]+1;i&lt;J;i++){if(!c[i]){c[i]=1;w[l]=i;if(g(l+1))R 1;c[i]=0;}}R 0;}f(s){I=s;J=I*I;int C[J],W[J],y[J];c=C;w=W;Y=y;for(m=1;;m++){Q(c)if(!g(0))R m-1;}}


518 bytes, DFS with pruning, O(2n)

#define R return
#define Z(q)for(j=q;j&lt;I;j++)
#define Q(q)memset(q,0,4*J);
#define V(Q)t=Q;if(!Y[t]){G-=Y[t]=1;b[B++]=t;}
#define F(q)if(S(x q j,y+j)){V((x q j)*I+y+j)}
int*c,*w,*Y,j,k,r,I,J,m;S(x,y){R x&gt;=0&amp;&amp;x&lt;I&amp;&amp;y&gt;=0&amp;&amp;y&lt;I;}D(l,H){int i,b[J],B,t,x,y,G;if(l==m)R 1;for(i=!l?0:w[l-1]+1;i&lt;J;i++){if(!c[i]){c[i]=1;w[l]=i;x=i/I;y=i%I;G=H;Z(B=0){V(x*I+j)V(j*I+y)}Z(-I){F(+)F(-)}if(G&gt;=m&amp;&amp;D(l+1,G))R 1;for(j=B;j--;)Y[b[j]]=0;c[i]=0;}}R 0;}f(s){I=s;J=I*I;int C[J],W[J],y[J];c=C;w=W;Y=y;for(m=1;;m++){Q(c)Q(Y)if(!D(0,J))R m-1;}}


577 bytes, DFS iterating white and black queens, O(?)

#define R return
#define U(V,r,q)S(V,r[i]/I q j,r[i]%I+j)
#define W(q)for(j=q;j&lt;I;j++)
#define Z(r,q,t,v)for(i=0;i&lt;r;i++){t[q[i]]=1;W(0)v[T(q[i]/I,j)]=v[T(j,q[i]%I)]=1;W(-I)U(v,q,+),U(v,q,-);};
#define P(K,L,M)memcpy(v,K,4*J);for(i=0;i&lt;J;i++)if(!v[i]){L[M++]=i;if(g(E,N,!C))R 1;M--;};
int*w,*b,m,I,J;T(i,j){R i*I+j;}Q(int*q){memset(q,0,4*J);}S(V,x,y)int*V;{x&gt;=0&amp;&amp;x&lt;I&amp;&amp;y&gt;=0&amp;&amp;y&lt;I?V[T(x,y)]=1:0;}g(E,N,C){int i,j,v[J],X[J],Y[J];if(E==m&amp;&amp;N==m)R 1;Q(X);Q(Y);Z(E,w,X,Y)Z(N,b,Y,X)if(C){P(Y,b,N)}else{P(X,w,E)}R 0;}f(q){I=q,J=I*I;int W[J],B[J];w=W,b=B;for(m=1;;m++)if(!g(0,0,0))R m-1;}


Basically, the code iterates over possibilities of white queen and check whether black queen could be placed then.

Speed reference table (in seconds):

+---+----------------------+---------------------+-----------------+--------+
| n |      DFS w &amp; b       |        DFS w        |  DFS w/ pruning | Clingo |
+---+----------------------+---------------------+-----------------+--------+
| 3 |                 0.00 |                0.00 |            0.00 |   0.01 |
| 4 |                 0.00 |                0.00 |            0.00 |   0.02 |
| 5 |                 0.47 |                0.16 |            0.00 |   0.04 |
| 6 |                20.62 |                1.14 |            0.00 |   0.60 |
| 7 |              1125.07 |              397.88 |            0.63 |  18.14 |
| 8 |                      |                     |            1.28 | 979.35 |
| 9 |                      |                     |           23.13 |        |
+---+----------------------+---------------------+-----------------+--------+