Peaceable coexisting armies

Question

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

Answer 1

C, 476 bytes, DFS iterating white queens, O(2ⁿ²)

#define R return
#define Z(q)for(j=q;j<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>=0&&x<I&&y>=0&&y<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>=m;}for(i=!l?0:w[l-1]+1;i<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(2ⁿ)

#define R return
#define Z(q)for(j=q;j<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>=0&&x<I&&y>=0&&y<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<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>=m&&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<I;j++)
#define Z(r,q,t,v)for(i=0;i<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<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>=0&&x<I&&y>=0&&y<I?V[T(x,y)]=1:0;}g(E,N,C){int i,j,v[J],X[J],Y[J];if(E==m&&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 & 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 |        |
+---+----------------------+---------------------+-----------------+--------+

Answer 2

Clingo, 90 bytes

{q(1..n,1..n)}.a(X+(-I;0;I),Y+(0;I)):-q(X,Y),I=-n..n.:~K={q(X,Y)},{a(1..n,1..n)}n*n-K.[-K]

Demo

$ clingo peaceable.lp -cn=6
clingo version 5.1.0
Reading from peaceable.lp
Solving...
Answer: 1

Optimization: 0
Answer: 2
q(6,1) a(7,1) a(7,2) a(8,1) a(8,3) a(9,1) a(9,4) a(10,1) a(10,5) a(11,1) a(11,6) a(12,1) a(6,1) a(6,2) a(6,3) a(6,4) a(6,5) a(6,6) a(5,1) a(5,2) a(4,1) a(4,3) a(3,1) a(3,4) a(2,1) a(2,5) a(1,1) a(1,6) a(0,1) a(7,0) a(8,-1) a(9,-2) a(10,-3) a(11,-4) a(12,-5) a(6,-4) a(6,-3) a(6,-2) a(6,-1) a(6,0) a(5,0) a(4,-1) a(0,7) a(1,-4) a(2,-3) a(3,-2) a(6,-5) a(6,7) a(0,-5) a(12,7)
Optimization: -1
Answer: 3
q(1,6) q(6,1) a(7,1) a(7,2) a(7,6) a(8,1) a(8,3) a(9,1) a(9,4) a(10,1) a(10,5) a(11,1) a(11,6) a(12,1) a(6,1) a(6,2) a(6,3) a(6,4) a(6,5) a(6,6) a(5,1) a(5,2) a(5,6) a(4,1) a(4,3) a(4,6) a(3,1) a(3,4) a(3,6) a(2,1) a(2,5) a(2,6) a(1,1) a(1,2) a(1,3) a(1,4) a(1,5) a(1,6) a(0,1) a(0,5) a(0,6) a(-1,4) a(-1,6) a(-2,3) a(-2,6) a(-3,2) a(-3,6) a(-4,1) a(-4,6) a(-5,6) a(7,0) a(8,-1) a(9,-2) a(10,-3) a(11,-4) a(12,-5) a(6,-4) a(6,-3) a(6,-2) a(6,-1) a(6,0) a(5,0) a(4,-1) a(0,7) a(1,7) a(2,7) a(-1,8) a(1,8) a(3,8) a(-2,9) a(1,9) a(-3,10) a(1,10) a(-4,11) a(1,11) a(-5,12) a(1,-4) a(1,0) a(2,-3) a(3,-2) a(6,-5) a(6,7) a(4,9) a(5,10) a(6,11) a(1,12) a(-5,0) a(0,-5) a(7,12) a(12,7)
Optimization: -2
Answer: 4
q(1,6) q(6,1) q(6,6) a(7,1) a(7,2) a(7,5) a(7,6) a(8,1) a(8,3) a(8,4) a(8,6) a(9,1) a(9,3) a(9,4) a(9,6) a(10,1) a(10,2) a(10,5) a(10,6) a(11,1) a(11,6) a(12,1) a(12,6) a(6,1) a(6,2) a(6,3) a(6,4) a(6,5) a(6,6) a(5,1) a(5,2) a(5,5) a(5,6) a(4,1) a(4,3) a(4,4) a(4,6) a(3,1) a(3,3) a(3,4) a(3,6) a(2,1) a(2,2) a(2,5) a(2,6) a(1,1) a(1,2) a(1,3) a(1,4) a(1,5) a(1,6) a(0,1) a(0,5) a(0,6) a(-1,4) a(-1,6) a(-2,3) a(-2,6) a(-3,2) a(-3,6) a(-4,1) a(-4,6) a(-5,6) a(7,0) a(8,-1) a(9,-2) a(10,-3) a(11,-4) a(12,-5) a(12,0) a(6,-4) a(6,-3) a(6,-2) a(6,-1) a(6,0) a(5,0) a(4,-1) a(0,7) a(1,7) a(2,7) a(5,7) a(-1,8) a(1,8) a(3,8) a(4,8) a(-2,9) a(1,9) a(3,9) a(-3,10) a(1,10) a(2,10) a(-4,11) a(1,11) a(-5,12) a(0,12) a(1,-4) a(1,0) a(2,-3) a(3,-2) a(6,-5) a(6,7) a(6,8) a(4,9) a(6,9) a(5,10) a(6,10) a(6,11) a(1,12) a(6,12) a(-5,0) a(0,-5) a(0,0) a(7,7) a(8,8) a(9,9) a(10,10) a(11,11) a(7,12) a(12,7) a(12,12)
Optimization: -3
Answer: 5
q(1,1) q(1,6) q(6,1) q(6,6) a(7,1) a(7,2) a(7,5) a(7,6) a(8,1) a(8,3) a(8,4) a(8,6) a(9,1) a(9,3) a(9,4) a(9,6) a(10,1) a(10,2) a(10,5) a(10,6) a(11,1) a(11,6) a(12,1) a(12,6) a(6,1) a(6,2) a(6,3) a(6,4) a(6,5) a(6,6) a(5,1) a(5,2) a(5,5) a(5,6) a(4,1) a(4,3) a(4,4) a(4,6) a(3,1) a(3,3) a(3,4) a(3,6) a(2,1) a(2,2) a(2,5) a(2,6) a(1,1) a(1,2) a(1,3) a(1,4) a(1,5) a(1,6) a(0,1) a(0,2) a(0,5) a(0,6) a(-1,1) a(-1,3) a(-1,4) a(-1,6) a(-2,1) a(-2,3) a(-2,4) a(-2,6) a(-3,1) a(-3,2) a(-3,5) a(-3,6) a(-4,1) a(-4,6) a(-5,1) a(-5,6) a(7,-5) a(7,0) a(8,-1) a(9,-2) a(10,-3) a(11,-4) a(12,-5) a(12,0) a(6,-4) a(6,-3) a(6,-2) a(6,-1) a(6,0) a(5,-3) a(5,0) a(4,-2) a(4,-1) a(3,-1) a(2,0) a(0,7) a(1,7) a(2,7) a(5,7) a(-1,8) a(1,8) a(3,8) a(4,8) a(-2,9) a(1,9) a(3,9) a(-3,10) a(1,10) a(2,10) a(-4,11) a(1,11) a(-5,7) a(-5,12) a(0,12) a(1,-5) a(1,-4) a(1,-3) a(1,-2) a(1,-1) a(1,0) a(2,-3) a(3,-2) a(6,-5) a(6,7) a(6,8) a(4,9) a(6,9) a(5,10) a(6,10) a(6,11) a(1,12) a(6,12) a(-5,-5) a(-5,0) a(-4,-4) a(-3,-3) a(-2,-2) a(-1,-1) a(0,-5) a(0,0) a(7,7) a(8,8) a(9,9) a(10,10) a(11,11) a(7,12) a(12,7) a(12,12)
Optimization: -4
Answer: 6
q(1,2) q(1,3) q(2,2) q(2,3) q(2,6) a(7,1) a(7,2) a(7,3) a(7,6) a(8,2) a(8,3) a(8,6) a(6,2) a(6,3) a(6,6) a(5,2) a(5,3) a(5,5) a(5,6) a(4,1) a(4,2) a(4,3) a(4,4) a(4,5) a(4,6) a(3,1) a(3,2) a(3,3) a(3,4) a(3,5) a(3,6) a(2,1) a(2,2) a(2,3) a(2,4) a(2,5) a(2,6) a(1,1) a(1,2) a(1,3) a(1,4) a(1,5) a(1,6) a(0,1) a(0,2) a(0,3) a(0,4) a(0,5) a(0,6) a(-1,1) a(-1,2) a(-1,3) a(-1,4) a(-1,5) a(-1,6) a(-2,2) a(-2,3) a(-2,5) a(-2,6) a(-3,1) a(-3,2) a(-3,3) a(-3,6) a(-4,2) a(-4,3) a(-4,6) a(-5,2) a(-5,3) a(7,-4) a(7,-3) a(7,-2) a(8,-4) a(8,-3) a(8,0) a(6,-3) a(6,-2) a(6,-1) a(5,-2) a(5,-1) a(5,0) a(4,-1) a(4,0) a(3,0) a(2,0) a(1,7) a(2,7) a(3,7) a(5,7) a(0,8) a(1,8) a(2,8) a(4,8) a(-2,7) a(-1,9) a(1,9) a(2,9) a(-3,7) a(-3,8) a(-2,10) a(2,10) a(-4,7) a(-4,8) a(-4,9) a(-3,11) a(-5,8) a(-5,9) a(-4,12) a(1,-4) a(1,-3) a(1,-2) a(1,-1) a(1,0) a(2,-4) a(2,-3) a(2,-2) a(2,-1) a(6,7) a(6,8) a(5,9) a(6,10) a(2,11) a(2,12) a(-5,-4) a(-5,-3) a(-4,-4) a(-4,-3) a(-4,-2) a(-4,0) a(-3,-3) a(-3,-2) a(-3,-1) a(-2,-2) a(-2,-1) a(-2,0) a(-1,-1) a(-1,0) a(0,0) a(7,7) a(7,8) a(8,8) a(7,9) a(8,9) a(7,11) a(8,12)
Optimization: -5
OPTIMUM FOUND

