MATLAB: Find the unique path in a matrix

doit4megraphmatrixoptimization

Hello! I have a matrix (shown below). The matrix is the possible indices of a vector. The width of the matrix is 18 here. The width varies for different examples. We have to choose one index from each column so that the final answer, which is a vector of length 18, should be unique. That means the final vector, if sorted, is exactly 1,2,3…,18. A sample solution is shown in the attached picture.
I do not have "graph" on my Matlab R2015a. Maybe the optimization function "fgoalattain" helps. Thank you for your help!
13  6  1  1  1  2  5  2  7  9  3  8  9  9  1  8  6  6
1  2  2  2  3  12  6  8  9  10  11  11  10  15  4  12  14  14
12  12  3  4  4  16  4  12  10  15  7  12  15  17  10  16  1  2
16  16  11  11  8  7  8  16  15  17  9  16  5  18  15  13  2  16
5  5  3  14  12  9  14  5  6  6  17  12  6  15  6  11  16  1
6  9  4  3  16  15  1  13  13  13  5  5  13  17  9  12  2  4
10  15  15  4  9  17  2  8  14  6  18  13  NaN  6  10  16  3  NaN
15  17  17  11  10  14  3  12  6  14  NaN  2  NaN  13  15  15  11  NaN
18  6  18  9  15  7  4  7  1  2  NaN  8  NaN  14  18  17  NaN  NaN
6  13  10  15  13  9  NaN  10  3  3  NaN  12  NaN  2  6  9  NaN  NaN
13  NaN  17  18  NaN  10  NaN  15  4  4  NaN  16  NaN  3  14  15  NaN  NaN
14  NaN  2  7  NaN  5  NaN  9  12  8  NaN  15  NaN  4  NaN  2  NaN  NaN
NaN  NaN  3  15  NaN  6  NaN  10  16  11  NaN  NaN  NaN  12  NaN  8  NaN  NaN
NaN  NaN  11  17  NaN  NaN  NaN  8  5  12  NaN  NaN  NaN  9  NaN  16  NaN  NaN
NaN  NaN  NaN  18  NaN  NaN  NaN  16  6  16  NaN  NaN  NaN  15  NaN  NaN  NaN  NaN
NaN  NaN  NaN  1  NaN  NaN  NaN  NaN  13  5  NaN  NaN  NaN  NaN  NaN  NaN  NaN  NaN
NaN  NaN  NaN  4  NaN  NaN  NaN  NaN  NaN  13  NaN  NaN  NaN  NaN  NaN  NaN  NaN  NaN

Best Answer

How about this code? Let A be your matrix, which you have given. This code is like a trial/ random, for few runs it will throw error, for the paths which we expect, it will run and show no error, this is the path which you expect.
[nx,ny] = size(A) ;
path = zeros(1,ny) ;
%%consider first column 
col = A(:,1) ;
col = col(~isnan(col)) ; % remove NaN's

path(1) = randsample(col,1) ;
for i = 2:ny
    col = A(:,i) ;
    col = col(~isnan(col)) ; % remove NaN's
    % Remove already selected number in path from this col
    col = setdiff(col,path(1:i)) ;
    %%pick one number in random from the column
    if length(col) ~=1
        path(i) = randsample(col,1) ;
    else
        path(i) = col ;
    end
end
I have run the above code for seven times, for the first six times, it throwed error and the successful result was:
path = [ 10    16     1    14    15     7     6     8    12    13    17    11     5     4
    18     9     3     2];
The above path satisfies your conditions.
Related Question