Summary
Recently I have had a path-finding puzzle that has some complex constraints (currently, I don't have any solution for this one)
- A 2D matrix represented the graph. The length of a path is the number of traversed cells.
- One or more number sequences are to be found inside the matrix. Each sequence is scored with a value.
- Maximum length of the path in the graph. The number of picked cells must not exceed this value.
- At any given moment, you can only choose cells in a specific column or row.
- On each turn, you need to switch between column and row and stay on the same line as the last cell you picked. You have to move at right angles. (The direction is like the Snake game).
- Always start with picking the first cell from the top row, then go vertically down to pick the second cell, and then continue switching between column and row as usual.
- You can't choose the same cell twice. The resulting path must not contain duplicated cells.
For example:
The task is to find the shortest path, if possible in the graph that contains one or more sequences with the highest total score and the path's length is not exceed the provided maximum length.
The picture below demonstrates the solved puzzle with the resulting path marked in red:
Here, we have a path 3A-10-9B. This path contains the given sequence 3A-10-9B so, which earns 10pts. More complex graphs typically have longer paths containing various sequences at once.
More complex examples
Multiple Sequences
You can complete sequences in any order. The order in which the sequences are listed doesn't matter.
Wasted Moves
Sometimes we are forced to waste moves and choose different cells that don't belong to any sequence. Here are the rules:
- Able to waste 1 or 2 moves before the first sequence.
- Able to waste 1 or 2 moves between any neighboring sequences.
- However, you cannot break sequences and waste moves in the middle of them.
Here, we must waste one move before the sequence 3A-9B and two moves between sequences 3A-9B and 72-D4. Also, notice how red lines between 3A and 9B as well as between 72 and D4 "cross" previously selected cells D4 and 9B, respectively. You can pick different cells from the same row or column multiple times.
Optimal Sequences
Sometimes, it is not possible to have a path that contains all of the provided sequences. In this case, choose the way which achieved the most significant score.
In the above example, we can complete either 9B-3A-72-D4 or 72-D4-3A but not both due to the maximum path length of 5 cells. We have chosen the sequence 9B-3A-72-D4 since it grants more score points than 72-D4-3A.
Unsolvable solution
The first sequence 3A-D4 can't be completed since the code matrix doesn't contain code D4 at all. The second sequence, 72-10, can't be completed for another reason: codes 72 and 10 aren't located in the same row or column anywhere in the matrix and, therefore, can't form a sequence.
Conclusion
I am looking for any advice for this puzzle since I have no idea what keywords to look for. A pseudo-code or hints would be helpful for me, and I appreciate that. What has come to my mind is just Dijkstra:
- For each sequence, since the order doesn't matter, I have to find all get all possible paths with every permutation, then find the highest score path that contains other input sequences
- After that, choose the best of the best.
In this case, I doubt the performance will be the issue.
