Puzzler: Find four-connected component to element 1 of 2-d matrix

Posted by Doug Hull, June 17, 2009

2 views (last 30 days) | 0 Likes | 37 comments

This week, I was going to make a great video on recursion to solve a fun little puzzle. However, my code runs too slow. Before my recursive solution to the larger puzzle is practical, I need to clean out this bottleneck in the solver.

I have found the bottleneck to be here (taken out of context for clarity):

sizeBoardEdge = 6;
numColors      = 6;
tic
for i = 1:15000
    %optimize contents of loop
    %currently this take 3 seconds, would like to do significantly better
    board = round(rand(sizeBoardEdge)*numColors);
    oldColor = board(1,1);
    %
    connectedComponents = bwconncomp((board == oldColor),4);
    vi = connectedComponents.PixelIdxList{1};
end
toc

Notice that I only want the indices of the pixels that are in the ‘four connected pool’ of pixels of the same value as the pixel in the upper left corner.

The benchmark to beat is 15000 calls in 3 seconds.

Here is a graphical example of what this should do.

My code uses the Image Processing Toolbox. I am hoping a dedicated function could be optimized to run faster than BWCONNCOMP since I am only using a small amount of the information that this function calculates.

The best solution to this by next week will get a MATLAB t-shirt, if it can cut the time on my machine by at least one half.