Help checking a grid

[Medieval Bob]

I have a grid that I need to check to see if a path of like colors exists from left to right or top to bottom. The buttons will be changed from white to blue or red.

The path does not have to be straight. i.e. the following path is fine.

XXXXXX
XXXXXX
XXXXXX
XXXXXX
XXXXXX
XXXXXX

Also, please note that, since the grid is actually composed of hexagons, more paths exist than simply the linear ones like in the previous example.

For example:

If you had a path that ran almost all the way from left to right on the bottom row
grid(0,5), grid(1,5), grid(2,5), grid(3,5), grid(4,5)
then having either grid(5,5) or grid(5,4) would result in a complete path. That's because grid(4,5) touches both grid(5,5) and grid(4,4).

The "color" of each button is stored into a 2-dimensional array grid(0,0) through grid(5,5) as red=1 and blue=2.

I tried hard-coding it, but the number of paths is just way too large.

Any ideas how how to go about this check?

I'm using VB05, but I can adapt any functionality that works.

[Demosthenes]

I'm not sure I understand the problem completely, but I think you could use two recursive functions to solve this, one for top to bottom and one for left to right. Have a global variable that store true or false, initialize it to false, and if you find a like path, set it to true. For checking top to bottom, have it start the recurive function from every...hexagon in the top row, and for checking left to right have the recursive function start from every hexagon in the left-most column.

I don't know, that seems like it would work to me. You got some sample data I could try out?

[Medieval Bob]

So you're saying like

check(i,j){
if grid(i,j) = grid(i+1,j) { check(i+1,j); }
if grid(i,j) = grid(i+1, j+1) { check(i+1, j+1); }
}

Ya I think that'll work. I'll code it up later on when I get some free time. Thx for the suggestion.

[Demosthenes]

I did a hexagon problem like this earlier . . . it helped me to make the matrix 12x6 as well, but when checking fromt op to bottom sometimes you have to say:

check(r+2, c);
check(r+1, c+1);
check(r+1, c-1);

and I can't remember, but I also thing I ended up trying:

check(r-1, c-1); and check(r-1, c+1); as well . . ., making sure it didn't go backwards to the spot it just came from, but I'm not sure about those.

That got somewhat confusing at times, but it worked for me. Good luck man, those hexagon problems are a beast...lol.

[Medieval Bob]

When the function calls itself, how do you make sure it's not going back to the same place? What if you had a circle of them? That would infinite loop...

*thinks* I guess I could get an array of grid locations and use it like a stack.

Start at 0,1: Store 0,1 in 'stack'
Find next at 1,1: Store 1,1 in 'stack'
Find next at 1,2: Store 1,2 in 'stack'
Find next at 2,2: Store 2,2 in 'stack'
Find next at 2,1: Store 2,1 in 'stack'
Find next at 1,1: 1,1 already exists in 'stack' do not take.

And then when I fall out of an iteration, I can set the most recent location in the 'stack' back to -1,-1. That may be hard to code correctly...

I suppose if I sat down and worked on it, I might find out... but meh. I'll do it later.

[Demosthenes]

When the function calls itself, how do you make sure it's not going back to the same place? What if you had a circle of them? That would infinite loop...

*thinks* I guess I could get an array of grid locations and use it like a stack.

Start at 0,1: Store 0,1 in 'stack'
Find next at 1,1: Store 1,1 in 'stack'
Find next at 1,2: Store 1,2 in 'stack'
Find next at 2,2: Store 2,2 in 'stack'
Find next at 2,1: Store 2,1 in 'stack'
Find next at 1,1: 1,1 already exists in 'stack' do not take.

And then when I fall out of an iteration, I can set the most recent location in the 'stack' back to -1,-1. That may be hard to code correctly...

I suppose if I sat down and worked on it, I might find out... but meh. I'll do it later.

Yea, I ran across a problem with it bouncing between two spots. It wasn't a very elegant method to solve it, but I passed two more arguments to the function: the old r and the old c values, and made sure it didn't go back to that location. That made it work for me.

I guess you could have a parallell boolean grid and mark true false for spots you've been also . . . I haven't tried that though.

[Medieval Bob]

Ya, that would work even better I think.

That way, I'd just have to set the current (i,j) location to false when the iteration fell back a step.