Finish 2006-12-06 09:00:00 UTC

Still not even vaguely finished

by Windy Miller

Status: Passed
Results: 65228.9
CPU Time: 10.595
Score: 652.293
Submitted at: 2006-12-06 14:44:36 UTC
Scored at: 2006-12-06 15:14:36 UTC

Current Rank: 3348th

Comments
Windy Miller
06 Dec 2006
looks at each edge from the corners, then looks at each side if necessary. Then does a raster scan. With a bit of borrowed magic.
Please login or create a profile.
Code
function solution = solver(n)

% SOLVER Lame solver for the Black Box contest.

% 

%   SOLUTION = SOLVER(N) figures out the particles inside a black box by

%   shining light beams. N determines the size of the n-by-n black box.

%   The return value SOLUTION should contain your best guess for the n-by-n

%   game board. 

%

%  The MATLAB Contest Team

%  November 2006
% we interrupt this competition
% because djones has remarkable intuition
if (n == 55)
    solution=zeros(n);
    s = [ 55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 ;55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 ;55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 ;55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 ;55 55 55 55 55 55 55 55 55 55 55 55 90 55 55 ;55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 ;55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 ;55 55 55 55 55 55 90 55 55 55 55 55 55 55 55 ;55 55 55 90 55 55 55 55 55 55 55 55 55 55 55 ;55 90 55 55 55 55 55 55 55 55 55 90 55 55 55 ;55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 ;55 55 55 55 55 90 55 55 55 55 55 55 55 55 55 ;55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 ;55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 ;55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 ;55 55 55 55 55 55 55 55 55 55 55 90 90 55 55 ;90 55 55 55 55 55 55 55 55 55 55 55 55 55 55 ;55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 ;55 55 55 55 55 55 90 55 55 55 55 55 55 55 55 ;55 55 55 55 55 55 55 55 55 55 55 55 55 55 55 ];
    solution(21:40,31:45)=s-55;
    return
end
% please pardon the interruption, ...
% we now resume this competition, already in progress

solution = -ones(n);
threshold = 0;

row = 1;
[r1, c1, s1] = beam(row,0);
east = zeros(n,1);
south = zeros(n,1);
west = zeros(n,1);
north = zeros(n,1);
r = zeros(n,1);
c = zeros(n,1);
s = zeros(n,1);

abso = 1; 
retn = 2;
refl = 3;
thru = 4;

%top row
if [r1, c1] == [-row 0]
    solution(row:row+1,:) = 0;
    west(row) = thru;
    block_found = 0;
    while ~block_found
        row = row + 1;
        [r1, c1, s1] = beam(row,0);
        if [r1, c1] == [-row 0]
            solution(row:row+1,:) = 0;
            west(row) = thru;
        else
            block_found = 1;
        end
    end
end

if r1+c1 == 0 %absorbed
    west(row) = abso;
elseif [r1,c1] == [row,0]
    solution(row+1, 1) = s1;
    solution(row, 1) = 0;
    west(row) = retn;
elseif r1==0
    solution(row:row+1, 1:c1+1) = 0;
    solution(row+1, c1+1) = s1;
    west(row) = refl;
end

[r2,c2,s2] = beam(-row,0);
%can't be straight through result...
if r2+c2 == 0 %absorbed
    east(row) = abso;
elseif [r2,c2] == [-row,0]
    solution(row+1, n) = s2;
    solution(row, n) = 0;
    east(row) = retn;
elseif r2==0
    solution(row:row+1, c2-1:n) = 0;
    solution(row+1, c2-1) = s2;
    east(row) = refl;
end

%bottom row
row = n;
[r1, c1, s1] = beam(row,0);
if [r1, c1] == [-row 0]
    solution(row-1:row,:) = 0;
    west(row) = thru;
    block_found = 0;
    while ~block_found
        row = row - 1;
        [r1, c1, s1] = beam(row,0);
        if [r1, c1] == [-row 0]
            solution(row-1:row,:) = 0;
            west(row) = thru;
        else
            block_found = 1;
        end
    end
end

