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