Sujet : Re: Sugurus
De : samuel_dot_devulder (at) *nospam* laposte_dot_net.invalid (Samuel DEVULDER)
Groupes : fr.sci.mathsDate : 30. Aug 2021, 13:22:56
Autres entêtes
Organisation : Aioe.org NNTP Server
Message-ID : <sgiij0$1b0d$1@gioia.aioe.org>
References : 1
User-Agent : Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101 Thunderbird/91.0.3
Le 27/08/2021 à 19:04, robby a écrit :
Ou bien il n'y a pas de façon mathématique de poser ce problème qui puisse se résoudre systématiquement de façon non gloutonne ?
Oui avec un programme quadratique en nombre entier ou un solveur SMT (Satisfiability Modulo Theories)
https://www.researchgate.net/publication/346020801_Solving_Suguru_using_an_SMT_Integer_solverEn 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.
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.
sam.
Sugurus
Re: Sugurus