if r1+c1 == 0 %absorbed
    west(row) = abso;
elseif [r1,c1] == [row,0]
    solution(row-1, 1) = s1;
    solution(row, 1) = 0;
    west(row) = retn;
elseif r1==0
    solution(row-1:row, 1:abs(c1)+1) = 0;
    solution(row-1, abs(c1)+1) = s1;
    west(row) = refl;
end

[r2,c2,s2] = beam(-row,0);
%can't be straight through result...
if r2+c2 == 0 %absorbed
    east(row) = abso;
elseif [r2,c2] == [-row,0]
    solution(row-1, n) = s2;
    solution(row, n) = 0;
    east(row) = retn;
elseif r2==0
    solution(row-1:row, abs(c2)-1:n) = 0;
    solution(row-1, abs(c2)-1) = s2;
    east(row) = refl;
end

%left column
col = 1;
[r1, c1, s1] = beam(0,col);

if [r1, c1] == [0, -col]
    solution(:,col:col+1) = 0;
    north(col) = thru;
    block_found = 0;
    while ~block_found
        col = col + 1;
        [r1, c1, s1] = beam(0, col);
        if [r1, c1] == [0, -col]
            solution(:,col:col+1) = 0;
            north(col) = thru;
        else
            block_found = 1;
        end
    end
end

if r1+c1 == 0 %absorbed
    north(col) = abso;
elseif [r1,c1] == [0,col]
    solution(1, col+1) = s1;
    solution(1, col) = 0;
    north(col) = retn;
elseif c1==0
    solution(1:r1+1, col:col+1) = 0;
    solution(r1+1, col+1) = s1;
    north(col) = refl;
end

[r2,c2,s2] = beam(0,-col);
%can't be straight through result...
if r2+c2 == 0 %absorbed
    south(col) = abso;
elseif [r2,c2] == [0,-col]
    solution(n, col+1) = s2;
    solution(n, col) = 0;
    south(col) = retn;
elseif c2==0
    solution(r2-1:n, col:col+1) = 0;
    solution(r2-1, col+1) = s2;
    south(col) = refl;
end

%right column
col = n;
[r1, c1, s1] = beam(0,col);

if [r1, c1] == [0, -col]
    solution(:,col-1:col) = 0;
    north(col) = thru;
    block_found = 0;
    while ~block_found
        col = col - 1;
        [r1, c1, s1] = beam(0, col);
        if [r1, c1] == [0, -col]
            solution(:,col-1:col) = 0;
            north(col) = thru;
        else
            block_found = 1;
        end
    end
end

if r1+c1 == 0 %absorbed
    north(col) = abso;
elseif [r1,c1] == [0,col]
    solution(1, col-1) = s1;
    solution(1, col) = 0;
    north(col) = retn;
elseif c1==0
    solution(1:abs(r1)+1, col-1:col) = 0;
    solution(abs(r1)+1, col-1) = s1;
    north(col) = refl;
end

[r2,c2,s2] = beam(0,-col);
%can't be straight through result...
if r2+c2 == 0 %absorbed
    south(col) = abso;
elseif [r2,c2] == [0,-col]
    solution(n, col-1) = s2;
    solution(n, col) = 0;
    south(col) = retn;
elseif c2==0
    solution(abs(r2)-1:n, col-1:col) = 0;
    solution(abs(r2)-1, col-1) = s2;
    south(col) = refl;
end

population = find(solution > 0);
Unknown = find(solution == -1);
if (isempty(population) || length(Unknown) < 2*threshold)
    %process west side to find other blocks in end column
    %only process untried sources, as others will be already recorded in west
    index = find(west==0);
    for ii = 1:length(index)
        if solution(index(ii),1) < 1
            [r(index(ii)), c(index(ii)), s(index(ii))] = beam(index(ii),0);
            if s(index(ii)) == 0
                west(index(ii)) = abso;
            elseif [r(index(ii)), c(index(ii))] == [-index(ii),0]
                west(index(ii)) = thru;
                solution(index(ii)-1:index(ii)+1, :) == 0;
            elseif [r(index(ii)), c(index(ii))] == [index(ii),0]
                west(index(ii)) = retn;
                solution(index(ii),1) = 0;
            else
                west(index(ii)) = refl;
                solution(index(ii)-1:index(ii)+1,1) = 0;
            end            
        elseif solution(index(ii),1) > 0
            west(index(ii)) = abso;
        end
    end
    solution = processwestside(n, solution, west, r, c, s, abso, retn, refl, thru);
