Re: Sugurus

Le 30/08/2021 à 14:22, Samuel DEVULDER a écrit :

En gros on encore chaque case par une variable d'un programme linéaire. Une variable une case vide dans une région de N places s'encode avec 1 <= V <= N, une case avec un indice devient V = indice. Ensuite on ajoute à ce programme linéaire les contraintes d'adjacence qui sont de la forme V1!=V2, ce qui s'encode avec la contrainte quadratique suivante: (V1-V2)² >= 1.

ça suffit a imposer des entiers, ça, meme si résolu dans R ?

Cependant il me semble que l'encodage en programme linéaire/quadratique ou contraintes SMT n'est pas spécialement adapté aux propriétés de ces systèmes, et ne me semble pas plus puissant qu'une résolution par force brute.

tout dépend ce qu'on appelle puissant, et des contraintes qu'on se donne.
par exemple la résolution par exploration systématique des arbres suppose pas mal de mémoire, dont une pile, et peut demander beaucoup de pas avant de trouver la solution ( vu qu'on back track pour explorer potentiellement tout l'arbre des possibles si pas de bol ).
La méthode que tu cite ici est peut-etre plus directe.
--
Fabrice