Comment by cousin_it

I think a naive tree search (start from one tile and try adding others with matching edges) might find a solution pretty fast, because most of the search space gets discarded early.