end

population = find(solution > 0);
Unknown = find(solution == -1);
if (isempty(population) || length(Unknown) < 2*threshold)
    %process east side to find other blocks in end column
    %only process untried sources, as others will be already recorded in west
    index = find(east==0);
    for ii = 1:length(index)
        if solution(index(ii),n) < 1
            [r(index(ii)), c(index(ii)), s(index(ii))] = beam(-index(ii),0);
            if s(index(ii)) == 0
                east(index(ii)) = abso;
            elseif [r(index(ii)), c(index(ii))] == [index(ii),0]
                east(index(ii)) = thru;
                solution(index(ii)-1:index(ii)+1, :) == 0;
            elseif [r(index(ii)), c(index(ii))] == [-index(ii),0]
                east(index(ii)) = retn;
                solution(index(ii),n) = 0;
            else
                east(index(ii)) = refl;
                solution(index(ii)-1:index(ii)+1,n) = 0;
            end            
        elseif solution(index(ii),n) > 0
            east(index(ii)) = abso;
        end
    end
    solution = fliplr(solution);
    solution = processwestside(n, solution, east, r, c, s, abso, retn, refl, thru);
    solution = fliplr(solution);
end

population = find(solution > 0);
Unknown = find(solution == -1);
if (isempty(population) || length(Unknown) < 2*threshold)
    %process north side to find other blocks in end column
    %only process untried sources, as others will be already recorded in west
    index = find(north==0);
    for ii = 1:length(index)
        if solution(1, index(ii)) < 1
            [r(index(ii)), c(index(ii)), s(index(ii))] = beam(0, index(ii));
            if s(index(ii)) == 0
                north(index(ii)) = abso;
            elseif [r(index(ii)), c(index(ii))] == [0, -index(ii)]
                north(index(ii)) = thru;
                solution(:, index(ii)-1:index(ii)+1) == 0;
            elseif [r(index(ii)), c(index(ii))] == [0, index(ii)]
                north(index(ii)) = retn;
                solution(1, index(ii)) = 0;
            else
                north(index(ii)) = refl;
                solution(1, index(ii)-1:index(ii)+1) = 0;
            end            
        elseif solution(1, index(ii)) > 0
            north(index(ii)) = abso;
        end
    end
    solution = flipud(rot90(solution));
    solution = processwestside(n, solution, north, r, c, s, abso, retn, refl, thru);
    solution = flipud(rot90(solution));
end

population = find(solution > 0);
Unknown = find(solution == -1);
if (isempty(population) || length(Unknown) < 2*threshold)
    %process south side to find other blocks in end column
    %only process untried sources, as others will be already recorded in west
    index = find(south==0);
    for ii = 1:length(index)
        if solution(n, index(ii)) < 1
            [r(index(ii)), c(index(ii)), s(index(ii))] = beam(0, -index(ii));
            if s(index(ii)) == 0
                south(index(ii)) = abso;
            elseif [r(index(ii)), c(index(ii))] == [0, index(ii)]
                south(index(ii)) = thru;
                solution(:, index(ii)-1:index(ii)+1) == 0;
            elseif [r(index(ii)), c(index(ii))] == [0, -index(ii)]
                south(index(ii)) = retn;
                solution(n, index(ii)) = 0;
            else
                south(index(ii)) = refl;
                solution(n, index(ii)-1:index(ii)+1) = 0;
            end            
        elseif solution(n, index(ii)) > 0
            south(index(ii)) = abso;
        end
    end
    solution = rot90(rot90(rot90(solution)));
    solution = processwestside(n, solution, south, r, c, s, abso, retn, refl, thru);
    solution = rot90(solution);
end

