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 ]

% a naive algorithm to check all n! assignments and 
% select the assignment with the smallest cost

[n,n] = size(C);
p = perms(1:n);
[m,q] = size(p);
z = zeros(1,m);

for ip = 1 : m
    X = zeros(n); % the assignment matrix
    for i = 1:n
        X(i,p(ip,i)) = 1;
    end
    z(ip)= sum(sum(C.*X));
end

[zMin,iMin] = min(z);
X = zeros(n); % the assignment matrix
for i = 1:n
        X(i,p(iMin,i)) = 1;
end

zMin
X
