% submissions/solver_I.m
% James White
function [moves, vine] = solver(board, limit)
SCORE = -Inf * ones(1,25);
VINE = cell(1,25);
MOVES = cell(1,25);
%[MOVES{1}, VINE{1}, SCORE(1)] = initial_solver(board, limit);
%A =[];
A = graph_from_board(board);
%roughhist = hist(board(:), min(board(:):max(board(:))));
%if sum(roughhist>0) < 50,
%
% [regionboard, regioncounts, regionA] = regionfinder3(board);
%else
regionboard = [];
regioncounts= [];
regionA = [];
%end
% [MOVES{2}, VINE{2}, SCORE(2)] = dfs(board,A,7);
% %check(MOVES{2},VINE{2},board,limit, SCORE(2));
%
%[MOVES{3}, VINE{3}, SCORE(3)] = greedy(board,A,1);
% % check(MOVES{3},VINE{3},board,limit, SCORE(3));
%[MOVES{4}, VINE{4}, SCORE(4)] = greedy(board,A, -1);
% % check(MOVES{4},VINE{4},board,limit, SCORE(4));
N=5;
%[MOVES{N}, VINE{N}, SCORE(N)] = warnsdorff3(board,A);
%check(MOVES{N},VINE{N},board,limit, SCORE(N));
N=6;
%[MOVES{N}, VINE{N}, SCORE(N)] = reverse_warnsdorff3(board,A);
%check(MOVES{N},VINE{N},board,limit, SCORE(N));
% why are these guys with A' doing better?
N=15;
%[MOVES{N}, VINE{N}, SCORE(N)] = reverse_warnsdorff3(board,A');
%check(MOVES{N},VINE{N},board,limit, SCORE(N));
N=16;
%[MOVES{N}, VINE{N}, SCORE(N)] = warnsdorff3(board,A');
%check(MOVES{N},VINE{N},board,limit, SCORE(N));
nrows = size(board,1);
nsew = [ 1 -1 nrows -nrows ];
%ewns = [ nrows -nrows 1 -1 ];
ewns = [ -nrows -1 nrows 1 ];
%
N=6;
[MOVES{N}, VINE{N}, SCORE(N)] = winder(board,A, 1, nsew,regionboard, regioncounts, regionA);
% check(MOVES{N},VINE{N},board,limit, SCORE(N));
N=7;
%[MOVES{N}, VINE{N}, SCORE(N)] = winder(board,A', -1, nsew,regionboard, regioncounts, regionA);
%check(MOVES{N},VINE{N},board,limit, SCORE(N));
N=8;
%[MOVES{N}, VINE{N}, SCORE(N)] = greedorf2(board,A, 1, nsew,regionboard, regioncounts, regionA);
%check(MOVES{N},VINE{N},board,limit, SCORE(N));
N=9;
%[MOVES{N}, VINE{N}, SCORE(N)] = greedorf2(board,A', -1, nsew,regionboard, regioncounts, regionA);
%check(MOVES{N},VINE{N},board,limit, SCORE(N));
N=10;
%[MOVES{N}, VINE{N}, SCORE(N)] = greedorf2(board,A, 1, ewns,regionboard, regioncounts, regionA);
%check(MOVES{N},VINE{N},board,limit, SCORE(N));
N=11;
%[MOVES{N}, VINE{N}, SCORE(N)] = greedorf2(board,A', -1, ewns,regionboard, regioncounts, regionA);
%check(MOVES{N},VINE{N},board,limit, SCORE(N));
N=12;
%[MOVES{N}, VINE{N}, SCORE(N)] = greedorf3(board,A', -1, ewns,[], [], []);
N=20;
%[MOVES{N}, VINE{N}, SCORE(N)] = greedorf(board,A, 1);
N=21;
%[MOVES{N}, VINE{N}, SCORE(N)] = greedorf(board,A', -1);
[result, vine_idx] = max(SCORE);
% fprintf('%i',vine_idx);
vine = VINE{vine_idx};
moves = MOVES{vine_idx};
%out = double(board);
end
function A = graph_from_board(board)
A = sparse(numel(board),numel(board));
nrows = size(board,1);
for i = 1:numel(board)
if i+1 <= numel(board) && mod(i,nrows) % smaller index must not be at end of a column
A(i,i+1 ) = board(i) <= board(i+1);
end
if i > 1 && mod(i-1,nrows) % smaller index must not be at end of a column
A(i,i-1 ) = board(i) <= board(i-1);
end
if i + nrows <= numel(board)
A(i,i+nrows) = board(i) <= board(i+nrows);
end
if i > nrows
A(i,i-nrows) = board(i) <= board(i-nrows);
end
end
end
% function flag = isconnected(a,b,m)
% % a,b: Absolute indices
% % m,n: Size of board
% % flag: True if indices a and b are four connected
% d = abs(a(:)-b(:));
% flag = (d == m) | (d == 1 & mod(min(a(:),b(:)), m));
% end
function [moves, bestvine, bestscore] = winder(board,A, UPDOWN, nsew, regionboard, regioncounts, regionA)
% UPDOWN = 1 to walk uphill, -1 to walk downhill
% try to stay in current region and try to wind
%board 64 issue
board = UPDOWN*board;
VISITED = -Inf;
moves = [];
vine = zeros(numel(board),1);
bestscore = -Inf;
%startnodes = 1:numel(board); % all
minboard = min(board(:));
%if board(1,:) == min
startnodes = find(board(:) == minboard)'; % maybe not the best strategy
edgecount = sum(A,2); % outdegree
%[ec, idx] = sort(edgecount(startnodes));
%[ignore,idx] = min(edgecount(startnodes));
%startnodes = startnodes(idx);
if false%regionboard
numregions = numel(regioncounts);
indeg = full(sum(regionA,1));
for k = find(indeg == 0)'
startnodes = [startnodes; find(regionboard(:) == k)];
end
startnodes = startnodes';
else
[minboard, startnodes] = min(board(:)); % maybe not the best strategy
startnodes = find(board(:) == minboard)';
%startnodes = find(board(:) == min(board(board(:) > minboard)))';
startnodes = startnodes(1);
end
% div = 5;
% if numel(startnodes) > div,
% startnodes = startnodes(1:ceil(numel(startnodes)/div):end);
% end
nrows = size(board,1);
original_board = board;
for i = startnodes
board = original_board;
edgecount = sum(A,2); % outdegree
backtracks = 0;
vine(1) = i;
score = board(vine(1));
curval = board(vine(1));
neighbors = find(A(:, vine(1))); % nodes pointing to vine
edgecount(neighbors) = edgecount(neighbors)-1;
board(vine(1)) = VISITED; % mark as visited
k = 1;
%next = 0;
%hi = Inf;
while(1)
%fprintf('round %i\n',k);
%fprintf(' vine(%i) = %i\n',k, vine(k));
edge_count_lo = Inf;
hi = Inf;
next = 0;
%alldeadend = true;
bob = find(A(vine(k),:));
%for adj = vine(k) + nsew%(randperm(4))
for adj = bob
%if adj > 0 && adj <= numel(board) && ( abs(adj - vine(k))==nrows | mod(min(vine(k),adj),nrows) ) && curval == board(adj)
%assert( any( bob == adj ) );
%assert(adj > 0 && adj <= numel(board) && ( abs(adj - vine(k))==nrows | mod(min(vine(k),adj),nrows) ));
if curval == board(adj)
%[r,c]=ind2sub(size(board), adj);
%fprintf(' adj %i (%3i,%3i) is %i \n',adj, r,c, board(adj));
%assert(edgecount(adj)<4);
%edgecount(adj) = region_edges_left(adj, board, original_board);
%if alldeadend && edgecount(adj) > 0 % can avoid deadend
% alldeadend = false;
% hi = board(adj);
% next = adj;
% edge_count_lo = edgecount(adj); %edges_left(adj, board);
% continue;
%end
%if true %edgecount(adj) > 0 || alldeadend
if board(adj) < hi
hi = board(adj);
next = adj;
edge_count_lo = edgecount(adj); %edges_left(adj, board);
else if board(adj) == hi && edgecount(adj)
if edgecount(adj) < edge_count_lo
%hi = board(adj);
next = adj;
edge_count_lo = edgecount(adj);
end
end
end
%end
end
end
if ~next
tempscore = UPDOWN*score;
if tempscore > bestscore
bestscore = tempscore;
bestvine = vine;
bestlength = k;
end
%backtrack
score = score - original_board(vine(k));
k = k-1; % board(vine(k)) is still marked as visited so we will not visit it again
if k
%backtracks = backtracks + 1;
continue
end
break
end
curval = board(next); % hi;
k = k+1;
score = score + board(next); %hi;
vine(k) = next;
occupied(next) = true;
neighbors = find(A(:, vine(k))); % nodes pointing to vine
edgecount(neighbors) = edgecount(neighbors)-1;
board(vine(k)) = VISITED; % mark as visited
end
score = UPDOWN*score;
if score > bestscore
bestscore = score;
bestvine = vine;
bestlength = k;
end
end
if UPDOWN == 1
bestvine = bestvine(1:bestlength);
else
bestvine = bestvine(bestlength:-1:1);
end
%score
end
% note that all visited nodes have the same board value
% pass in original_board to keep "visited" nodes from forming a "region"
function n = region_edges_left(node, board,original_board)
n = 0;
nrows = size(board,1);
nsew = [ 1 -1 nrows -nrows];
% counting issues if nrows = 1
for adj = node + nsew
if adj > 0 && adj <= numel(board) && ( abs(adj - node)==nrows | mod(min(node,adj),nrows) ) && original_board(node) == board(adj)
n = n+1;
end
end
if nrows == 1 % counting issues if nrows = 1
n = n/2;
end
end
function tf = has_neighbor_in_region(node, board, regionval)
nrows = size(board,1);
nsew = [ 1 -1 nrows -nrows];
% counting issues if nrows = 1
for adj = node + nsew
if adj > 0 && adj <= numel(board) && ( abs(adj - node)==nrows | mod(min(node,adj),nrows) ) && board(adj) == regionval
tf = true;
return
end
end
tf = false;
end
|
