# How to find a path that connects all the dots in the matrix?

I have a matrix that consists of 0, 1, 2.

• 0 - dot.
• 1 - block.
• 2 - start dot (initial position in the path).

I have to create a path from the start dot, that

1. connects all the dots in the matrix and
2. visits each dot ONE time
3. doesn't visit blocks

In other words, create a Hamiltonian path in a matrix. A pic below exhaustively shows what I want.

• For small grids (less than 10x10) a backtrack algorithm with some pruning heuristics will be effective. See chapter 5.4 on the book cses.fi/book/book.pdf for some examples of pruning heuristics in this problem. – Laakeri Nov 22 '19 at 11:10

The problem of finding a Hamiltonian path in a partial grid graph (that is, an arbitrary subgraph of a grid, not necessarily even induced) remains NP-complete [1]. Thus, you are likely out of luck for a polynomial-time approach.

A good choice for a heuristic might depend on your instance size and further structure. However, in general, you could try say a genetic algorithm, ant colony optimization, or some more problem specific heuristic.

[1] Papadimitriou, Christos H., and Umesh V. Vazirani. "On two geometric problems related to the travelling salesman problem." Journal of Algorithms 5.2 (1984): 231-246.

• Couldn't you help with such type of algorithm? I'm very bad in algorithms and it will take me weeks for understanding and writing algorithm :( – Alexander Nov 22 '19 at 12:17
• @Alexander Sorry, I don't think there's a shortcut to happiness here. Maybe you can find a package or some implementation out there that's helpful for your programming language. – Juho Nov 22 '19 at 12:37
• programming language is not important, I need some general idea, a little piece of pseudocode – Alexander Nov 22 '19 at 18:12

Actually, grid graphs are a very specific class of input problems, and a good number of algorithms are known that can solve problems which remain hard in other instances, i.e., non-grid graphs.

Even if it is not directly related to your question, I could not avoid citing the following paper:

F. Keshavarz-Kohjerdi, A. Bagheri, A. Asgharian-Sardroud. A linear time algorithm for the longest path problem in rectangular grid graphs. Discrete Applied Mathematics, 2012 160(3) 210-217.

For your specific problem, the best (up to my knowledge) is a polynomial-time algorithm in solid grid-graphs:

W. Lenhart, C. Umans, Hamiltonian cycles in solid grid graphs, in: Proc. 38th Annual Symposium on Foundations of Computer Science, FOCS’97, 1997, pp. 496–505.

Hope this helps,

• as I mentioned above I'm very bad in algorithms. Couldn't you please help me with this one? I need just a general idea of the algorithm or a piece of pseudocode – Alexander Nov 23 '19 at 9:00
• Of all answers, I think that Ashkan R.Nejad's reply might be the best one if you want/need a quick implementation. I would then go for the idea of using a state space search formalism. Would you like to see a pseudocode of such approach? What is the size of your instances?? – Carlos Linares López Nov 23 '19 at 11:21

One simple way is to face this problem like a state-space search. Assume that going in each of 4 directions on a node that has not been visited is one action. Make a function that is responsible for producing all the next possible states given the current state. It produces a list of all next actions (at most 4 states). As you may know, we call this function the successor function. Then run a BFS\DFS search using this function. Run till all nodes on your matrice are visited.

Another better way is to face this problem like a traveling salesman problem [1]. Although it tries to find the path with the lowest cost, it is a good choice. There exists a dynamic programming algorithm for solving this problem. Tushar Roy has given a good explanation of this algorithm in his youtube channel (link).