Consulting

Results 1 to 7 of 7

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

  1. #1

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

    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

  2. #2
    Moderator VBAX Sage SamT's Avatar
    Joined
    Oct 2006
    Location
    Near Columbia
    Posts
    7,814
    Location
    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
    Last edited by SamT; 09-07-2020 at 09:42 PM.
    I expect the student to do their homework and find all the errrors I leeve in.


    Please take the time to read the Forum FAQ

  3. #3
    VBAX Sage
    Joined
    Apr 2007
    Location
    United States
    Posts
    8,711
    Location
    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"?
    ---------------------------------------------------------------------------------------------------------------------

    Paul


    Remember: Tell us WHAT you want to do, not HOW you think you want to do it

    1. Use [CODE] ....[/CODE ] Tags for readability
    [CODE]PasteYourCodeHere[/CODE ] -- (or paste your code, select it, click [#] button)
    2. Upload an example
    Go Advanced / Attachments - Manage Attachments / Add Files / Select Files / Select the file(s) / Upload Files / Done
    3. Mark the thread as [Solved] when you have an answer
    Thread Tools (on the top right corner, above the first message)
    4. Read the Forum FAQ, especially the part about cross-posting in other forums
    http://www.vbaexpress.com/forum/faq...._new_faq_item3

  4. #4
    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!
    Last edited by Spielberg; 09-08-2020 at 07:11 AM. Reason: Forgot to add something

  5. #5
    Moderator VBAX Sage SamT's Avatar
    Joined
    Oct 2006
    Location
    Near Columbia
    Posts
    7,814
    Location
    This is a variant of a 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.
    I expect the student to do their homework and find all the errrors I leeve in.


    Please take the time to read the Forum FAQ

  6. #6
    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

  7. #7
    Knowledge Base Approver VBAX Wizard p45cal's Avatar
    Joined
    Oct 2005
    Location
    Surrey UK
    Posts
    5,844
    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.
    Attached Files Attached Files
    p45cal
    Everyone: If I've helped and you can't be bothered to acknowledge it, I can't be bothered to look at further posts from you.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •