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.

StackExchange Computer Science Q#117449, answer score: 4