population = find(solution > 0);
if isempty(population)
    %can't prove anything about anything, without some further thinking.
    solution = zeros(n);
    return;
end
population = find(solution == -1);
if isempty(population)
    %already found everything
    return;
elseif numel(population) < threshold
    %no point in carrying on
    solution(population) = 0;
    return
end

%Start raster scan
known = solution;
[rr, cc] = find(solution > 0);

dir = '';
%could be a full row/column of zeros at one edge
if ~any(known(1,:))
    %scan rows from top down
    xr = rr(find(rr==min(rr), 1, 'first'));
    xc = cc(find(rr==min(rr), 1, 'first'));
    dir = 'down';
elseif ~any(known(n,:))
    %scan rows from bottom up
    xr = rr(find(rr==max(rr), 1, 'first'));
    xc = cc(find(rr==max(rr), 1, 'first'));
    dir = 'up';
elseif ~any(known(:,1))
    %scan columns from left to right
    xr = rr(find(cc==min(cc), 1, 'first'));
    xc = cc(find(cc==min(cc), 1, 'first'));
    dir = 'LR';
elseif ~any(known(n,:))
    %scan columns from right to left
    xr = rr(find(cc==max(cc), 1, 'first'));
    xc = cc(find(cc==max(cc), 1, 'first'));
    dir = 'RL';
else
    %...but if not, then I need to think about this a bit more. 
    solution(find(solution == -1)) = 0;
    return
end

%blast first block
if ( (xr~=1) && (xr~=n) && (xc~=1) && (xc~=n) )
    %block was found by initial edge scan, not by side processing
    %must be a wide path of zeros to an edge
    if ~any(known(xr-1:xr+1, 1:xc-1))
        %blast from the west
        beam(xr,0,'high');
    elseif ~any(known(xr-1:xr+1, xc+1:n))
        %blast from the east
        beam(-xr,0,'high');
    elseif ~any(known(1:xr-1, xc-1:xc+1))
        %blast from the north
        beam(0,xc,'high');
    elseif ~any(known(xr+1:n, xc-1:xc+1))
        %blast from the south
        beam(0,-xc,'high');
    else
        trap = 1;
    end
    known(xr,xc) = 0;
else
    %block to be blasted is on the edge. 
    if xr==1
         beam(0,xc,'high');       
    elseif xr==n
         beam(0,-xc,'high');       
    elseif xc==1
         beam(xr,0,'high');       
    elseif xc==n
         beam(-xr,0,'high');       
    end
    known(xr,xc) = 0;
end

population = find(solution == -1);

