Serpent

Une grille de snake fait n cases de côté. Il s'agit de noircir des cases de façon à représenter un serpent. Chaque case représente un anneau du serpent. Sur le bord horizontal et le bord vertical, on indique le nombre d'anneaux dans cette ligne ou colonne. On donne également les deux extrémités du serpent.

Il y a des règles supplémentaires :

• le serpent forme une ligne continue – il n'y a pas deux serpents
• un anneau du serpent ne peut avoir de côté commun qu'avec son anneau précédent et son anneau suivant.

Le problème peut être énoncé simplement en donnant les contraintes sur les bords et les coordonnées des extrémités :

h = [1, 1, 7, 3, 4, 2, 1, 2]
v = [5, 4, 1, 3, 1, 3, 1, 3]
start = 0,7
end = 7, 0

[ [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0] ]

Ou bien une grille 1D où toutes les lignes sont à la suite :

[0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

La première solution peut sembler plus naturelle mais à l'usage, la seconde est plus simple. À vous de voir.

On pourra compléter la grille en plaçant par exemple 1 pour un anneau, -1 pour une absence d'anneau et 0 pour une case non encore résolue – beaucoup d'autres choix possibles.

• Il faut vérifier que chaque ligne et colonne est compatible, tenant compte des cases non encore résolue, avec le compte en tête de ligne et colonne.
• Il faut vérifier que chaque anneau a deux anneaux voisins, sauf pour les extrémités qui n'ont qu'un anneau voisin.