Path: ...!weretis.net!feeder6.news.weretis.net!feeder8.news.weretis.net!news.mixmin.net!aioe.org!wWi+bf82x/J4IG13ZEtRgw.user.46.165.242.75.POSTED!not-for-mail
From: Samuel DEVULDER <samuel_dot_devulder@laposte_dot_net.invalid>
Newsgroups: fr.sci.maths
Subject: Re: Sugurus
Date: Mon, 30 Aug 2021 14:22:56 +0200
Organization: Aioe.org NNTP Server
Message-ID: <sgiij0$1b0d$1@gioia.aioe.org>
References: <61291b21$0$21601$426a74cc@news.free.fr>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 8bit
Injection-Info: gioia.aioe.org; logging-data="44045"; posting-host="wWi+bf82x/J4IG13ZEtRgw.user.gioia.aioe.org"; mail-complaints-to="abuse@aioe.org";
User-Agent: Mozilla/5.0 (Windows NT 10.0; Win64; x64; rv:91.0) Gecko/20100101
 Thunderbird/91.0.3
Content-Language: fr
X-Antivirus-Status: Clean
X-Notice: Filtered by postfilter v. 0.9.2
X-Antivirus: Avast (VPS 210829-8, 29/8/2021), Outbound message
Bytes: 2085
Lines: 22

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_solver

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.

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.