19.4.2012 Čtvrtek 9:15

Máte někdo zadání? Jde o to umístění maxima černých kuliček na tu mřížku tak, aby na vodorovných, svislých a diagonálách nebyly víc jak 2.

% NESTIHL JSEM ULOHU c)
 
clear all % vymaze workspace (aktualni promenne)
close all %
clc % 
 
n = 8;
size = 2*n + 2*(2*n-1); %% pro n < 6 je pocet radku vetsi nez pocet sloupcu
if n > 5                
    size = n*n; 
end
 
A = zeros(size);
 
% horizontalni rady
for i = 1 : n %i znaci dalsi radek matice A
   for j = 1 : n
       A(i,j + (i-1)*n) = 1;
   end
end
 
% vertikalni rady
for i = 1 : n %i znaci dalsi radek matice A
   for j = 0 : n - 1
      A(n + i, i + j*n) = 1; 
   end
end
 
% diagonalni rady 1... od stredu doprava
for i = 1 : n %i znaci dalsi radek matice A
   for j = 0 : n - i  % na diagonale jich je nejvic, a pak je vzdy o jednu mene...
      A(2*n + i, i + j*(n+1)) = 1; 
   end
end
 
 
% diagonalni rady 2... od stredu dolu
for i = 1 : n - 1 %i znaci dalsi radek matice A
   for j = 0 : n - i - 1 % na diagonale jich je nejvic, a pak je vzdy o jednu mene...
      A(3*n + i, (1 + i*n) + j*(n+1)) = 1; 
   end
end
 
% antidiagonalni rady 1... od praveho vrchniho stredu doleva
for i = 1 : n %i znaci dalsi radek matice A
   for j = 0 : i - 1  % na diagonale jich je nejmene (jedna), a pak je vzdy o jednu vice...
      A(4*n + i - 1, i + j*(n-1)) = 1; 
   end
end
 
 
% antidiagonalni rady 2 ... od praveho vrchniho stredu dolu
for i = 1 : n - 1 %i znaci dalsi radek matice A
   for j = 0 : n - i - 1 % na diagonale jich je nejvic, a pak je vzdy o jednu mene...
      A(5*n + i - 1, ((i+1)*n) + j*(n-1)) = 1; 
   end
end
 
A
 
b = 2*ones(size, 1);
 
%%%%%% TORSCHE
 
% maximalisation
sense = -1;
 
% ctype (vsechno jsou NEROVNICE-L jako lower (<=)
ctype = char(ones(size,1) * 'L');
 
% lower bound = 0 (samy nuly)
lb = zeros(size,1);
 
% upper bound = 1 (true false)
ub = ones(size,1);
 
% crit vector
c = ones(size,1);
 
% vartype = I (vsechno je integer)
vartype = char(ones(size,1) * 'I');
 
% parametry solveru (limit 60 s)
schoptions=schoptionsset('ilpSolver','glpk','solverVerbosity',0,'solverTiLim',60);
 
% vyres...
[xmin,fmin,status,extra] = ilinprog(schoptions,sense,c,A,b,ctype,lb,ub,vartype);
 
% prevadim vystup torsche na human-readable info
pocetUmistenych = fmin + (n*n - size)
maticeUmistenych = zeros(n);
for i=1:n*n
    maticeUmistenych(1 + floor((i-1)/n), 1 + mod((i-1), n)) = xmin(i);
end
%maticeUmistenych
 
% vykreslim grafik
 
G = graph('adj', zeros(n*n));
 
for a=0 : n*n - 1
   if xmin(a + 1) == 1
       G.N(a + 1).graphicParam(1).facecolor = [1 0 0];
   end
end
 
graphedit(G, 'viewnodesnames', 'off');
 
 
for a=0 : n*n - 1
   graphedit('movenode', {a + 1, 200 + 30*mod(a, n), 200 + 30*floor(a/n)});   
end