Create an algorithm for filling the playing field?

Question

Programming

Greetings!
I can’t cope with the task - maybe the habro-community will tell you in which direction to look.
There is a playing field n by m cells.
We expose x pairs of figures on it (for example, in random order).
The task of the algorithm is to connect pairs of figures with lines that pass through free cells (cells cannot be connected diagonally) in such a way that there are no empty cells left on the field. Or to say that there is no solution for this arrangement of pieces.
Connector lines cannot cross.
Maybe someone met a similar problem at the olympiads or somewhere else.
I would be grateful for any hints =)

Answer 1

I would look towards finding ways. There are many algorithms - A * (A star), wave, etc. Personally, I have experience with the wave algorithm - the implementation is quite simple. A * at one time could not overpower.
Calculate the "distance" between the points, and start from the closest to each other. Once a path has been built, these points (cells) that are included in it are no longer available when calculating for the next path. The full filling of the field can be achieved by "playing" with the number of points.

Answer 2

It looks like a PCB routing task.

Answer 3

Looks like a task for A*. I hope this helps: eax.me/a-star/