Models       : 6
  Optimum    : yes
Optimization : -5
Calls        : 1
Time         : 0.733s (Solving: 0.71s 1st Model: 0.00s Unsat: 0.71s)
CPU Time     : 0.730s

Answer 3

Python 2 | 325 284 217 bytes

Try it online!

from itertools import*
N=input()
r=range(N*N)
for n in r:
 g=r
 for s in combinations(g,n):
    for p in s:g=filter(lambda q:all([abs(q%N-p%N)!=abs(q/N-p/N),q%N!=p%N,q/N!=p/N]),g)
    if len(g)>=n:break
    g=r
 else:exit(n-1)

Edit: Replaced tuples with integers in g and other trivial edits.

Edit2: Bytes down to 217 thanks to musicman523 and CalculatorFeline!

How it works

The program iterates over all possible positions of n queens and filters out non-peaceful points in g caused due to position of the queens. If the remaining points is greater than n then it means that it is possible to for n queen armies to stay peacefully. If for the next value of n, no peaceful situation is found, then the program exits with exit code : n-1, which is the answer. In short, it is brute force

The program can be made faster by changing the last two lines to

for n in range(N**2):
    if not z(n,N):print n-1;break

Answer 4

Haskell, 169 156 153 152 bytes

k!(a:b)=k!b++[a:c|c<-(k-1)!b]
k!x=[x|k==0]
q&l|p<-q![[x,y,x-y,x+y]|x<-l,y<-l]=or[all and$zipWith(/=)<$>b<*>w|b<-p,w<-p]
g n=last$filter(&[1..n])[0..n*n]

