Più difficile che trovare la soluzione è determinare se una soluzione esiste. Assumendone l'esistenza, puoi semplicemente andare di brute-force.
Non so consigliarti un algoritmo migliore, ma dato che questo problema è simile al sudoku puoi provare a vedere se riesci a convertirlo in un problema topologico.