Thanks for taking a look.
I’m a beginner trying to continue to bite off more than I can chew. I’ve been trying to make something in excel/VBA that can find the longest path in a directed (one way) graph. The problem in question is the end game portion of this puzzle.
Essentially you are given a 6 x 6 grid of tiles with the objective: visit every tile three times. Depending on the tile determines which tile you may travel to next. Despite the variety, all paths are of equal length. Integer tiles 1,2,3 and 4 will only allow you to path to tiles that many squares adjacent or diagonal from itself so a 2 would let you select tiles two squares away from it. Of the piece tiles, the knight is the only one that functions as it does in chess. The bishop, rook and queen path direction mirrors their chess counterpart but only to live tiles on the edge of the board. The difficulty arises from the tiles changing once visited. Upon visiting a tile for a third time, it “dies” leaving a hole and one less node in the overall graph. Should you have no choice but dead tiles, the game ends. I note a 4 will never spawn in the middle 2x2 portion of the grid as it would give no options and instant loss. Your score is mostly determined by the number of tiles left so the fewer the better hence a longest path problem. In the beginning you can start anywhere. After that your choices are limited by the tiles on your path. A way to almost guarantee a perfect solution is to have visited all tiles twice while trying not to do so three times. Reaching this part isn’t terribly hard as the colour of the tiles indicate how many times they have been visited. And at this point, since there can be no more randomness the puzzle can be solved keeping in mind that there may not be a perfect solution. Alternatively, you can find the longest path that visits every tile exposing one layer at a time but there are drawbacks to that as you may forego many bonus point opportunities and other things along the way but I digress.
So as previously stated, I am attempting to make something that can find a maximum solution to a longest path problem. What I have at present is a worksheet to set up the board state, VBA code to read the board state and in the end calculate all the inputs (paths in) and outputs (paths out) of every tile using a 36x36 matrix on a second worksheet.
Each row and column is associated with a position in the 6x6 grid so row 1 and column 1 for (1,1), row 2 and column 2 for (2,1), r3 c3 for (3,1)… r7 c7 for (2,1), r8 c8 for (2,2)… ending at r36 c 36 for (6,6). By placing a 1 anywhere in this matrix, I am saying there is a path from one tile to another. In this case there are no paths to themselves so nothings would show up on the diagonal or (n,n) though it should still work.
This 36 x 36 grid is my first step to making the program understand which paths are possible and I hope by extension which forks are more favourable should I need to pick one. For example if I find a tile T1 with only one path in to it from a tile T2, since no other path in to T1 can ever be generated, T2 =>T1 must be part of the longest path solution if one exists. This has potential for a knock on effect if T2 also had other choices to path to. Imagine if T2 could have also pathed to T3, T4 and T5 in addition to T1. T3, T4 and T5 now have one less option going into them which on its own may not seem to do much but subtract 1 from their total inputs but say T3 had only T2 and T4 going into it, since T2 => T1, T3 is left with T4 so from one level of processing we have found two connections and our tree has grown by two levels. And though we don’t know where the connections lie in the overall solution yet, the more connections the clearer it becomes but more importantly being able to decrease the options overall should mean having to grow fewer branches in the tree thus less processing.
I want to store the contents of the 36x36 grid in perhaps an array to be used as a seed maybe named grid1 for a tree that upon processing it will highlight the more promising options at each point with which I would use to generate new arrays for the children of the parent 36x36 like grid11 and grid12 if there were two options. And then grid111, grid112, grid113 or grid 121, 122… until a solution is found.
I have an example of VBA code that can traverse a declared tree via depth first search but I can’t understand how it works even with the comments added by WBD because I don’t know enough about coding let alone VBA. But even then, in my case my tree needs to be grown from scratch. In both cases I don’t understand how to make it work but I sort of get the algorithm to complete the puzzle. I mean I have solved it manually a few times and once as close to how I imagined a computer would step by step before my project could do anything of use. Concepts of recursion, memoisation, depth/breadth first search, tree traversal, seeds… I know of them, I imagine I’ll need them but I have no idea how they work. And to top it all off, this is my first coding project, a project I started over three years ago that I haven’t touched until now.
At this point, I don't know how to move forward. I’d like someone to be able to break down all of those concepts outlined in such a way that I can take little steps towards understanding the code underlying them all with little projects in between that I can play around with before I move on.
Like exactly what code will be necessary, how they can work together... How to make a tree of arrays that grows. How to generate, link and name the children in the tree. That sort of stuff.
A lot to ask I know but again I’m out of ideas so any help is very much appreciated.
Let me know if you want to check it out.
I’m a beginner trying to continue to bite off more than I can chew. I’ve been trying to make something in excel/VBA that can find the longest path in a directed (one way) graph. The problem in question is the end game portion of this puzzle.
Essentially you are given a 6 x 6 grid of tiles with the objective: visit every tile three times. Depending on the tile determines which tile you may travel to next. Despite the variety, all paths are of equal length. Integer tiles 1,2,3 and 4 will only allow you to path to tiles that many squares adjacent or diagonal from itself so a 2 would let you select tiles two squares away from it. Of the piece tiles, the knight is the only one that functions as it does in chess. The bishop, rook and queen path direction mirrors their chess counterpart but only to live tiles on the edge of the board. The difficulty arises from the tiles changing once visited. Upon visiting a tile for a third time, it “dies” leaving a hole and one less node in the overall graph. Should you have no choice but dead tiles, the game ends. I note a 4 will never spawn in the middle 2x2 portion of the grid as it would give no options and instant loss. Your score is mostly determined by the number of tiles left so the fewer the better hence a longest path problem. In the beginning you can start anywhere. After that your choices are limited by the tiles on your path. A way to almost guarantee a perfect solution is to have visited all tiles twice while trying not to do so three times. Reaching this part isn’t terribly hard as the colour of the tiles indicate how many times they have been visited. And at this point, since there can be no more randomness the puzzle can be solved keeping in mind that there may not be a perfect solution. Alternatively, you can find the longest path that visits every tile exposing one layer at a time but there are drawbacks to that as you may forego many bonus point opportunities and other things along the way but I digress.
So as previously stated, I am attempting to make something that can find a maximum solution to a longest path problem. What I have at present is a worksheet to set up the board state, VBA code to read the board state and in the end calculate all the inputs (paths in) and outputs (paths out) of every tile using a 36x36 matrix on a second worksheet.
Each row and column is associated with a position in the 6x6 grid so row 1 and column 1 for (1,1), row 2 and column 2 for (2,1), r3 c3 for (3,1)… r7 c7 for (2,1), r8 c8 for (2,2)… ending at r36 c 36 for (6,6). By placing a 1 anywhere in this matrix, I am saying there is a path from one tile to another. In this case there are no paths to themselves so nothings would show up on the diagonal or (n,n) though it should still work.
This 36 x 36 grid is my first step to making the program understand which paths are possible and I hope by extension which forks are more favourable should I need to pick one. For example if I find a tile T1 with only one path in to it from a tile T2, since no other path in to T1 can ever be generated, T2 =>T1 must be part of the longest path solution if one exists. This has potential for a knock on effect if T2 also had other choices to path to. Imagine if T2 could have also pathed to T3, T4 and T5 in addition to T1. T3, T4 and T5 now have one less option going into them which on its own may not seem to do much but subtract 1 from their total inputs but say T3 had only T2 and T4 going into it, since T2 => T1, T3 is left with T4 so from one level of processing we have found two connections and our tree has grown by two levels. And though we don’t know where the connections lie in the overall solution yet, the more connections the clearer it becomes but more importantly being able to decrease the options overall should mean having to grow fewer branches in the tree thus less processing.
I want to store the contents of the 36x36 grid in perhaps an array to be used as a seed maybe named grid1 for a tree that upon processing it will highlight the more promising options at each point with which I would use to generate new arrays for the children of the parent 36x36 like grid11 and grid12 if there were two options. And then grid111, grid112, grid113 or grid 121, 122… until a solution is found.
I have an example of VBA code that can traverse a declared tree via depth first search but I can’t understand how it works even with the comments added by WBD because I don’t know enough about coding let alone VBA. But even then, in my case my tree needs to be grown from scratch. In both cases I don’t understand how to make it work but I sort of get the algorithm to complete the puzzle. I mean I have solved it manually a few times and once as close to how I imagined a computer would step by step before my project could do anything of use. Concepts of recursion, memoisation, depth/breadth first search, tree traversal, seeds… I know of them, I imagine I’ll need them but I have no idea how they work. And to top it all off, this is my first coding project, a project I started over three years ago that I haven’t touched until now.
At this point, I don't know how to move forward. I’d like someone to be able to break down all of those concepts outlined in such a way that I can take little steps towards understanding the code underlying them all with little projects in between that I can play around with before I move on.
Like exactly what code will be necessary, how they can work together... How to make a tree of arrays that grows. How to generate, link and name the children in the tree. That sort of stuff.
A lot to ask I know but again I’m out of ideas so any help is very much appreciated.
Let me know if you want to check it out.
