% A075458: Minimum number of queens needed to occupy or attack all squares of an n X n chessboard.
% Program takes about 1 minute for n=13, but becomes significantly slower for larger n.
% 
% Dmitry Kamenetsky, 11th September 2019

N=6;    %board size

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

tic

M=N*N;    %number of variables

f=ones(M,1);      %minimize sum

%binary integers: 0 or 1
intcon=1:M;       
lb=zeros(M,1);        
ub=ones(M,1);

%constraints
A=zeros(M,M);
b=-ones(1,M);

cur1=0;
for r=1:N
  for c=1:N
    cur1=cur1+1;
    cur2=0;
    for r2=1:N
      for c2=1:N
        cur2=cur2+1;
        %Queen at (r2,c2) can attack location at (r,c)
        if r2==r || c2==c || abs(r2-r)==abs(c2-c)     
          A(cur1,cur2)=-1;
        end
      end
    end
  end
end

%solve linear integer program
x = intlinprog(f,intcon,A,b,[],[],lb,ub)


%print optimal placement of queens (1)
cur=0;
for r=1:N
  for c=1:N
    cur=cur+1;
    fprintf('%d',x(cur));
  end
  fprintf('\n');
end
fprintf('total queens needed: %d\n',sum(x));

toc;