Path: ...!news.snarked.org!news.gegeweb.eu!gegeweb.org!usenet-fr.net!agneau.org!nntpfeed.proxad.net!proxad.net!feeder1-1.proxad.net!cleanfeed1-b.proxad.net!nnrp1-2.free.fr!not-for-mail
Subject: Re: Sugurus
Newsgroups: fr.sci.maths
References: <61291b21$0$21601$426a74cc@news.free.fr>
 <sgiij0$1b0d$1@gioia.aioe.org>
From: robby <me@pla.net.invalid>
Date: Mon, 30 Aug 2021 15:19:18 +0200
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:78.0) Gecko/20100101
 Thunderbird/78.11.0
MIME-Version: 1.0
In-Reply-To: <sgiij0$1b0d$1@gioia.aioe.org>
Content-Type: text/plain; charset=iso-8859-15; format=flowed
Content-Transfer-Encoding: 8bit
Content-Language: fr
Lines: 27
Message-ID: <612cdad6$0$27450$426a34cc@news.free.fr>
Organization: Guest of ProXad - France
NNTP-Posting-Date: 30 Aug 2021 15:19:18 CEST
NNTP-Posting-Host: 91.168.150.105
X-Trace: 1630329558 news-4.free.fr 27450 91.168.150.105:38290
X-Complaints-To: abuse@proxad.net
Bytes: 2212

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