function W = solver(B)

b = B;
W = zeros(0,4);
numbers = sortNumbers(B);
lines = zeros(0,6);

% find easy connectable islands (without bridges, very fast
for ii=1:size(numbers,1)
    N = numbers(ii,2);
    indN = B==N;

    [row col] = find(indN);
    nodes = [row,col];

    root = nodes(1,:);
    delNodes = nodes(1,:);
    nodes(1,:) = [];

    activeNode = root;
    cnt = 0;
    firstPoint = root(1:2);
    while ~isempty(nodes)
        nearestNodeInd = findNearestNode(activeNode,nodes);
        nn = nodes(nearestNodeInd,:);
        [path b1] = findPath(activeNode, nn, b, N);
        if ~isempty(path) && all(path(end,3:4)==nn)
            %path(:,5) = repmat(N, size(path,1),1);
            W = [W;path];
            lastPoint = nn;
            b = b1;
            cnt = cnt+1;
            nodes(nearestNodeInd,:) = [];
            activeNode = nn;
        else
            lastPoint = activeNode;
            lines = [lines; [firstPoint lastPoint, N, cnt]];
            cnt=0;
            activeNode = nodes(1,:);
            nodes(1,:) = [];
            firstPoint = activeNode;
            lastPoint = firstPoint;
        end
    end
    lines = [lines; [firstPoint lastPoint, N, cnt]];    
end

% try to connect islands with help of bridges
for i=1:size(numbers,1)
    N = numbers(i,2);
    islands = lines(:,5);
    ind = find(islands==N);
    if length(ind) > 1
        [paths b] = connectIslands(lines(ind,:),b, N);
        W = [W;paths];
    end
end

W = W(:,1:4);


function [paths b] = connectIslands(lines, b, N)

paths = [];
l = sortrows(lines,6);
l=l(end:-1:1,:);

nodes = l(:,1:4);
i = 2;
startPoint1 = nodes(1,1:2);
endPoint1 = nodes(1,3:4);
while i<=size(nodes,1)
    startPoint2 = nodes(i,1:2);
    endPoint2 = nodes(i,3:4);
    [path b] = findPath(startPoint1, startPoint2, b, N, true);
    if ~isempty(path) && all(path(end,3:4)==startPoint2)
        paths = [paths; path];
        startPoint1 = endPoint2;
        nodes(i,:) = [];
        %i=i+1;
        continue
    else
        [path b] = findPath(endPoint1, startPoint2, b, N, true);        
    end
    
    if ~isempty(path) && all(path(end,3:4)==startPoint2)
        paths = [paths; path];
        endPoint1 = endPoint2;
        nodes(i,:) = [];
        %i=i+1;
        continue
    else
        [path b] = findPath(startPoint1, endPoint2, b, N, true);
    end
    
    if ~isempty(path) && all(path(end,3:4)==endPoint2)
        paths = [paths; path];
        startPoint1 = startPoint2;
        nodes(i,:) = [];
        %i=i+1;
        continue
    else
        [path b] = findPath(endPoint1, endPoint2, b, N, true);
    end
    
    if ~isempty(path) && all(path(end,3:4)==endPoint2)
        paths = [paths; path];
        endPoint1 = startPoint2;
        nodes(i,:) = [];
        %i=i+1;
        continue
    end

    nodes(i,:) = [];
    %i = i+1;
end




% #########################################################################
function [path b] = findPath(n1, n2, b, N, allowBridges)

if nargin == 4
    allowBridges = false;
end

path = [];
if (all(n1==n2))
    return
end

[newNode b useBridge node2] = findClosestFreeNode(n1, n2, b, N);
if isempty(newNode)
    return
end

path = [path; [n1 newNode]];
if useBridge
    path = [path; [newNode newNode]; [newNode node2]];
    newNode = node2;
end
[newPath b] = findPath(newNode, n2, b, N);
path = [path; newPath];



% #########################################################################
function [node b useBridge node2] = findClosestFreeNode(n1, n2, b, N, allowBridges)

if nargin == 4
    allowBridges = false;
end

node = [];
node2 = [];
useBridge = false;
horz = n2(2)-n1(2);
vert = n2(1)-n1(1);

%   4
% 3   1
%   2
if horz == 1 && vert == 0
    node = n1 + [0 1];
    return;
end
if horz == -1 && vert == 0
    node = n1 - [0 1];
    return
end
if horz == 0 && vert == 1
    node = n1 + [1 0];
    return
end
if horz == 0 && vert == -1
    node = n1 - [1 0];
    return
end

incr = [0 1; 1 0; 0 -1; -1 0];
if horz>0
    if vert>0
        order = [1 2 4];
    else
        order = [1 4 2];
    end
elseif horz < 0
    if vert>0
        order = [3 2 4];
    else
        order = [3 4 2];
    end
else
    if vert>0
        order = [2 1 3];
    else
        order = [4 1 3];
    end
end

if n1(1)==1
    order(order==4) =[];
end
if (n1(1) == size(b,1))
    order(order==2) = [];
end
if (n1(2)==1)
    order(order==3) = [];
end
if (n1(2)== size(b,2))
    order(order==1) = [];
end

found = false;
for i=1:length(order)
    nodeT = n1+incr(order(i),:);
    if b(nodeT(1),nodeT(2)) == 0
        b(nodeT(1),nodeT(2)) = -1;
        node = nodeT;
        found = true;
        break
    end
end

if found
    return
end

node2 = [];
% if allowBridges
%     for i=1:length(order)
%         nodeT = n1+incr(order(i),:);
%         if (b(nodeT(1),nodeT(2)) == -1)
%             nextNode = nodeT+incr(order(i),:);
%             if isValid(nextNode,b) && b(nextNode(1),nextNode(2)) == 0
%                 b(nodeT(1),nodeT(2)) = -2;
%                 useBridge = true;
%                 node = nodeT;
%                 node2 = nextNode;
%             end
%             break
%         end
%     end
% end


function ret = isValid(node, b)

ret = node(1)>0 && node(1)<= size(b,1) && node(2)>0 && node(2)<size(b,2);


% #########################################################################
function ind = findNearestNode(a, nodes)

a = repmat(a,size(nodes,1),1);
dists = sum(abs(a-nodes),2);
[dummy ind] = min(dists);


% #########################################################################
function N = sortNumbers(b)

numbers = unique(b);
numbers(numbers==0) = [];
sortedN = [zeros(length(numbers),1), numbers(:)];
for i=1:length(numbers)
    num = numbers(i);
    gain = sum(sum(b==num))*num;
    if gain>num
        sortedN(i,1) = sum(sum(b==num))*num;
    end
end
sortedN = sortrows(sortedN);
sortedN(sortedN==0,:) = [];
N = sortedN(end:-1:1,:);