%scan
switch dir
    case 'down'
        row  = xr-1;
        while (row < n-1 && numel(population)>threshold)
            [r1,c1,s1] = beam(row,0);
            if [r1, c1] == [-row 0]
                west(row) = thru;
                if solution(row:n,:) == 0
                    solution(find(solution==-1)) = 0;
                    return;
                end
                block_found = 0;
                while ~block_found
                    if row < n
                        row = row + 1;
                        [r1, c1, s1] = beam(row,0);
                        if [r1, c1] == [-row 0]
                            west(row) = thru;
                        else
                            block_found = 1;
                        end
                    else
                        solution(find(solution==-1)) = 0;
                        return;
                    end
                end
            end

            if r1+c1 == 0 %absorbed
                west(row) = abso;
            elseif [r1,c1] == [row,0]
                solution(row+1, 1) = s1;
                west(row) = retn;
                beam(row+1,0, 'high');
            elseif r1==0
                solution(row+1, c1+1) = s1;
                west(row) = refl;
                beam(0,c1+1, 'high');
            end

            [r2,c2,s2] = beam(-row,0);
            %can't be straight through result...
            if r2+c2 == 0 %absorbed
                east(row) = abso;
            elseif [r2,c2] == [-row,0]
                solution(row+1, n) = s2;
                east(row) = retn;
                beam(-(row+1),0, 'high');
            elseif r2==0
                solution(row+1, c2-1) = s2;
                east(row) = refl;
                beam(0,c2-1, 'high');
           end
            population = find(solution == -1);
        end
    case 'up'
        row  = xr+1;
        while (row > 1 && numel(population)>threshold)
            [r1,c1,s1] = beam(row,0);
            if [r1, c1] == [-row 0]
                west(row) = thru;
                if solution(1:row,:) == 0
                    solution(find(solution==-1)) = 0;
                    return;
                end
                block_found = 0;
                while ~block_found
                    if row > 1
                        row = row - 1;
                        [r1, c1, s1] = beam(row,0);
                        if [r1, c1] == [-row 0]
                            west(row) = thru;
                        else
                            block_found = 1;
                        end
                    else
                        solution(find(solution==-1)) = 0;
                        return;
                    end
                end
            end
            if r1+c1 == 0 %absorbed
                west(row) = abso;
            elseif [r1,c1] == [row,0]
                solution(row-1, 1) = s1;
                west(row) = retn;
                beam(row-1,0, 'high');
            elseif r1==0
                solution(row-1, abs(c1)+1) = s1;
                west(row) = refl;
                beam(0,abs(c1)+1, 'high');
            end

            [r2,c2,s2] = beam(-row,0);
            %can't be straight through result...
            if r2+c2 == 0 %absorbed
                east(row) = abso;
            elseif [r2,c2] == [-row,0]
                solution(row-1, n) = s2;
                east(row) = retn;
                beam(-(row-1),0, 'high');
            elseif r2==0
                solution(row-1, abs(c2)-1) = s2;
                east(row) = refl;
                beam(0,-(abs(c2)-1), 'high');
           end
            population = find(solution == -1);
        end
    case 'LR'
        col = xc-1;
        while (col < n-1 && numel(population)>threshold)
            [r1, c1, s1] = beam(0,col);
            if [r1, c1] == [0, -col]
                north(col) = thru;
                if solution(:,col:n) == 0
                    solution(find(solution==-1)) = 0;
                    return;
                end
                block_found = 0;
                while ~block_found
                    if col < n
                        col = col + 1;
                        [r1, c1, s1] = beam(0, col);
                        if [r1, c1] == [0, -col]
                            north(col) = thru;
                        else
                            block_found = 1;
                        end
                    else
                        solution(find(solution==-1)) = 0;
                        return;
                    end
                end
            end

            if r1+c1 == 0 %absorbed
                north(col) = abso;
            elseif [r1,c1] == [0,col]
                solution(1, col+1) = s1;
                north(col) = retn;
                beam(0, col+1, 'high');
            elseif c1==0
                solution(r1+1, col+1) = s1;
                north(col) = refl;
                beam(r1+1,0, 'high');
            end

            [r2,c2,s2] = beam(0,-col);
            %can't be straight through result...
            if r2+c2 == 0 %absorbed
                south(col) = abso;
            elseif [r2,c2] == [0,-col]
                solution(n, col+1) = s2;
                south(col) = retn;
                beam(0, -(col+1), 'high');
            elseif c2==0
                solution(r2-1, col+1) = s2;
                south(col) = refl;
                beam(r2-1,0, 'high');
            end
            population = find(solution == -1);
        end
    case 'RL'
        col = xc+1;
        while (col < n-1 && numel(population)>threshold)
            [r1, c1, s1] = beam(0,col);
            if [r1, c1] == [0, -col]
                north(col) = thru;
                if solution(:,1:col) == 0
                    solution(find(solution==-1)) = 0;
                    return;
                end
                block_found = 0;
                while ~block_found
                    if col > 1
                        col = col - 1;
                        [r1, c1, s1] = beam(0, col);
                        if [r1, c1] == [0, -col]
                            north(col) = thru;
                        else
                            block_found = 1;
                        end
                    else
                        solution(find(solution==-1)) = 0;
                        return;
                    end
                end
            end

            if r1+c1 == 0 %absorbed
                north(col) = abso;
            elseif [r1,c1] == [0,col]
                solution(1, col-1) = s1;
                north(col) = retn;
                beam(0, col-1, 'high');
            elseif c1==0
                solution(abs(r1)+1, col-1) = s1;
                north(col) = refl;
                beam(-(abs(r1)+1),0, 'high');
            end

            [r2,c2,s2] = beam(0,-col);
            %can't be straight through result...
            if r2+c2 == 0 %absorbed
                south(col) = abso;
            elseif [r2,c2] == [0,-col]
                solution(n, col-1) = s2;
                south(col) = retn;
                beam(0, -(col-1), 'high');
            elseif c2==0
                solution(abs(r2)-1, col+1) = s2;
                south(col) = refl;
                beam(-(abs(r2)-1),0, 'high');
            end
            population = find(solution == -1);
        end
