clear all
close all
C = [   20,15,10,10,17,23,25,5,15; ...
        10,10,12,15,9,7,8,7,8; ...
        12,9,9,10,10,5,7,13,9; ...
        13,14,10,15,15,5,8,20,10; ...
        12,13,10,15,14,5,9,20,10; ...
        15,14,15,16,15,5,10,20,10; ...
        7,9,12,12,7,6,7,15,12; ...
        5,6,8,8,5,4,5,10,7; ... 
        5,6,8,8,5,4,5,10,7 ];

% the computational algorithm to approach 
% to the optimal solution with smallest cost

[n,n] = size(C);
X = sparse(zeros(n)); % the assignment matrix

% first assignment: row-by-row
for i = 1:n
       [Crow,Irow] = sort(C(i,:));
        for j = 1:length(Crow)
            if (~any(X(:,Irow(j)))) % in this case the column Irow(j) is not yet assigned
                X(i,Irow(j)) = 1;
                break; % break the j-loop
            end
        end
end
z = sum(sum(C.*X))

k = 1; % counter of new assignments

while (k ~= 0)
    k = 0; % new loop

    for i = 1:n
        d = zeros(1,n);
        indD = zeros(1,n);
        iZ = find(X(i,:));
        for j = 1:n
            if (j ~= iZ)
                jZ = find(X(:,j));
                d(j) = C(i,j)+C(jZ,iZ)-C(i,iZ)-C(jZ,j);
                indD(j) = jZ;
            end
        end
        % interchange of the assignment
        [dMin,iMin] = min(d);
        if (dMin < 0)
            X(i,iZ) = 0;
            X(indD(iMin),iMin) = 0;
            X(i,iMin) = 1;
            X(indD(iMin),iZ) = 1;
            z = sum(sum(C.*X))
            k = k+1;
        end  
    end
    k
end

X