function W = solver(B)

W = zeros(0,4);
% find all pins
values = unique(B);
% find number of pins
for pin = 2:length(values)
    pins(pin-1).value = values(pin);
    [pins(pin-1).rows,pins(pin-1).cols] = find(B==pins(pin-1).value);
    pins(pin-1).num = length(pins(pin-1).rows);
end

[c,index]=min(cost(B,pins)');
workB = B;

while c < inf    
    current_pin.rows = pins(index).rows;
    current_pin.cols = pins(index).cols;
    solder.rows = [];
    solder.cols = [];
    
    % find a good starting point...
    start.rows = sum(current_pin.rows)/length(current_pin.rows);
    start.cols = sum(current_pin.cols)/length(current_pin.cols);
    [junk first] = findShortestPath(start,current_pin);
    startIndex=intersect(find(current_pin.rows==first(1)),find(current_pin.cols==first(2)));
    solder.rows(length(solder.rows)+1)=current_pin.rows(startIndex);
    solder.cols(length(solder.cols)+1)=current_pin.cols(startIndex);
    current_pin.rows = rmrow(current_pin.rows,startIndex);
    current_pin.cols = rmrow(current_pin.cols,startIndex);
    num = 1;
    while num < pins(index).num
        [from to] = findShortestPath(solder,current_pin);
        [newMoves, workB_, solder_, connected] = moveTo(from, to, workB, solder, pins(index).value);
        if connected == 1
            if (pins(index).value - length(newMoves(:,1))) > 0
                workB = workB_;
                solder = solder_;
                W = [W; newMoves];
            end
        end
        toIndex=intersect(find(current_pin.rows==to(1)),find(current_pin.cols==to(2)));
        current_pin.rows = rmrow(current_pin.rows,toIndex);
        current_pin.cols = rmrow(current_pin.cols,toIndex);
        num = num + 1;
    end
    pins(index).value = 0;
    [c,index]=min(cost(B,pins)');
end
end

function c=cost(B,pins)
for pin = 1:length(pins)
    c(pin) = (pins(pin).num*pins(pin).value/(max(pins(pin).rows)-min(pins(pin).rows))/(max(pins(pin).cols)-min(pins(pin).cols)))^-1;
    if (c(pin)==0)
        c(pin) = inf;
    end
end
end

function [from, to]=findShortestPath(solder,current_pin)
shortest = inf;
from = [];
to = [];
for pinLooper = 1:length(current_pin.rows)
    for solderLooper = 1:length(solder.rows)
        if abs(solder.rows(solderLooper)-current_pin.rows(pinLooper)) + abs(solder.cols(solderLooper)-current_pin.cols(pinLooper)) < shortest
            shortest = abs(solder.rows(solderLooper)-current_pin.rows(pinLooper)) + abs(solder.cols(solderLooper)-current_pin.cols(pinLooper));
            to = [current_pin.rows(pinLooper) current_pin.cols(pinLooper)];
            from = [solder.rows(solderLooper) solder.cols(solderLooper)];
        end
    end
end
end

function [newMoves, workB, solder, yoho] = moveTo(from, to, workB, solder, val)
newMoves = [];
yoho = 0;

fromRow = from(1);
fromCol = from(2);
toRow = to(1);
toCol = to(2);

xDir = sign(toCol - fromCol);
yDir = sign(toRow - fromRow);

% in the righ column
if xDir==0
    % the end is right next door
    if (fromRow + yDir) == toRow
        newMoves = [fromRow, fromCol, fromRow+yDir, fromCol];
        solder.rows = [solder.rows; fromRow+yDir];
        solder.cols = [solder.cols; fromCol];
        yoho = 1;
        return
    end
    % can move in the desired direction
    if fromRow+yDir > 0 && fromRow+yDir < length(workB(:,1))
        if (workB((fromRow+yDir),fromCol)==0)
            workB(fromRow+yDir,fromCol)=-val;
            [tmpMove, tmpWorkB, tmpSolder, tmpYoho] = moveTo([(fromRow+yDir),fromCol],to,workB,solder,val);
            yoho = tmpYoho;
            newMoves = [tmpMove; fromRow, fromCol, fromRow+yDir, fromCol];
            solder.rows = [tmpSolder.rows; fromRow+yDir];
            solder.cols = [tmpSolder.cols; fromCol];
            workB=tmpWorkB;
            workB(fromRow+yDir,fromCol)=-val;
            return
        end
    end
    % can move perpendicular
    if fromCol+1 > 0 && fromCol+1 < length(workB(1,:))
        if (workB(fromRow,(fromCol + 1))==0)
            workB(fromRow,fromCol+1)=-val;
            [tmpMove, tmpWorkB, tmpSolder, tmpYoho] = moveTo([fromRow,(fromCol + 1)],to,workB,solder,val);
            yoho = tmpYoho;
            newMoves = [tmpMove; fromRow, fromCol, fromRow, fromCol+1];
            solder.rows = [tmpSolder.rows; fromRow];
            solder.cols = [tmpSolder.cols; fromCol+1];
            workB=tmpWorkB;
            workB(fromRow,fromCol+1)=-val;
            return
        end
    end
    if fromCol-1 > 0 && fromCol-1 < length(workB(1,:))
        if (workB(fromRow,(fromCol - 1))==0)
            workB(fromRow,fromCol-1)=-val;
            [tmpMove, tmpWorkB, tmpSolder, tmpYoho] = moveTo([fromRow,(fromCol - 1)],to,workB,solder,val);
            yoho = tmpYoho;
            newMoves = [tmpMove; fromRow, fromCol, fromRow, fromCol-1];
            solder.rows = [tmpSolder.rows; fromRow];
            solder.cols = [tmpSolder.cols; fromCol-1];
            workB=tmpWorkB;
            workB(fromRow,fromCol-1)=-val;
            return
        end
    end
    % last option is to move away
    if fromRow-yDir > 0 && fromRow-yDir < length(workB(:,1))
        if (workB((fromRow-yDir),fromCol)==0)
            workB(fromRow-yDir,fromCol)=-val;
            [tmpMove, tmpWorkB, tmpSolder, tmpYoho] = moveTo([(fromRow-yDir),fromCol],to,workB,solder,val);
            yoho = tmpYoho;
            newMoves = [tmpMove; fromRow, fromCol, fromRow-yDir, fromCol];
            solder.rows = [tmpSolder.rows; fromRow-yDir];
            solder.cols = [tmpSolder.cols; fromCol];
            workB=tmpWorkB;
            workB(fromRow-yDir,fromCol)=-val;
            return
        end
    end
% in the right row
elseif yDir==0
    % the end is right next door
    if (fromCol + xDir) == toCol
        newMoves = [fromRow, fromCol, fromRow, fromCol+xDir];
        solder.rows = [solder.rows; fromRow];
        solder.cols = [solder.cols; fromCol+xDir];
        yoho = 1;
        return
    end
    % can move in the desired direction
    if fromCol+xDir > 0 && fromCol+xDir < length(workB(1,:))
        if (workB(fromRow,(fromCol + xDir))==0)
            workB(fromRow,fromCol+xDir)=-val;
            [tmpMove, tmpWorkB, tmpSolder, tmpYoho] = moveTo([fromRow,(fromCol + xDir)],to,workB,solder,val);
            yoho = tmpYoho;
            newMoves = [tmpMove; fromRow, fromCol, fromRow, fromCol+xDir];
            solder.rows = [tmpSolder.rows; fromRow];
            solder.cols = [tmpSolder.cols; fromCol+xDir];
            workB=tmpWorkB;
            workB(fromRow,fromCol+xDir)=-val;
            return
        end
    end
    % can move perpendicular
    if fromRow+1 > 0 && fromRow+1 < length(workB(:,1))
        if (workB(fromRow + 1,fromCol)==0)
            workB(fromRow+1,fromCol)=-val;
            [tmpMove, tmpWorkB, tmpSolder, tmpYoho] = moveTo([fromRow+1,fromCol],to,workB,solder,val);
            yoho = tmpYoho;
            newMoves = [tmpMove; fromRow, fromCol, fromRow+1, fromCol];
            solder.rows = [tmpSolder.rows; fromRow+1];
            solder.cols = [tmpSolder.cols; fromCol];
            workB=tmpWorkB;
            workB(fromRow+1,fromCol)=-val;
            return
        end
    end
    if fromRow-1 > 0 && fromRow-1 < length(workB(:,1))
        if (workB(fromRow - 1,fromCol)==0)
            workB(fromRow-1,fromCol)=-val;
            [tmpMove, tmpWorkB, tmpSolder, tmpYoho] = moveTo([fromRow-1,(fromCol)],to,workB,solder,val);
            yoho = tmpYoho;
            newMoves = [tmpMove; fromRow, fromCol, fromRow-1, fromCol];
            solder.rows = [tmpSolder.rows; fromRow-1];
            solder.cols = [tmpSolder.cols; fromCol];
            workB=tmpWorkB;
            workB(fromRow-1,fromCol)=-val;
            return
        end
    end
    % last option is to move away
    if fromCol-xDir > 0 && fromCol-xDir < length(workB(1,:))
        if (workB(fromRow,(fromCol - xDir))==0)
            workB(fromRow,fromCol-xDir)=-val;
            [tmpMove, tmpWorkB, tmpSolder, tmpYoho] = moveTo([fromRow,(fromCol - xDir)],to,workB,solder,val);
            yoho = tmpYoho;
            newMoves = [tmpMove; fromRow, fromCol, fromRow, fromCol-xDir];
            solder.rows = [tmpSolder.rows; fromRow];
            solder.cols = [tmpSolder.cols; fromCol-xDir];
            workB=tmpWorkB;
            workB(fromRow,fromCol-xDir)=-val;
            return
        end
    end
else
    [distance x_or_y] = max([abs(toCol-fromCol) abs(toRow-fromRow)]);
    if x_or_y == 1
        if fromCol+xDir > 0 && fromCol+xDir < length(workB(1,:))
            if (workB(fromRow,(fromCol + xDir))==0)
                workB(fromRow,fromCol+xDir)=-val;
                [tmpMove, tmpWorkB, tmpSolder, tmpYoho] = moveTo([fromRow,(fromCol + xDir)],to,workB,solder,val);
                yoho = tmpYoho;
                newMoves = [tmpMove; fromRow, fromCol, fromRow, fromCol+xDir];
                solder.rows = [tmpSolder.rows; fromRow];
                solder.cols = [tmpSolder.cols; fromCol+xDir];
                workB=tmpWorkB;
                workB(fromRow,fromCol+xDir)=-val;
                return
            end
        end
        if fromRow+yDir > 0 && fromRow+yDir < length(workB(:,1))
            if (workB((fromRow+yDir),fromCol)==0)
                workB(fromRow+yDir,fromCol)=-val;
                [tmpMove, tmpWorkB, tmpSolder, tmpYoho] = moveTo([(fromRow+yDir),fromCol],to,workB,solder,val);
                yoho = tmpYoho;
                newMoves = [tmpMove; fromRow, fromCol, fromRow+yDir, fromCol];
                solder.rows = [tmpSolder.rows; fromRow+yDir];
                solder.cols = [tmpSolder.cols; fromCol];
                workB=tmpWorkB;
                workB(fromRow+yDir,fromCol)=-val;
                return
            end
        end
        if fromCol-xDir > 0 && fromCol-xDir < length(workB(1,:))
            if (workB(fromRow,(fromCol - xDir))==0)
                workB(fromRow,fromCol-xDir)=-val;
                [tmpMove, tmpWorkB, tmpSolder, tmpYoho] = moveTo([fromRow,(fromCol - xDir)],to,workB,solder,val);
                yoho = tmpYoho;
                newMoves = [tmpMove; fromRow, fromCol, fromRow, fromCol-xDir];
                solder.rows = [tmpSolder.rows; fromRow];
                solder.cols = [tmpSolder.cols; fromCol-xDir];
                workB=tmpWorkB;
                workB(fromRow,fromCol-xDir)=-val;
                return
            end
        end
        if fromRow-yDir > 0 && fromRow-yDir < length(workB(:,1))
            if (workB((fromRow-yDir),fromCol)==0)
                workB(fromRow-yDir,fromCol)=-val;
                [tmpMove, tmpWorkB, tmpSolder, tmpYoho] = moveTo([(fromRow-yDir),fromCol],to,workB,solder,val);
                yoho = tmpYoho;
                newMoves = [tmpMove; fromRow, fromCol, fromRow-yDir, fromCol];
                solder.rows = [tmpSolder.rows; fromRow-yDir];
                solder.cols = [tmpSolder.cols; fromCol];
                workB=tmpWorkB;
                workB(fromRow-yDir,fromCol)=-val;
                return
            end
        end
    else
        if fromRow+yDir > 0 && fromRow+yDir < length(workB(:,1))
            if (workB((fromRow+yDir),fromCol)==0)
                workB(fromRow+yDir,fromCol)=-val;
                [tmpMove, tmpWorkB, tmpSolder, tmpYoho] = moveTo([(fromRow+yDir),fromCol],to,workB,solder,val);
                yoho = tmpYoho;
                newMoves = [tmpMove; fromRow, fromCol, fromRow+yDir, fromCol];
                solder.rows = [tmpSolder.rows; fromRow+yDir];
                solder.cols = [tmpSolder.cols; fromCol];
                workB=tmpWorkB;
                workB(fromRow+yDir,fromCol)=-val;
                return
            end
        end
        if fromCol+xDir > 0 && fromCol+xDir < length(workB(1,:))
            if (workB(fromRow,(fromCol + xDir))==0)
                workB(fromRow,fromCol+xDir)=-val;
                [tmpMove, tmpWorkB, tmpSolder, tmpYoho] = moveTo([fromRow,(fromCol + xDir)],to,workB,solder,val);
                yoho = tmpYoho;
                newMoves = [tmpMove; fromRow, fromCol, fromRow, fromCol+xDir];
                solder.rows = [tmpSolder.rows; fromRow];
                solder.cols = [tmpSolder.cols; fromCol+xDir];
                workB=tmpWorkB;
                workB(fromRow,fromCol+xDir)=-val;
                return
            end
        end
        if fromRow-yDir > 0 && fromRow-yDir < length(workB(:,1))
            if (workB((fromRow-yDir),fromCol)==0)
                workB(fromRow-yDir,fromCol)=-val;
                [tmpMove, tmpWorkB, tmpSolder, tmpYoho] = moveTo([(fromRow-yDir),fromCol],to,workB,solder,val);
                yoho = tmpYoho;
                newMoves = [tmpMove; fromRow, fromCol, fromRow-yDir, fromCol];
                solder.rows = [tmpSolder.rows; fromRow-yDir];
                solder.cols = [tmpSolder.cols; fromCol];
                workB=tmpWorkB;
                workB(fromRow-yDir,fromCol)=-val;
                return
            end
        end
        if fromCol-xDir > 0 && fromCol-xDir < length(workB(1,:))
            if (workB(fromRow,(fromCol - xDir))==0)
                workB(fromRow,fromCol-xDir)=-val;
                [tmpMove, tmpWorkB, tmpSolder, tmpYoho] = moveTo([fromRow,(fromCol - xDir)],to,workB,solder,val);
                yoho = tmpYoho;
                newMoves = [tmpMove; fromRow, fromCol, fromRow, fromCol-xDir];
                solder.rows = [tmpSolder.rows; fromRow];
                solder.cols = [tmpSolder.cols; fromCol-xDir];
                workB=tmpWorkB;
                workB(fromRow,fromCol-xDir)=-val;
                return
            end
        end
    end
end
end

function new_matrix = rmrow(old_matrix, index)
if index==1
    new_matrix = old_matrix(index+1:end,:);
elseif index==length(old_matrix(:,1))
    new_matrix = old_matrix(1:index-1,:);
else
    new_matrix = [old_matrix(1:index-1,:);old_matrix(index+1:end,:)];
end
end