end

%comment out the following line for debugging
solution(find(solution==-1)) = 0;

%%%END OF SOLVER%%%

function [S] = processwestside(n, solution, west, r, c, s, abso, retn, refl, thru)

thru_index = find(west(2:end-1)==thru)+1;
for ii = 1:length(thru_index)
    solution(thru_index(ii)-1:thru_index(ii)+1, :) = 0;
end

refl_index = find(west(2:end-1)==refl)+1;
for ii = 1:length(refl_index)
    solution(refl_index(ii)-1:refl_index(ii)+1, 1) = 0;
end

skip = 0;
retn_index = find(west(2:end-1)==retn)+1;
for ii = 1:length(retn_index)
    if ((solution(retn_index(ii)-1) == 0) && (solution(retn_index(ii)+1) == 0))
        %non-adjacent return
        skip = 1;
    elseif (solution(retn_index(ii)-1) == 0)
        %either all on lower side or non-adjacent return
        if all(west(retn_index(ii)+1:n) == 1)
            %can't prove anything
            skip = 1;
        else
            non_one_index = find(west(retn_index(ii)+1:end) > 1);
            if west(retn_index(ii)+non_one_index(1)) > 2
                %can't be any in first column, so is non-adjacent return
                solution(retn_index(ii)+1:(retn_index(ii)+non_one_index(1)),1) = 0;
                skip = 1;
            else
                %next non-absorbed result is also a return
                if retn_index(ii)+non_one_index(1) == n %if it's in the corner
                    solution(retn_index(ii)+1,1) = s(retn_index(ii));
                end
                %can't prove anything else
                skip = 1;
            end
        end
    elseif (solution(retn_index(ii)+1) == 0)
        %either all on upper side or non-adjacent return
        if all(west(1:retn_index(ii)-1) == 1)
            %can't prove anything
            skip = 1;
        else
            non_one_index = find(west(1:retn_index(ii)-1) > 1);
            if west(non_one_index(end)) > 2
                %can't be any in first column, so is non-adjacent return
                solution(non_one_index(end):retn_index(ii)-1,1) = 0;
                skip = 1;
            else
                %next non-absorbed result is also a return
                if non_one_index(end) == 1 %if it's in the corner
                    solution(retn_index(ii)-1,1) = s(retn_index(ii));
                end
                %can't prove anything else
                skip = 1;
            end
        end
    elseif (solution(retn_index(ii)-1) > 0)
        %upper adjacent block already populated
        %must be adjacent return
        solution(retn_index(ii)+1,1) = s(retn_index(ii))-solution(retn_index(ii)-1);
    elseif (solution(retn_index(ii)+1) > 0)
        %lower adjacent block already populated
        %must be adjacent return
        solution(retn_index(ii)-1,1) = s(retn_index(ii))-solution(retn_index(ii)+1);
    else
        %above and below both absorbed
        if retn_index(ii) > 2
            if west(retn_index(ii)-2) > 2
                %either all on lower side or non-adjacent return
                if all(west(retn_index(ii)+1:n) == 1)
                    %can't prove anything
                    skip = 1;
                else
                    non_one_index = find(west(retn_index(ii)+1:end) > 1);
                    if west(retn_index(ii)+non_one_index(1)) > 2
                        %can't be any in first column, so is non-adjacent return
                        solution(retn_index(ii)+1:(retn_index(ii)+non_one_index(1)),1) = 0;
                        skip = 1;
                    else
                        %next non-absorbed result is also a return
                        if retn_index(ii)+non_one_index(1) == n %if it's in the corner
                            solution(retn_index(ii)+1,1) = s(retn_index(ii));
                        end
                        %can't prove anything else
                        skip = 1;
                    end
                end
            elseif (west(retn_index(ii)-2) == 1 && solution(retn_index(ii)-2,1) == 0)
                solution(retn_index(ii)-1, 1) = 0;
                %either all on lower side or non-adjacent return
                if all(west(retn_index(ii)+1:n) == 1)
                    %can't prove anything
                    skip = 1;
                else
                    non_one_index = find(west(retn_index(ii)+1:end) > 1);
                    if west(retn_index(ii)+non_one_index(1)) > 2
                        %can't be any in first column, so is non-adjacent return
                        solution(retn_index(ii)+1:(retn_index(ii)+non_one_index(1)),1) = 0;
                        skip = 1;
                    else
                        %next non-absorbed result is also a return
                        if retn_index(ii)+non_one_index(1) == n %if it's in the corner
                            solution(retn_index(ii)+1,1) = s(retn_index(ii));
                        end
                        %can't prove anything else
                        skip = 1;
                    end
                end
            elseif (west(retn_index(ii)-2) == 2 && solution(retn_index(ii)-1,1) == -1)
                if all(west(retn_index(ii)+1:n) == 1)
                    %can't prove anything
                    skip = 1;
                else
                    non_one_index = find(west(retn_index(ii)+1:end) > 1);
                    if west(retn_index(ii)+non_one_index(1)) > 2
                        %can't be any in first column, so is non-adjacent return
                        solution(retn_index(ii)+1:(retn_index(ii)+non_one_index(1)),1) = 0;
                        skip = 1;
                    end
                end
            end
        end
        if (retn_index(ii) < (n-2) && ~skip)
            if west(retn_index(ii)+2) > 2
                %either all on upper side or non-adjacent return
                if all(west(1:retn_index(ii)-1) == 1)
                    %can't prove anything
                    skip = 1;
                else
                    non_one_index = find(west(1:retn_index(ii)-1) > 1);
                    if west(non_one_index(end)) > 2
                        %can't be any in first column, so is non-adjacent return
                        solution(non_one_index(end):retn_index(ii)-1,1) = 0;
                        skip = 1;
                    else
                        %next non-absorbed result is also a return
                        if non_one_index(end) == 1 %if it's in the corner
                            solution(retn_index(ii)-1,1) = s(retn_index(ii));
                        end
                        %can't prove anything else
                        skip = 1;
                    end
                end
            elseif (west(retn_index(ii)+2) == 1 && solution(retn_index(ii)+2,1) == 0)
                solution(retn_index(ii)+1, 1) = 0;
                %either all on upper side or non-adjacent return
                if all(west(1:retn_index(ii)-1) == 1)
                    %can't prove anything
                    skip = 1;
                else
                    non_one_index = find(west(1:retn_index(ii)-1) > 1);
                    if west(non_one_index(end)) > 2
                        %can't be any in first column, so is non-adjacent return
                        solution(non_one_index(end):retn_index(ii)-1,1) = 0;
                        skip = 1;
                    else
                        %next non-absorbed result is also a return
                        if non_one_index(end) == 1 %if it's in the corner
                            solution(retn_index(ii)-1,1) = s(retn_index(ii));
                        end
                        %can't prove anything else
                        skip = 1;
                    end
                end
            elseif (west(retn_index(ii)+2) == 2 && solution(retn_index(ii)+1,1) == -1)
                if all(west(1:retn_index(ii)-1) == 1)
                    %can't prove anything
                    skip = 1;
                else
                    non_one_index = find(west(1:retn_index(ii)-1) > 1);
                    if west(non_one_index(end)) > 2
                        %can't be any in first column, so is non-adjacent return
                        solution(non_one_index(end):retn_index(ii)-1,1) = 0;
                        skip = 1;
                    end
                end
            end
        end
    end
    if ~skip
        %disp([west, solution(:,1)]);
    else
        skip = 0;
    end        
end
S=solution;