main

function main
clc
clf

currentMove     =  0;
maxMoves        =  22; %22 % 30 % 36
numColors       =  6;
numPixelsOnSide =  12; %12 % 17 % 22

setReproducableRandomState()

board = defineBoard(numPixelsOnSide, numColors);

displayBoard(board, numColors)

colorList = computerChoose(board, currentMove, [], maxMoves, numColors)

displayAnimation(board, numColors, colorList)

function reproSeed = setReproducableRandomState(reproSeed)
% Leave semicolon off of call with no input to see the time based seed.  
% Use seed as input to function to use prior seed.

if nargin == 0
    %set seed so if an error occurs, I can reproduce and debug
    c = clock;
    reproSeed = c(6);
end

rand('seed', reproSeed);

function board = defineBoard(numPixelsOnSide, numColors)
board = ceil(rand(numPixelsOnSide)*numColors);

function displayBoard(board, numColors, next)

if nargin == 2
    next = [];
end
    clf
    subplot(1,3,[1:2])
    image(board)
    colormap(jet(numColors))
    axis off
    colorbar
    axis equal
    
    if ~isempty(next)
        subplot(1,3,3)
        image(next)
        axis off
        title ('Next Color')
    end

function displayAnimation(board, numColors, colorList)

displayBoard(board, numColors, colorList(1))

for i = 1 : numel(colorList)  
    pause
    
    board = flood(colorList(i), board);
    if i < numel(colorList)
        
        nextColor = colorList(i + 1);
    else
        cla
        nextColor = [];
    end
    
    displayBoard(board, numColors, nextColor)
end

function board = flood(color, board)

if isempty(color) %startup condition
    return
end

connectedComponents = findConnected(board);

board(connectedComponents) = color;

function vi = findConnected(board)
%vi  is the list of indices that are 4 connected to first element of the
%matrix by the same color.

% Code created here:
%http://blogs.mathworks.com/videos/2009/06/17/puzzler-find-four-connected-c
%omponent-to-element-1-of-2-d-matrix/#comments
sizeBoardEdge = size(board,1);

oldColor = board(1,1);
    boardPath = round(zeros(sizeBoardEdge));
    updated=1;
    while updated==1
        updated=0;
        for row=1:sizeBoardEdge
            for col=1:sizeBoardEdge
                    if row==1 && col==1 && boardPath(row,col)==0  ...
                        || board(row,col)== oldColor && row>1             && boardPath(row-1,col  )~=0 && boardPath(row,col)==0 ...
                        || board(row,col)== oldColor && col>1             && boardPath(row  ,col-1)~=0 && boardPath(row,col)==0 ...
                        || board(row,col)== oldColor && col<sizeBoardEdge && boardPath(row  ,col+1)~=0 && boardPath(row,col)==0 ...
                        || board(row,col)== oldColor && row<sizeBoardEdge && boardPath(row+1,col  )~=0 && boardPath(row,col)==0;
                    
                        boardPath(row,col) = 1;
                        updated=1;
                        
                    end
            end
        end
    end

    vi = find(boardPath==1);
    
function lastColor = computerChoose(board, currentMove, choice, maxMoves, numColors)
%Returns a sequence of moves that will solve the board from the current
%state
% This function and the fringe function below were authored by
% Darren Rowland, 5 August 09
% [e-mail]
board2 = board; % local copy of the board
a      = 1:numColors;

% It is assumed that the full number of moves are allowed; 
% i.e. currentMove and choice are not used
for n = 1:maxMoves

    vi = findConnected(board2); % vi is the closed list of cells
    fopen = fringe(board2,vi);  % obtain the open list of cells

    if(isempty(fopen)) return; end;  % No open cells so board is solved

    y = histc(board2(fopen),a); % Bin the open cells by colour
    for jj = 1:numColors
        if(y(jj)>0)
            % Number of cells of this colour remaining
            ncj = nnz(board2 == jj);

            % Try each possible colour in turn
            board2(vi) = jj;

            % List of closed cells for new colour
            vj = findConnected(board2); 

            if((numel(vj)-numel(vi)) == ncj)
                % If all the cells of this colour can be finished off now,
                % then assign a large weight (but not inf).
                % This helps toward the end
                score(jj) = 1000 + ncj;
            else
                % The open list of cells with new colour applied
                f2 = fringe(board2,vj);

                y2 = histc(board2(f2),a);

                % Heuristic for each colour choice based on best projected
                % 2-step colouring
                score(jj) = numel(vj) + max(y2) + 0.1*numel(f2);
            end
        else
            score(jj) = 0;
        end
    end
    [ind,ind] = max(score); % Most viable colour
    lastColor(n) = ind;     
    board2(vi) = ind;   % Set the new colour on the board
end


function fList = fringe(board,vi)
% Create a list of cells which are 4-connected to the cells in vi
% This is the open list.
% This function requires that the board be padded with a border (of -1)
L = length(board);
Lpad = L + 2;  % Size of the padded board

% Wasteful to construct the board each time, but who's counting
Bpad = -ones(Lpad);
Bpad(2:end-1,2:end-1) = board;

% Convert the indices for the regular board to indices for the padded board
[I1,J1] = ind2sub([L,L],vi);
I1 = I1 + 1;
J1 = J1 + 1;
IND = sub2ind([Lpad,Lpad],I1,J1);

% List of all 4-connected neighbours to cells in vi (with duplicates)
aconn = [IND-1; IND-Lpad; IND+1; IND+Lpad];

% remove border cells and cells already connected to the origin ...
II = Bpad(aconn)>0 & (Bpad(aconn) ~= Bpad(2,2));

% ... then eliminate duplicates
f1 = unique(aconn(II));

% Convert the indices for the padded board back to indices for normal board
[I1,J1] = ind2sub([Lpad,Lpad],f1);
I1 = I1 - 1;
J1 = J1 - 1;
fList = sub2ind([L,L],I1,J1);