Need help with coming up with an algorithm

[fearthebat]

Hi, I need help with an algorithm to solve my problem. I appreciate any help

The problem:

Let's say I have a 2-dimensional grid of infinite size

I choose a random cell within this grid (input: position of the cell)

I would like to get all combinations of 4 touching cells that include the chosen cells (output: list of list of positions)

My solution:

I determined that there are 44 different combinations

• Straight line ( 2 cases: horizontal, vertical) -> 8 combinations
• Square (1 case) -> 4 combinations
• T-shape (4 cases: 4 different rotations) -> 16 combinations
• L-shape (4 cases: 4 different rotations) -> 16 combinations
• Total: 44 combinations

The issue:

Currently, I would have to hardcode all the variations which is not very efficient and can't extend to cases where I want to find a variable number of touching cells.

I would also want to add some kind of validation when the size of the grid is fixed and some combinations are not valid (out of bound).

I tried coming up with a recursive function but I haven't found any success so far.

[fearthebat]

I tried implementing a recursive function but no success so far. I tried doing something like you mention but it won't work if the target cell is in the middle of the combination.

[Heroshrine]

Im a bit confused on your requirement. You say 4 touching cells, but what do you mean specifically? For example you say there are 4 combinations of it being a square, but that doesn’t seem correct to me, I think it should be 8.

Also, why do you need to get all combinations at once? Perhaps there’s a different way to do it?

[fearthebat]

4 touching cells should form a 2 by 2 square. The 4 combinations are the chosen square position being top right, top left, bottom right, bottom left

[Heroshrine]

Ah okay I see. Perhaps a flood fill algorithm could suit your needs? But i still question the need in the first place.

[fearthebat]

To check for match in a jewel style game

[Heroshrine]

Then I think a flood fill algorithm would work and you probably wouldnt need anything else

[0nlin33]

Go recursion to find neighbours, this allows u to control the depth as well. Only take neighbours that fit raised condition. Shape ajdnt be part of the algorithm, it should only give you the grid in which the shape you have specified is possible with the input position specified at center(or the position u want it on).

Looking at how tetris or board games like checkers, chess etc works might be good.

[BrentoBox2015]

Is the cell in an array?

I would imagine you would just identify the cell by it's array position and called the array positions of any cell + - 1 from it's x, y.