Pou connect game algorithm

Question

Recently I played a simple game on android called Pou, and one of it's inside games was a connect the dots on the field game. Here is a screenshot to better explain the situation.

At the beginning of the game you are given n-pairs of dots and you have to connect the same colored ones. While doing this you need to fill the matrix field.

Generating such a field is not a problem, but how can I be sure that it is solvable?

My question would be how can I generate a field that has a solution? Is this a graph problem? Or some kind of a connectivity problem?

Of course I can always produce a brute force solution, but I am looking for something better

Answer 1

Actually you can generate the matrix in such a way that you can be sure it is solvable.

The main idea is as follow. Let say that you need i pairs of dots and the matrix is n by n

1. Set i randomly chosen cells (start points) as heads and to each assign a different color.
2. At each iteration for each color move its head randomly (left, right, up, down) into an uncolored cell and color it with i-th color. (if there is no legal such moves do not consider this color any more -- that will be the end point)
3. When you are finished and there is no uncolored cells you created a legal coloring of the board.
4. If there are some uncolored cells -- it may be quite challenging but for sure doable to modify / extend the coloring you obtained to fill those regions with some color -- the easiest way would be to exclude those regions from the matrix altogether :-)

Some other very loose thoughts:

• each region that consists of more than 2 uncolored cells can be made legal (or at least some part of it) by assigning two additional dots to it;
• you can split your initial n by n matrix into smaller rectangular parts and assign to each part some number of dots (proportional to the area) and use the above method -- for sure there will be less uncolored cells when you merge those parts back (on the other hand the puzzle will be bit easier).

UPDATE

• once still in phase of coloring, if the next move produces a single, isolated cell: chose a different move and if no such move exists stop the coloring process for this color.
• if you want to have a predefined number of dots (or the number close to it), check not only for single isolated cell, but for whole isolated regions. [btw. mind the possibility of coloring a candidate for isolation region by extending its start point]
• for relative small n you can try using above method(s) until you hit full-coloring (so generate, check if legal, if not: generate again)

UPDATE II

If you have time you can try generating colors once at a time, with some probability of stopping, that depends on the length / area of the coloring. So basically just choose a random uncolored position and execute the above method. It should be easier to implement.