Les serpents sont sur les murs ! - Lycée de la mer (Gujan Mestras)

Le problème se joue dans une grille rectangulaire ou autre. On veut construire des chemins dans cette grille, un chemin étant une succession case/mur/case/mur... qui ne repasse pas deux fois par la même case(les murs extérieurs peuvent être ignorés).
On cherche à trouver des chemins de telle sorte que chaque mur ne peut être traversé que par un et un seul chemin.
Une des questions peut être : pour une grille donnée, peut -on trouver le nombre minimum de chemins que l'on peut utiliser ?