Hum j'ai l'impression que ça dépend pas mal des contraintes que tu as... on pourrait imaginer de concevoir les tiles de telle manière qu'il en existe toujours un qui va dans un trou, mais apparemment c'est pas ton cas ^^.

Sinon plutôt que d'avoir des listes de tiles qui peuvent se trouver à proximité j'aurais plutôt vu des listes de bords : chaque tile a 4 bords, ou 6 ou 3 enfin peu importe, et il y a un nombre fini de bords possibles en tout. Deux tiles adjacents doivent avoir le même bord (dans le même sens mais ça simplifie pas mal si les bords sont symétriques à mon avis ^^). Ensuite tes différents modèles de tiles indiquent quels sont les différentes combinaisons de bords possibles.

À partir de là, tu peux imaginer de remplir ta map ligne par ligne de haut en bas, genre ; à supposer que tu n'as pas de contraintes sur le bord de la map tu auras pour la plupart des tiles deux bords adjacents imposés (le bord gauche et le bord supérieur) et deux bords libres. Donc pour être sûr que c'est possible il suffit que toutes les combinaisons de deux bords adjacents existent dans ton ensemble de tiles, ce qui est peut-être une contrainte raisonnable ? par contre si tu as des contraintes en bord de map ça ne résout pas vraiment le problème, sur la dernière ligne tu auras trois côtés imposés, et quatre pour le dernier tile, mais bon c'est peut-être une piste ^^