1
$\begingroup$

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: enter image description here

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

enter image description here

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.

enter image description here

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.

enter image description here

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

enter image description here

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.

$\endgroup$
1

1 Answer 1

1
$\begingroup$

I believe the problem is, in the worst case, NP-hard. In particular, finding a Hamiltonian path in an induced subgraph of a grid graph is NP-hard. (See https://cs.stackexchange.com/a/68600/755.) Moreover, it seems like it is possible to construct an instance of such a problem in your setting, by putting the same value in all cells in the vertex set of the induced subgraph, and choosing a sequence and a minimum length that requires visiting everyone of those cells exactly once.

The problem is clearly in NP. Therefore, one approach is to solve it with a SAT solver. You should be able to formulate this as an instance of SAT, with boolean variables that capture the path taken through the graph and which cells are picked and which sequences have been scored. Then, you could use an off-the-shelf SAT solver to search for a solution. It is possible this might work for your situation. It's hard to know for sure without trying it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.