Re: Math/Programming Algorithm Help

Dasher wrote:
Hello -

I'm having trouble with an algorithm. Basically, the user is presented with
a grid of toggle buttons (clicking on each button will change its color
from "inactive" to "active" and back). When the user is presented by a
grid of size NxN, they need to click to activate N number of squares, so
that all the activated squares are contiguous, ie, they each squares shares
an edge with at least one other square. So, for instance, when N=5, the
user would need to activate 5 contiguous squares, like so (let 1=active,
and 0=inactive):

00000 00100
00100 00100
01110 or 00100 would be valid combinations
00100 00100
00000 00100

00110
00000
00000 would not be valid
00111
00000

So, basically, I'm trying to develop an algorithm for testing whether the
users selected a valid combination, for any size N>1. I was thinking that
there might be some kind of mathematical solution, for instance, using
geometric properties, or matrices, but I haven't had any success going that
route thus far. Does anyone have any pointers on how to go about doing
this?


There are a couple of approaches. I don't think you can rely on mathematical properties...

You can use flood-fill algorithm to ensure that all elements are connected. I think that is probably the easiest and most-likely-correct solution.

You might also read a little bit about graph theory. Basically what you're trying to determine is if you have a graph that is connected.

What are your bounds on N?

--
Daniel Pitts' Tech Blog: <http://virtualinfinity.net/wordpress/>
.

Quantcast