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


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


In other words, create a Hamiltonian path in a matrix.
A pic below exhaustively shows what I want.
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.