Pour illustrer un peu (même si vous aviez probablement déjà saisi, mais là j'ai du temps à perdre ), voilà un petit schéma. En premier, mon jeu de tiles :



Les règles associées sont simples : un tile peut être à coté d'un autre si leurs bords en commun partagent la même couleur. Vous remarquerez qu'il manque (volontairement) le tile tout bleu. Maintenant admettons qu'à l'étape N - 1 de mon algo, j'en suis ici :



Je suis bloqué. En respectant les contraintes, je ne peux pas remplir la dernière case. Et pourtant tout ce que j'ai placé jusqu'ici respectait parfaitement toutes les règles, l'objectif serait donc de se "rendre compte" le plus tôt possible que je vais vers une impasse puisqu'avec la façon naïve ce n'est que vers la fin que le problème apparaît.