en gros tu veux faire du bruteforce sur une grille dont les lignes sont des permutations au lieu d'une grille totalement quelconque ? c'est déjà une première optimisation, mais ça doit rester pas mal coûteux qd même...

moi ce que je propose c'est vraiment tout simple : j'ai pas envie d'écrire le code parce que ma religion me l'interdit, mais conceptuellement on prend l'arbre des grilles partielles remplies dans un certain ordre (avec feuille = grille entièrement remplie), et on fait un parcours en profondeur en zappant les sous-arbres où on détecte une collision, jusqu'à atteindre une feuille