Pathfinder for a puzzle game

I want to develop a game like this one : https://gamesge.com/fr/fill-one-line-puzzle-game/

Starting with an empty grid I have to create a pathfinder to fill the grid with one line.

The empty grid The filled grid

I only heard of A* pathfinder and flood-fill algorithm, but I don't think it can help me. Do you know algorithms which would help me to create my own algorithm to generate the paths?


Backtracking algorithm should be good enough to solve that problem