Defines a function g, may be further golfable. Try it online! On TIO, when compiled with -O2, this takes about 36 seconds for n = 4 and times out on n = 5. The time complexity should be O(n²4ⁿ²).

Explanation

We iterate over the possible values for the number of queens (q). For each q, we generate all pairs of size-q subsets of [1..n]², one set of black queens (b) and one of white queens (w). Then, each element of b is checked against each element of w to see if they share a row, column, diagonal or anti-diagonal. This also takes care of two pieces sharing the same coordinate. The greatest value of q that admits a peaceable configuration is the final value.

The first two lines of the program define the function !, which computes the length-k subsequences of a list x. The implementation is by a basic recursion: either choose the first element to be in the set or not and recurse to the tail, decrementing k if necessary. Then the empty list or reached, check that k==0.

k!(a:b)=       -- ! on integer k and list with head a and tail b is
 k!b++         -- the concatenation of k!b and
 [a:c|         -- the list of lists a:c where
  c<-(k-1)!b]  -- c is drawn from (k-1)!b.
k!x=           -- If x doesn't have the form a:b (which means that it's empty),
 [x|           -- the result is a list containing x
  k==0]        -- but only if k==0.

The second auxiliary function & takes a number q (number of queens on either side) and a list l (the x-coordinates of the board, also used as the y-coordinates), and returns a Boolean value indicating if a peaceable configuration exists. We first compute p, the list of length-q subsequences of the list of values [x,y,x-y,x+y], where x and y range over l. They represent the row, column, diagonal and anti-diagonal of a square (x,y) on the board.

q&l               -- & on inputs q and l:
 |p<-             -- define p as
  q!              -- the q-subsequences of
  [[x,y,x-y,x+y]  -- the list of these 4-lists
   |x<-l,y<-l]    -- where x and y are drawn independently from l.

Next we have the result of q&l. We draw two subsequences b and w from p, pair the 4-lists of them together in all possible ways, and check that they always differ in all 4 coordinates. If some choices of b and w result in a truthy result, we return True.

=or            -- Does the following list contain a True:
 [all and$     -- every list contains only truthy values
  zipWith(/=)  -- if we zip with inequality
  <$>b<*>w     -- all elements of b and w in all possible ways,
 |b<-p,w<-p]   -- where b and w are drawn independently from p.

The last line is the main function. Given n, it simply finds the largest possible value of q for which q&[1..n] is true.

g n=              -- g on input n is
 last$            -- the last of
 filter(&[1..n])  -- those values q for which q&[1..n] is true
 [0..n*n]         -- in this list.