2007 VBA: Cannot figure out recursion to show all possible paths in a 4 x 4 grid.

[Spielberg]

Hello all gurus... Before I begin (Although teh subject pretty much sums it up,) I tried my best to search for a "dummies" version of trying to figure this out. I searched through the forum and all over.

I'm terrible in algorithms, and usually program stuff "the hard way" because I can't figure out the "right" way to do it.

I do NOT want anyone to write anything for me, I really do want to learn myself. Tips, tricks, or even a step-by-step tutorial would be AWESOME if someone knows of one.

Basically, I have a 4 x 4 grid and would like to find all possible paths of various lengths of characters form 3 up to 16. It almost sounds exactly like a Boggle Solver, and I guess in some ways it is, but it's not for that, although the paths would be exactly the same.

The hard way, again, the way I am used to doing things, was started by me created a tons of grids and manually plotting the paths of 3 characters, coming up with 416 possibilities.

That took a while. Then I started to do 4 characters paths and realized I would probably expire before i finished. There's NO way I would make it to 16 characters.

That's when I knew I would have to find a way to do it. I did learn that recursion was the way it [should] be done. (Correct me if I am wrong...)

So, if anyone knows of any kind of tutorial, or at least can get me started in the right direction with something literally for VBA (Excel '07) that would be amazing.

You guys have ALWAYS been able to solve all my crazy dilemmas!

Thank you in advance, and sorry if my grammar / explanations are not perfect.

Mike

[SamT]

How do you plan to recognize a correct path?

Sometimes it's easier to start with a possible Path and see if it exists.

http://gwicks.net/dictionaries.htm

to avoid reusing a grid Cell
Dim CellUsed(1 to 4, 1 to 4) As Boolean
set array Item True when corresponding Grid cell is used

[Paul_Hossler]

Basically, I have a 4 x 4 grid and would like to find all possible paths of various lengths of characters form 3 up to 16. It almost sounds exactly like a Boggle Solver, and I guess in some ways it is, but it's not for that, although the paths would be exactly the same.

Don't know Boggle

Can you explain more and maybe add some examples?

Can a character repeat, i.e. in (1,1) can you have "AAA" or just things like "AYZ"?

[Spielberg]

Thank you for the replies everyone. I am SO bad at describing things sometimes. Here's the rules for Boggle here, it'll explain it better than I could:
https://www.wikihow.com/Play-Boggle

The dictionary link is appreciated as I can surely use it for my other puzzles and games!

The main goal really of this "recursion" is figuring out how to find all possibilities based on Boggle pattern matching. I can't even begin to figure out how to do that in a program, beyond what I did by hand.

If the grid cells didn't "twist and turn" i think I could figure it out, but the complete "randomness" (for lack of a better word) just grinds my progress to a halt.

@Paul: No, letters may not repeat within a word. Each grid cell may be used only once. Interesting idea, though. as an option to be able to repeat grid cells. Thanks for the tip! :)

[SamT]

This is a variant of a Random Walk (https://en.wikipedia.org/wiki/Random_walk) problem.

This will not be a simple program. While I don't have the expertise to compute exactly how many possible Paths there are, I imagine it will be on the order of magnitude of n^n-1^^n-1 where n is the number of grid cells

I think you will need at least a Grid Class so that the code is not continually accessing the worksheet, and a Dictionary Class so that possible Steps and legitimate Paths can be validated.


The first step in creating an algorithm is determine the rules or restrictions or parameters.



Rule 1) No fewer than 3 steps per path
Restriction 2) Cannot reuse a grid cell
Parameter 3) each step must be on a legitimate path
What to do when one path contains many words (Feel, Feeling, Feelings)
How to handle when one starting cell leads to many paths (Feel, Fetch, Free, Field)
What to do when different paths return the same words.
Storing the legitimate results
How many CPU (core)s are available? Speed will be "Of The Essence" in this endeavor. Classes Are Essential.
???
???
???



The next possible step from any Cell (i, j) is always (i|i+1|i-1, j|j+1|j-1). These can be defined as Up, Down, Left, Right, UpLeft, DownLeft, UpRight. and DownRight. This is one place where Recursion could be used.

[Spielberg]

Well, SamT, as always, you've provided a great starting point! I am just wondering if I bit off more than I can chew with this...

But I will certainly take all advice and tips given and see what can be done with it!

Thanks again!

Mike

[p45cal]

Because I'll be away for a few days I decided to make a suggestion despite it being unfinished (it'd not efficient; there are many references to the sheet and ranges whereas I should really be using in-memory arrays throughout).
In the attached, in cell G8, is a number you can adjust; it causes the macro to pause every n iterations, draw the path at that point, and ask if you want to carry on.
Since the output includes all combinations including all lengths of the path, there's a hell of a lot of them.
Results are written to the sheet at cell A10 and below. This area is never erased by the macros so you'll need to it manually.

Plenty of comments in the code.

Realise, that although you didn't want stuff written for you, it takes an awful lot more effort to try and take you step by step in a tutorial type process, so perhaps the graphic portion of what I have written will help you through the logic; it did me.