{"id":477,"date":"2022-06-22T15:48:42","date_gmt":"2022-06-22T15:48:42","guid":{"rendered":"https:\/\/9h15.net\/activ\/?p=477"},"modified":"2022-06-22T15:48:42","modified_gmt":"2022-06-22T15:48:42","slug":"prolog-etape-c-entrainement","status":"publish","type":"post","link":"https:\/\/9h15.net\/activ\/prolog-etape-c-entrainement\/","title":{"rendered":"PROLOG : \u00e9tape C &#8211; entrainement"},"content":{"rendered":"\n<div class=\"wp-block-jetpack-markdown\"><p><code>Par O. Bailleux, Ma\u00eetre de conf\u00e9rences HDR \u00e0 l'universit\u00e9 de Bourgogne.<\/code><\/p>\n<h1>Listes et coupe choix &#8211; entrainement<\/h1>\n<p>Les <strong>activit\u00e9s d&rsquo;entrainement<\/strong> consistent \u00e0 traiter des <strong>exercices d&rsquo;entra\u00eenement<\/strong>. Vous devez d&rsquo;abord tenter de traiter ces exercices sans d\u00e9voiler d&rsquo;indice ni regarder la solution. Vous pouvez remonter dans le document pour relire certaines explications ou consulter les solutions des exercices de d\u00e9couverte ou d&rsquo;entra\u00eenement pr\u00e9c\u00e9demment trait\u00e9s. Si vous avez besoin d&rsquo;indices ou si vos solutions sont erron\u00e9es, analysez les causes de vos erreurs &#8211; au besoin, demandez des explications \u00e0 une personne qualifi\u00e9e &#8211; et refaites les exercices concern\u00e9s apr\u00e8s un d\u00e9lai d&rsquo;au moins une journ\u00e9e et au plus quelques jours.<\/p>\n<h2>Activit\u00e9 d&rsquo;entra\u00eenement C.ent<\/h2>\n<h3>C.ent1<\/h3>\n<p>Vous devez d\u00e9finir un pr\u00e9dicat <code>sum<\/code> permettant de produire toutes les valeurs pouvant \u00eatre obtenues en additionnant des nombres donn\u00e9s dans une liste d&rsquo;entr\u00e9e.<\/p>\n<p>Par exemple, l&rsquo;\u00e9valuation du but&#8230;<\/p>\n<pre><code class=\"language-Prolog\">sum([1,10,100],S).\n<\/code><\/pre>\n<p>&#8230;doit avoir pour r\u00e9sultat :<\/p>\n<pre><code class=\"language-Prolog\">S = 111\nS = 11\nS = 101\nS = 1\nS = 110\nS = 10\nS = 100\nS = 0\n<\/code><\/pre>\n<p>On consid\u00e8re que la valeur 0 est correcte. Elle repr\u00e9sente le cas o\u00f9 aucune des valeurs de la liste d&rsquo;entr\u00e9e n&rsquo;est utilis\u00e9e.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>On peut consid\u00e9rer trois possibilit\u00e9s, dont chacune sera d\u00e9crite par une clause.<\/p>\n<ol>\n<li>La liste d&rsquo;entr\u00e9e est vide. Dans ce cas, la seule valeur calculable est 0.<\/li>\n<li>La liste d&rsquo;entr\u00e9e n&rsquo;est pas vide. Elle se d\u00e9compose en <code>[T|R]<\/code>. On s&rsquo;int\u00e9resse aux sommes r\u00e9alisables en utilisant la premi\u00e8re valeur.<\/li>\n<li>La liste d&rsquo;entr\u00e9e n&rsquo;est pas vide. Elle se d\u00e9compose en <code>[_|R]<\/code>. On s&rsquo;int\u00e9resse aux sommes r\u00e9alisables sans utiliser la premi\u00e8re valeur.<\/li>\n<\/ol>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">sum([],0).                               % clause 1\nsum([T|R],S) :- .................... .   % clause 2\nsum([_|R],S) :- .................... .   % clause 3\n<\/code><\/pre>\n<p>La clause 2 dit que <code>S<\/code> est r\u00e9alisable en ajoutant <code>T<\/code> et une somme de valeurs de <code>R<\/code>.<\/p>\n<p>La clause 3 dit que <code>S<\/code> est une somme de valeurs de <code>R<\/code>.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Solution&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">sum([],0).\nsum([T|R],S) :- sum(R,S1), S is S1+T.\nsum([_|R],S) :- sum(R,S).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h3>C.ent2<\/h3>\n<p>Nous avons vu dans la partie d\u00e9couverte sur les listes la d\u00e9finition d&rsquo;un pr\u00e9dicat <code>pref<\/code> qui permet d&rsquo;obtenir tous les pr\u00e9fixes non vide d&rsquo;une liste.<\/p>\n<pre><code class=\"language-Prolog\">pref([T],[T|_]).\npref([T|P],[T|R]) :- pref(P,R).\n<\/code><\/pre>\n<p>Par exemple, le but&#8230;<\/p>\n<pre><code class=\"language-Prolog\">pref(P,[1,2,3]).\n<\/code><\/pre>\n<p>&#8230;produit le r\u00e9sultat :<\/p>\n<pre><code>P = [1]\nP = [1, 2]\nP = [1, 2, 3]\n<\/code><\/pre>\n<p>On appelle <strong>sous-liste<\/strong> d&rsquo;une liste $L$ toute suite non vide de valeurs cons\u00e9cutives apparaissant dans $L$. Par exemple, les sous-listes de [1,2,3] sont :<\/p>\n<pre><code>[1] [1, 2] [1, 2, 3] [2] [2, 3] [3]\n<\/code><\/pre>\n<p>Vous devez d\u00e9finir un pr\u00e9dicat <code>sl<\/code> tel que <code>sl(S,L)<\/code> sp\u00e9cifie que <code>S<\/code>\u00a0est une sous-liste de <code>L<\/code>. Ce pr\u00e9dicat doit permettre de produire toutes les sous-listes d&rsquo;une liste ou de d\u00e9terminer si une liste est sous-liste d&rsquo;une autre. Vous pouvez raisonner de mani\u00e8re constructive sur le premier cas d&rsquo;utilisation ou de mani\u00e8re plus d\u00e9clarative sur le deuxi\u00e8me.<\/p>\n<p>Par exemple, le but&#8230;<\/p>\n<pre><code class=\"language-Prolog\">sl(P,[1,2,3]).\n<\/code><\/pre>\n<p>&#8230;devra produire le r\u00e9sultat :<\/p>\n<pre><code>S = [1]\nS = [1, 2]\nS = [1, 2, 3]\nS = [2]\nS = [2, 3]\nS = [3]\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Vous pouvez vous appuyer sur cette propri\u00e9t\u00e9 :<\/p>\n<blockquote>\n<p>Soit une liste non vide <code>L<\/code> ayant pour t\u00eate <code>T<\/code> et pour reste <code>R<\/code>. Toute sous-liste de <code>L<\/code> est soit un pr\u00e9fixe de <code>L<\/code>, soit une sous-liste de <code>R<\/code>.<\/p>\n<\/blockquote>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">sl(S,L)     :- ............... .  %clause 1\nsl(S,[_|R]) :- ............... .  %clause 2\n<\/code><\/pre>\n<p>La clause 1 dit que tout pr\u00e9fixe d&rsquo;une liste <code>L<\/code> est une sous-liste de <code>L<\/code>.<\/p>\n<p>La clause 2 dit que toute sous liste d&rsquo;une liste <code>R<\/code> est une sous liste de toute liste de la forme <code>[_|R]<\/code>.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Solution&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">sl(S,L) :- pref(S,L).\nsl(S,[_|R]) :- sl(S,R).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h3>C.ent3<\/h3>\n<p>Vous devez d\u00e9finir un pr\u00e9dicat <code>dec<\/code> permettant de d\u00e9composer une liste en un de ses \u00e9l\u00e9ments et un reliquat qui est la liste de tous les autres \u00e9l\u00e9ments.<\/p>\n<p>Plus pr\u00e9cis\u00e9ment, <code>dec(L,E,R)<\/code> dit que <code>E<\/code> est un \u00e9l\u00e9ment de <code>L<\/code> et que le reliquat <code>R<\/code> est la liste des autres \u00e9l\u00e9ments de <code>L<\/code> (dans l&rsquo;ordre o\u00f9 ils apparaissant dans <code>L<\/code>).<\/p>\n<p>Par exemple, le but&#8230;<\/p>\n<pre><code class=\"language-Prolog\">dec([1,2,3],E,A).\n<\/code><\/pre>\n<p>&#8230;doit produire le r\u00e9sultat :<\/p>\n<pre><code>A = [2,3], E = 1\nA = [1,3], E = 2\nA = [1,2], E = 3\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Une premi\u00e8re mani\u00e8re \u00e9vidente de d\u00e9composer une liste <code>[T|R]<\/code> est de consid\u00e9rer son premier \u00e9l\u00e9ment et son reste. La clause correspondante est :<\/p>\n<pre><code class=\"language-Prolog\">dec([T|R],T,R).\n<\/code><\/pre>\n<p>Comment d\u00e9crire les autres d\u00e9compositions ?<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">dec([T|R],T,R).\ndec([T|R],E,[T|Q]) :- .......... .\n<\/code><\/pre>\n<p>La deuxi\u00e8me clause dit que <code>[T|R]<\/code> peut \u00eatre d\u00e9compos\u00e9e en un \u00e9l\u00e9ment <code>E<\/code> et un reliquat <code>[T|Q]<\/code>. Comment exprimer la relation entre <code>R<\/code>, <code>E<\/code> et <code>Q<\/code> ?<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Solution&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">dec([T|R],T,R).\ndec([T|R],E,[T|Q]) :- dec(R,E,Q).\n<\/code><\/pre>\n<p>Voici une illustration de la deuxi\u00e8me clause.<\/p>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/06\/pC11.png\" alt=\"pC11\"><\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>On appelle <strong>anagramme<\/strong> d&rsquo;une liste <code>L<\/code> toute les listes ayant les m\u00eames \u00e9l\u00e9ments dans un ordre quelconque.<\/p>\n<p>Vous devez, en utilisant notre pr\u00e9dicat <code>dec<\/code>, d\u00e9finir un pr\u00e9dicat <code>ana<\/code> permettant de produire les anagrammes d&rsquo;une liste. Par exemple, le but&#8230;<\/p>\n<pre><code class=\"language-Prolog\">ana([a,b,c],A).\n<\/code><\/pre>\n<p>&#8230;devra produire le r\u00e9sultat :<\/p>\n<pre><code>A = [a, b, c]\nA = [a, c, b]\nA = [b, a, c]\nA = [b, c, a]\nA = [c, a, b]\nA = [c, b, a]\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Le seul anagramme d&rsquo;une liste ayant un seul \u00e9l\u00e9ment est la liste elle-m\u00eame.<\/p>\n<p>Tout anagramme d&rsquo;une liste <code>L<\/code> plus grande est constitu\u00e9 d&rsquo;un \u00e9l\u00e9ment de <code>L<\/code> suivi d&rsquo;un anagramme du reliquat de la d\u00e9composition de cette liste telle que d\u00e9finie par le pr\u00e9dicat <code>dec<\/code>.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">ana([E],[E]).\nana(L,[T|Q]) :- ............... .\n<\/code><\/pre>\n<p>La deuxi\u00e8me clause dit qu&rsquo;un anagramme <code>[T|Q]<\/code> de L est constitu\u00e9 d&rsquo;un \u00e9l\u00e9ment <code>T<\/code> issu de la d\u00e9composition de <code>L<\/code> par <code>dec<\/code> et d&rsquo;un anagramme <code>Q<\/code> du reliquat de cette d\u00e9composition.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Solution&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">ana([E],[E]).\nana(L,[T|Q]) :- dec(L,T,A), ana(A,Q).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>On peut utiliser le pr\u00e9dicat <code>ana<\/code> pour produire les anagramme d&rsquo;une cha\u00eene de caract\u00e8res. Pour ce faire, on dispose d&rsquo;un pr\u00e9dicat <code>string_chars<\/code> qui \u00e9tablit une relation entre une chaine et une liste de caract\u00e8res. Voici deux buts utilisant ce pr\u00e9dicat et leur r\u00e9sultats :<\/p>\n<pre><code class=\"language-Prolog\">string_chars(&quot;Tim&quot;,L).        --&gt;  L = ['T', i, m]\nstring_chars(S,['T', i, m]).  --&gt;  S = &quot;Tim&quot;\n<\/code><\/pre>\n<p>Les caract\u00e8res repr\u00e9sentant des majuscules sont entre cotes pour les diff\u00e9rencier des variables. Ces cotes sont facultatives pour les lettres minuscules.<\/p>\n<p>D\u00e9finissez un pr\u00e9dicat <code>anagramme<\/code> permettant de produire sous forme de chaines les anagrammes d&rsquo;une chaine. Par exemple, le but&#8230;<\/p>\n<pre><code class=\"language-Prolog\">anagramme(&quot;Tomy&quot;,A).\n<\/code><\/pre>\n<p>&#8230;produit tous les anagrammes du mot <code>&quot;Tomy&quot;<\/code>.<\/p>\n<pre><code>A = &quot;Tomy&quot;\nA = &quot;Toym&quot;\nA = &quot;Tmoy&quot;\nA = &quot;Tmyo&quot;\nA = &quot;Tyom&quot;\nA = &quot;Tymo&quot;\netc. (18 autres r\u00e9ponses)\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Solution&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">anagramme(S,A) :- \n    string_chars(S,L),\n    ana(L,M),\n    string_chars(A,M).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h3>C.ent4<\/h3>\n<p>Vous devez d\u00e9finir un pr\u00e9dicat <code>sd<\/code> permettant de supprimer les doublons (valeurs ayant plusieurs occurrences) dans une liste.<\/p>\n<p>Si <code>L_in<\/code> est une liste connue et <code>S_out<\/code> est une variable non instanci\u00e9e, alors le but&#8230;<\/p>\n<pre><code class=\"language-Prolog\">sd(L_in, S_out).\n<\/code><\/pre>\n<p>Fait remonter dans la variable <code>S_out<\/code> une liste contenant exactement une occurrence de chaque valeur de <code>L_in<\/code>.<\/p>\n<p>Par exemple, l&rsquo;\u00e9valuation de&#8230;<\/p>\n<pre><code class=\"language-Prolog\">sd([2,1,2,3,1,1,3],F).\n<\/code><\/pre>\n<p>&#8230;produit le r\u00e9sultat :<\/p>\n<pre><code>F = [2, 1, 3]\n<\/code><\/pre>\n<p>Vous pouvez utiliser le pr\u00e9dicat standard <code>member<\/code> qui permet de v\u00e9rifier si une valeur est dans une liste. Voici deux exemples de buts construits avec ce pr\u00e9dicat et leur r\u00e9sultats :<\/p>\n<pre><code class=\"language-Prolog\">member(1,[2,1,1,3,2]).   --&gt;  true\nmember(4,[2,1,1,3,2]).   --&gt;  false\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Quant la liste d&rsquo;entr\u00e9e et vide, la liste de sortie l&rsquo;est aussi.<\/p>\n<p>Si le premier \u00e9l\u00e9ment <code>T<\/code> de la liste d&rsquo;entr\u00e9e est aussi dans le reste <code>Q<\/code> de cette liste, alors la liste de sortie est obtenue en supprimant les doublons de <code>Q<\/code>.<\/p>\n<p>Si le premier \u00e9l\u00e9ment <code>T<\/code> de la liste d&rsquo;entr\u00e9e n&rsquo;est pas dans le reste <code>Q<\/code> de cette liste, alors la liste de sortie est  constitu\u00e9e de <code>T<\/code> et de la liste obtenue en supprimant les doublons de <code>Q<\/code>.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">sd([],[]).\nsd([T|R],.....) :- member(T,R),!, .......... . \nsd([T|R],.....) :- .......... .\n<\/code><\/pre>\n<p>La premi\u00e8re clause concerne le cas o\u00f9 le premier \u00e9l\u00e9ment <code>T<\/code> de la liste d&rsquo;entr\u00e9e apparait \u00e9galement dans le reste <code>R<\/code> de cette liste. On ne conservera pas cette premi\u00e8re occurrence et la liste de sortie sera obtenue en supprimant les doublons de <code>R<\/code>. En raison de la pr\u00e9sence du coupe-choix, la troisi\u00e8me clause ne sera prise en compte que si <code>T<\/code> n&rsquo;est pas dans <code>R<\/code>.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Solution&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">sd([],[]).\nsd([T|R],S) :- member(T,R),!, sd(R,S). \nsd([T|R],[T|S]) :- sd(R,S).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<h2>Activit\u00e9 d&rsquo;approfondissement<\/h2>\n<p>Vous commencez \u00e0 avoir une certaine aisance avec la manipulation des listes ? Je vous propose maintenant de r\u00e9soudre des probl\u00e8mes avec Prolog.<\/p>\n<h3>C.top1<\/h3>\n<p>Nous allons utiliser Prolog pour r\u00e9soudre le probl\u00e8me suivant :<\/p>\n<blockquote>\n<p>Un berger est sur la rive gauche d&rsquo;une rivi\u00e8re en pr\u00e9sence d&rsquo;un loup, d&rsquo;une ch\u00e8vre et d&rsquo;une salade. Il peut traverser la rivi\u00e8re soit seul, soit avec la ch\u00e8vre, soit avec la salade, soit avec le loup.<\/p>\n<p>Il ne doit en aucun cas laisser la ch\u00e8vre seule avec le loup ou avec la salade sur une des rives.<\/p>\n<p>Il faut trouver un sc\u00e9nario permettant, en un nombre donn\u00e9 de travers\u00e9es, d&#8217;emmener la ch\u00e8vre, le loup, le berger et la salade sur la rive droite.<\/p>\n<\/blockquote>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/06\/pC7.png\" alt=\"pC7\"><\/p>\n<p>Pour r\u00e9soudre un tel probl\u00e8me, nous devons trouver un moyen de repr\u00e9senter les donn\u00e9es. Il y a de nombreuses possibilit\u00e9s et j&rsquo;en ai choisi une, mais vous pouvez en chercher d&rsquo;autres.<\/p>\n<p>On appelle <strong>\u00e9tat<\/strong> une donn\u00e9e repr\u00e9sentant les positions respectives du berger, du loup, de la ch\u00e8vre et de la salade. Un \u00e9tat sera repr\u00e9sent\u00e9 par une liste de 4 \u00e9l\u00e9ments pouvant prendre deux valeurs possibles : <code>g<\/code> pour rive gauche et <code>d<\/code> pour rive droite.<\/p>\n<p>Par exemple :<\/p>\n<ul>\n<li><code>[g,g,d,d]<\/code> repr\u00e9sente l&rsquo;\u00e9tat dans lequel le berger et le loup sont sur la rive gauche et la ch\u00e8vre et la salade sont sur la rive droite.<\/li>\n<li><code>[d,g,d,g]<\/code> repr\u00e9sente l&rsquo;\u00e9tat dans lequel le berger est sur la rive droite, le loup sur la rive gauche, la ch\u00e8vre sur la rive droite et la salade sur la rive gauche.<\/li>\n<\/ul>\n<p>On d\u00e9finit le pr\u00e9dicat <code>op<\/code> qui d\u00e9finit la notion de <strong>rives oppos\u00e9es<\/strong> :<\/p>\n<pre><code class=\"language-Prolog\">op(d,g).\nop(g,d).\n<\/code><\/pre>\n<hr>\n<p>Dans un premier temps, je vous propose de d\u00e9finir un pr\u00e9dicat <code>bad<\/code> qui d\u00e9termine les <strong>\u00e9tats interdits.<\/strong> Plus pr\u00e9cis\u00e9ment, <code>bad(E)<\/code> soit \u00eatre satisfait si et seulement si l&rsquo;\u00e9tat <code>E<\/code> correspond \u00e0 une situation dans laquelle la ch\u00e8vre et le loup ou la ch\u00e8vre et la salade sont sur la m\u00eame rive sans le berger.<\/p>\n<blockquote>\n<p>Pourquoi les \u00e9tats interdits et pas les \u00e9tats autoris\u00e9s ? Parce-qu&rsquo;on peut mod\u00e9liser les \u00e9tats interdits de mani\u00e8re plus concise.<\/p>\n<\/blockquote>\n<p>Une premi\u00e8re solution consiste \u00e0 d\u00e9finir <code>bad<\/code> en 4 faits comme ceci :<\/p>\n<pre><code class=\"language-Prolog\">bad([g,d,d,_]). % berger \u00e0 gauche, loup et ch\u00e8vre \u00e0 droite\nbad([g,_,d,d]). % berger \u00e0 gauche, ch\u00e8vre et salade \u00e0 droite\nbad([d,g,g,_]). % berger \u00e0 droite, loup et ch\u00e8vre \u00e0 gauche\nbad([d,_,g,g]). % berger \u00e0 droite, ch\u00e8vre et salade \u00e0 gauche\n<\/code><\/pre>\n<p>Proposez une d\u00e9finition plus concise en deux clauses, en utilisant le pr\u00e9dicat <code>op<\/code>.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Solution&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">bad([A,B,B,_]) :- op(A,B).\nbad([A,_,B,B]) :- op(A,B).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Maintenant, vous devez d\u00e9finir un pr\u00e9dicat <code>trav<\/code> permettant de d\u00e9terminer si une travers\u00e9e est r\u00e9alisable, c&rsquo;est \u00e0 dire si elle correspond \u00e0 une de ces 4 possibilit\u00e9s :<\/p>\n<ol>\n<li>Le berger traverse seul.<\/li>\n<li>Le berger traverse avec le loup.<\/li>\n<li>Le berger traverse avec la ch\u00e8vre.<\/li>\n<li>Le berger traverse avec la salade.<\/li>\n<\/ol>\n<p>Plus pr\u00e9cis\u00e9ment, <code>trav(E1,E2,T)<\/code> est satisfait si et seulement si une travers\u00e9e r\u00e9alisable permet de passer de l&rsquo;\u00e9tat <code>E1<\/code> \u00e0 l&rsquo;\u00e9tat <code>E2<\/code>, <code>T<\/code> \u00e9tant ce qui change de rive avec le berger. Les valeurs possibles de <code>T<\/code> sont <code>loup<\/code>, <code>chevre<\/code>, <code>salade<\/code> et <code>rien<\/code>.<\/p>\n<p>Par exemple, l&rsquo;\u00e9valuation du but&#8230;<\/p>\n<pre><code class=\"language-Prolog\">trav([g,g,g,g],S,T).\n<\/code><\/pre>\n<p>&#8230;a pour r\u00e9sultats :<\/p>\n<pre><code>S = [d, d, g, g], T = loup\nS = [d, g, d, g], T = chevre\nS = [d, g, g, d], T = salade\nS = [d, g, g, g], T = rien\n<\/code><\/pre>\n<p>La premi\u00e8re solution dit que le berger et le loup ont chang\u00e9 de rive, puisque le nouvel \u00e9tat est <code>[d,d,g,g]<\/code>.  La quatri\u00e8me solution dit que le berger traverse seul. Le nouvel \u00e9tat, <code>[d,g,g,g]<\/code> indique que le loup, le ch\u00e8vre et la salade sont rest\u00e9s sur la rive gauche.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>On peut d\u00e9finir <code>trav<\/code> en 4 clauses correspondant respectivement aux cas o\u00f9 le berger traverse seul, avec le loup, avec la ch\u00e8vre et avec la salade. Voici la premi\u00e8re clause correspondant au cas o\u00f9 le berger traverse seul :<\/p>\n<pre><code class=\"language-Prolog\">trav([D,L,C,S],[A,L,C,S],rien) :- op(D,A).\n<\/code><\/pre>\n<p>Les positions <code>L<\/code>, <code>C<\/code> et <code>S<\/code>, du loup, de la ch\u00e8vre et de la salade, ne changent pas de valeur entre l&rsquo;\u00e9tat avant la travers\u00e9e (premier slot) et l&rsquo;\u00e9tat apr\u00e8s la travers\u00e9e (deuxi\u00e8me slot). Par contre, la position du berger (premier slot) passe de <code>g<\/code> \u00e0 <code>d<\/code> ou de <code>d<\/code> \u00e0 <code>g<\/code>. (La variable D repr\u00e9sente la rive de d\u00e9part et la variable A la rive d&rsquo;arriv\u00e9e.)<\/p>\n<p>\u00c0 vous trouver les trois clauses restantes.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Solution&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">trav([D,L,C,S],[A,L,C,S],rien)   :- op(D,A).\ntrav([D,D,C,S],[A,A,C,S],loup)   :- op(D,A).\ntrav([D,L,D,S],[A,L,A,S],chevre) :- op(D,A).\ntrav([D,L,C,D],[A,L,C,A],salade) :- op(D,A).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Il vous reste \u00e0 d\u00e9finir le pr\u00e9dicat <code>transp<\/code> tel que <code>transp(I,F,N,L)<\/code> qui produise, si applicable, la liste <code>L<\/code> des travers\u00e9es permettant de passer d&rsquo;un \u00e9tat initial <code>I<\/code> \u00e0 un \u00e9tat final <code>F<\/code> en <code>N<\/code> \u00e9tapes.<\/p>\n<p>Par exemple, l&rsquo;\u00e9valuation du but&#8230;<\/p>\n<pre><code class=\"language-Prolog\">transp([g,g,g,g],[d,d,d,d],7,Plan).\n<\/code><\/pre>\n<p>&#8230;doit produire les listes :<\/p>\n<pre><code>Plan = [chevre, rien, loup, chevre, salade, rien, chevre]\nPlan = [chevre, rien, salade, chevre, loup, rien, chevre]\n<\/code><\/pre>\n<p>&#8230;qui sont les deux solutions du probl\u00e8me en 7 \u00e9tapes.<\/p>\n<p>La premi\u00e8re liste s&rsquo;interpr\u00e8te de la mani\u00e8re suivante :<\/p>\n<ol>\n<li>Le berger traverse avec la ch\u00e8vre.<\/li>\n<li>Il revient seul sur la rive gauche.<\/li>\n<li>Il retourne sur la rive droite avec le loup.<\/li>\n<li>Il revient sur la rive gauche avec la ch\u00e8vre.<\/li>\n<li>Il retourne sur la rive droite avec la salade.<\/li>\n<li>Il revient seul sur la rive gauche.<\/li>\n<li>Il traverse une derni\u00e8re fois de gauche \u00e0 droite avec la ch\u00e8vre.<\/li>\n<\/ol>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice1&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Si l&rsquo;\u00e9tat initial et l&rsquo;\u00e9tat final sont identiques, le transport n\u00e9cessite 0 \u00e9tapes et la liste des travers\u00e9es est vide, ce qui correspond \u00e0 la clause :<\/p>\n<pre><code class=\"language-Prolog\">transp(F,F,0,[]).\n<\/code><\/pre>\n<p>Il reste \u00e0 \u00e9crire la clause r\u00e9cursive qui permet de passer d&rsquo;un \u00e9tat initial \u00e0 un \u00e9tat final avec un nombre <code>N<\/code> de travers\u00e9es sup\u00e9rieur \u00e0 0.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice2&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Voici le d\u00e9but de le deuxi\u00e8me clause :<\/p>\n<pre><code class=\"language-Prolog\">transp(I,F,N,[E|S]) :- N&gt;0, .............................. .\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice3&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Voici une version \u00e0 compl\u00e9ter de la deuxi\u00e8me clause<\/p>\n<pre><code class=\"language-Prolog\">transp(I,F,N,[E|S]) :- N&gt;0, trav(I,J,E), not(bad(J)),\n                       .............................. .\n<\/code><\/pre>\n<blockquote>\n<p>Passer de l&rsquo;\u00e9tat <code>I<\/code> \u00e0 l&rsquo;\u00e9tat <code>F<\/code> en un nombre <code>N&gt;0<\/code> d&rsquo;\u00e9tapes suppose :<\/p>\n<ul>\n<li>de faire une travers\u00e9e <code>E<\/code> permettant de passer de l&rsquo;\u00e9tat <code>I<\/code> \u00e0 un \u00e9tat <code>J<\/code>,<\/li>\n<li>que <code>J<\/code> soit un \u00e9tat autoris\u00e9,<\/li>\n<li>&#8230;<\/li>\n<\/ul>\n<\/blockquote>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Solution&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">transp(F,F,0,[]).\ntransp(I,F,N,[E|S]) :- N&gt;0, trav(I,J,E), not(bad(J)),\n                       N1 is N-1, transp(J,F,N1,S).\n<\/code><\/pre>\n<p>La solution compl\u00e8te est donc :<\/p>\n<pre><code class=\"language-Prolog\">op(d,g).\nop(g,d).\n\nbad([A,B,B,_]) :- op(A,B).\nbad([A,_,B,B]) :- op(A,B).\n\ntrav([D,D,C,S],[A,A,C,S],loup) :- op(D,A).\ntrav([D,L,D,S],[A,L,A,S],chevre) :- op(D,A).\ntrav([D,L,C,D],[A,L,C,A],salade) :- op(D,A).\ntrav([D,L,C,S],[A,L,C,S],rien) :- op(D,A).\n\ntransp(F,F,0,[]).\ntransp(I,F,N,[E|S]) :- N&gt;0, trav(I,J,E), not(bad(J)),\n                       N1 is N-1, transp(J,F,N1,S).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Ce qui est remarquable, c&rsquo;est que ce programme de r\u00e9solution comporte moins de caract\u00e8res que l&rsquo;\u00e9nonc\u00e9 du probl\u00e8me \u00e0 r\u00e9soudre ! Sans compter les espaces, l&rsquo;\u00e9nonc\u00e9 comporte 402 caract\u00e8res alors que le programme complet en comporte 319.<\/p>\n<p>Nous avons donc l\u00e0 une illustration de la puissance d&rsquo;expression de Prolog. Certes, le passage de l&rsquo;\u00e9nonc\u00e9 au programme est loin d&rsquo;\u00eatre \u00e9vident et n\u00e9cessite une certaine exp\u00e9rience, mais une fois ma\u00eetris\u00e9e, une m\u00eame approche peut \u00eatre utilis\u00e9e pour r\u00e9soudre de nombreux probl\u00e8mes.<\/p>\n<p>Dans cet exercice, nous avons trait\u00e9 un probl\u00e8me de planification. Dans le suivant, nous abordons un casse-t\u00eate c\u00e9l\u00e8bre.<\/p>\n<h3>C.top2<\/h3>\n<p>Nous allons maintenant nous attaquer \u00e0 un casse-t\u00eate tr\u00e8s c\u00e9l\u00e8bre : le probl\u00e8me du z\u00e8bre. Voici une variante moderne de l&rsquo;\u00e9nonc\u00e9 :<\/p>\n<blockquote>\n<p>On consid\u00e8re cinq maisons, toutes de couleurs diff\u00e9rentes (rouge, bleu, jaune, blanc, vert), dans lesquelles logent cinq personnes de professions diff\u00e9rentes (peintre, sculpteur, diplomate, m\u00e9decin et violoniste) et de nationalit\u00e9s diff\u00e9rentes (anglaise, espagnole, japonaise, norv\u00e9gienne et italienne) ayant chacun une boisson favorite (th\u00e9, jus de fruits, caf\u00e9, lait et vin) et un animal favori (chien, escargots, renard, cheval et z\u00e8bre).<\/p>\n<p>On dispose des faits suivants :<\/p>\n<ol>\n<li>\n<p>Le norv\u00e9gien habite la premi\u00e8re maison \u00e0 gauche.<\/p>\n<\/li>\n<li>\n<p>On boit du lait dans la maison du milieu.<\/p>\n<\/li>\n<li>\n<p>L&rsquo;Anglais habite la maison rouge.<\/p>\n<\/li>\n<li>\n<p>L&rsquo;Espagnol poss\u00e8de un chien.<\/p>\n<\/li>\n<li>\n<p>Le Japonais est peintre.<\/p>\n<\/li>\n<li>\n<p>L&rsquo;Italien boit du th\u00e9.<\/p>\n<\/li>\n<li>\n<p>Le propri\u00e9taire de la maison verte boit du caf\u00e9.<\/p>\n<\/li>\n<li>\n<p>Le sculpteur \u00e9l\u00e8ve des escargots.<\/p>\n<\/li>\n<li>\n<p>Le diplomate habite la maison jaune.<\/p>\n<\/li>\n<li>\n<p>Le violoniste boit du jus de fruit.<\/p>\n<\/li>\n<li>\n<p>La maison verte est a droite de la blanche.<\/p>\n<\/li>\n<li>\n<p>Le Norv\u00e9gien habite a cote de la maison bleue.<\/p>\n<\/li>\n<li>\n<p>Le renard est dans une maison voisine de celle du m\u00e9decin.<\/p>\n<\/li>\n<li>\n<p>Le cheval est \u00e0 cot\u00e9 de la maison du diplomate.<\/p>\n<\/li>\n<\/ol>\n<p>On veut savoir quelle est la couleur, la nationalit\u00e9, la boisson, l&rsquo;animal et la profession associ\u00e9s \u00e0 chacune des maisons.<\/p>\n<\/blockquote>\n<p><img decoding=\"async\" src=\"https:\/\/9h15.net\/activ\/wp-content\/uploads\/2022\/06\/pC8.png\" alt=\"pC8\"><\/p>\n<p>Il nous faut une repr\u00e9sentation des informations \u00e0 rechercher. Il existe plusieurs approches possibles, plus ou moins efficaces. Je vous propose de repr\u00e9senter chacune des lignes apparaissant sur la figure pr\u00e9c\u00e9dente par une liste.<\/p>\n<p>La d\u00e9finition du pr\u00e9dicat permettant la r\u00e9solution du probl\u00e8me commence ainsi :<\/p>\n<pre><code class=\"language-Prolog\">sol(C,N,B,A,P) :-\n        C=[_,_,_,_,_],\n        N=[norvege,_,_,_,_],\n        B=[_,_,lait,_,_],\n        A=[_,_,_,_,_],\n        P=[_,_,_,_,_],\n        % \u00c0 compl\u00e9ter\n<\/code><\/pre>\n<ul>\n<li>La variable <code>C<\/code> repr\u00e9sente la liste des couleurs dans l&rsquo;ordre des maisons dans le rue, en partant de la gauche.<\/li>\n<li>La variable <code>N<\/code> repr\u00e9sente la liste des nationalit\u00e9s dans le m\u00eame ordre.<\/li>\n<li>La variable <code>B<\/code> repr\u00e9sente la liste des boissons dans le m\u00eame ordre.<\/li>\n<li>La variable <code>A<\/code> repr\u00e9sente la liste des animaux dans le m\u00eame ordre.<\/li>\n<li>La variable <code>P<\/code> repr\u00e9sente la liste des professions dans le m\u00eame ordre.<\/li>\n<\/ul>\n<p>\u00c0 ce stade, les seules informations qui sont donn\u00e9es est que chaque liste contient 5 valeurs, que le norv\u00e9gien habite la premi\u00e8re maison (premier indice de l&rsquo;\u00e9nonc\u00e9) et que la personne qui boit du lait habite la maison centrale (deuxi\u00e8me indice de l&rsquo;\u00e9nonc\u00e9).<\/p>\n<p>Il faut ajouter les autres indices de l&rsquo;\u00e9nonc\u00e9 sous une forme exploitable par Prolog.<\/p>\n<p>Commen\u00e7ons par le troisi\u00e8me indice de l&rsquo;\u00e9nonc\u00e9 du probl\u00e8me :<\/p>\n<blockquote>\n<p><strong>L&rsquo;anglais habite la maison rouge.<\/strong><\/p>\n<\/blockquote>\n<p>Cet indice concerne la liste <code>C<\/code> des couleurs et la liste <code>N<\/code> des nationalit\u00e9s. Il nous dit que <code>anglais<\/code> est dans la m\u00eame position dans la liste des nationalit\u00e9s que <code>rouge<\/code> dans la liste des couleurs.<\/p>\n<p>Pour le traduire en Prolog, nous allons d\u00e9finir un pr\u00e9dicat <code>memePos<\/code> tels que si <code>L1<\/code>, <code>L2<\/code> sont des listes et <code>E1<\/code>, <code>E2<\/code> des \u00e9l\u00e9ments, alors le but&#8230;<\/p>\n<pre><code class=\"language-Prolog\">memePos(E1,L1,E2,L2).\n<\/code><\/pre>\n<p>&#8230;est satisfait si et seulement si la position de <code>E1<\/code> dans <code>L1<\/code> est la m\u00eame que celle de <code>E2<\/code> dans <code>L2<\/code>.<\/p>\n<p>Voici deux exemples de buts et les r\u00e9sultats de leurs \u00e9valuations :<\/p>\n<pre><code>memePos(b,[a,b,c],c,[d,c,a]).  --&gt; true\nmemePos(a,[a,b,c],c,[d,c,a]).  --&gt; false\n<\/code><\/pre>\n<p>Donnez la d\u00e9finition de <code>memePos<\/code>.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Les deux \u00e9l\u00e9ments apparaissant en t\u00eate de chaque liste sont dans la m\u00eame position (cas trivial).<\/p>\n<p>Si deux \u00e9l\u00e9ments apparaissent en m\u00eame position dans les restes de deux listes alors ils apparaissent en m\u00eame positions dans ces deux listes (clause r\u00e9cursive).<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Solution&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">memePos(E1,[E1|_],E2,[E2|_]).\nmemePos(E1,[_|R1],E2,[_|R2]) :- memePos(E1,R1,E2,R2).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Continuez \u00e0 compl\u00e9ter la d\u00e9finition du pr\u00e9dicat <code>sol<\/code> en y ajoutant les indices 3 \u00e0 10 de l&rsquo;\u00e9nonc\u00e9.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice3&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>L&rsquo;indice n\u00b03 s&rsquo;exprime de cette mani\u00e8re :<\/p>\n<pre><code class=\"language-Prolog\">memePos(anglais,N,rouge,C)\n<\/code><\/pre>\n<blockquote>\n<p>Le symbole <code>anglais<\/code> apparait en m\u00eame position dans le liste des nationalit\u00e9 que le symbole <code>rouge<\/code> dans la liste des couleurs.<\/p>\n<\/blockquote>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Solution&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">sol(C,N,B,A,P) :-\n    C=[_,_,_,_,_],\n    N=[norvegien,_,_,_,_],                % indice 1\n    B=[_,_,lait,_,_],                     % indice 2\n    A=[_,_,_,_,_],\n    P=[_,_,_,_,_],\n    memePos(anglais,N,rouge,C),           % indice 3\n    memePos(chien,A,espagnol,N),          % indice 4\n    memePos(japonais,N,peintre,P),        % indice 5\n    memePos(italien,N,the,B),             % indice 6\n    memePos(verte,C,cafe,B),              % indice 7\n    memePos(sculpteur,P,escargots,A),     % indice 8\n    memePos(diplomate,P,jaune,C),         % indice 9\n    memePos(violoniste,P,jus,B),          % indice 10\n<\/code><\/pre>\n<p>\u00c0 ce stade, il peut \u00eatre int\u00e9ressant de tester la r\u00e9solution du but&#8230;<\/p>\n<pre><code class=\"language-Prolog\">sol(C,N,B,A,P).\n<\/code><\/pre>\n<p>&#8230;pour voir si Prolog peut faire des d\u00e9ductions \u00e0 partir des indices donn\u00e9s.<\/p>\n<p>Il s&rsquo;av\u00e8re que oui. Cette \u00e9valuation produit de nombreuses r\u00e9ponses compatibles aves les donn\u00e9es fournies, telle que :<\/p>\n<pre><code>A = [escargots, _1840, chien, _1852, _1858],\nB = [caf\u00e9, jus, lait, _1942, the],\nC = [verte, rouge, jaune, _1818, _1824],\nN = [norvegien, anglais, espagnol, japonais, italien],\nP = [sculpteur, violoniste, diplomate, peintre, _656]\n<\/code><\/pre>\n<p>Les variables commen\u00e7ant par le caract\u00e8re <code>_<\/code> sont non instanci\u00e9es. Attention, le fait que <code>escargots<\/code> soit associ\u00e9 \u00e0 la premi\u00e8re maison dans cette r\u00e9ponse n&rsquo;implique pas que ce soit le cas dans la solution du probl\u00e8me complet. Parmi les nombreuses solutions du probl\u00e8me partiel, certaines associent l&rsquo;escargot \u00e0 d&rsquo;autres maisons.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Int\u00e9ressons nous maintenant \u00e0 l&rsquo;indice n\u00b0 11 :<\/p>\n<blockquote>\n<p><strong>La maison verte est a droite de la blanche.<\/strong><\/p>\n<\/blockquote>\n<p>l&rsquo;expression &quot;\u00e0 droite&quot; est ici \u00e0 prendre au sens strict. La maison verte imm\u00e9diatement apr\u00e8s la blanche.<\/p>\n<p>Vous devez d\u00e9finir un pr\u00e9dicat <code>apres<\/code> tel que si <code>L<\/code>, est une liste et <code>X<\/code>, <code>Y<\/code> des \u00e9l\u00e9ments, alors le but&#8230;<\/p>\n<pre><code class=\"language-Prolog\">apres(X,Y,L).\n<\/code><\/pre>\n<p>&#8230;est satisfait si et seulement si <code>Y<\/code> apparait imm\u00e9diatement apr\u00e8s <code>X<\/code> dans <code>L<\/code>.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Voici la premi\u00e8re clause qui concerne le cas trivial o\u00f9 <code>X<\/code> et <code>Y<\/code> sont en d\u00e9but de liste :<\/p>\n<pre><code class=\"language-prolog\">apres(X,Y,[X,Y|_]).\n<\/code><\/pre>\n<p>Il reste \u00e0 \u00e9crire la clause r\u00e9cursive.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Solution&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">apres(X,Y,[X,Y|_]).\napres(X,Y,[_|L]) :- apres(X,Y,L).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Donnez maintenant le but exprimant l&rsquo;indice n\u00b011, qui sera \u00e0 ajouter dans la d\u00e9finition du pr\u00e9dicat <code>sol<\/code>.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Solution&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">apres(blanche,verte,C)               % indice 11\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Il nous reste 3 indices \u00e0 encoder :<\/p>\n<blockquote>\n<p>Le norv\u00e9gien habite a cote de la maison bleue.<\/p>\n<p>Le renard est dans une maison voisine de celle du m\u00e9decin.<\/p>\n<p>Le cheval est \u00e0 cot\u00e9 de la maison du diplomate.<\/p>\n<\/blockquote>\n<p>Dans les trois cas, on exprime qu&rsquo;un \u00e9l\u00e9ment <code>X<\/code> apparait dans une liste <code>L1<\/code> \u00e0 une position situ\u00e9e imm\u00e9diatement avant ou apr\u00e8s la position d&rsquo;un \u00e9l\u00e9ment <code>Y<\/code> dans une liste <code>L2<\/code>.<\/p>\n<p>Vous devez d\u00e9finir un pr\u00e9dicat <code>contigu<\/code> pour exprimer cette contrainte par le but :<\/p>\n<pre><code class=\"language-Prolog\">contigu(X,L1,Y,L2).\n<\/code><\/pre>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Voici les deux clauses non r\u00e9cursives :<\/p>\n<pre><code class=\"language-Prolog\">contigu(X,[X|_],Y,[_,Y|_]).\ncontigu(X,[_,X|_],Y,[Y|_]).\n<\/code><\/pre>\n<p>Il vous reste \u00e0 \u00e9crire la clause r\u00e9cursive.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Solution&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">contigu(X,[X|_],Y,[_,Y|_]).\ncontigu(X,[_,X|_],Y,[Y|_]).\ncontigu(X,[_|R1],Y,[_|R2]) :- contigu(X,R1,Y,R2).\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Ajoutez \u00e0 la d\u00e9finition du pr\u00e9dicat <code>sol<\/code> les trois derniers indices.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Solution&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">sol(C,N,B,A,P) :-\n    C=[_,_,_,_,_],\n    N=[norvegien,_,_,_,_],                % indice 1\n    B=[_,_,lait,_,_],                     % indice 2\n    A=[_,_,_,_,_],\n    P=[_,_,_,_,_],\n    memePos(anglais,N,rouge,C),           % indice 3\n    memePos(chien,A,espagnol,N),          % indice 4\n    memePos(japonais,N,peintre,P),        % indice 5\n    memePos(italien,N,the,B),             % indice 6\n    memePos(verte,C,caf\u00e9,B),              % indice 7\n    memePos(sculpteur,P,escargots,A),     % indice 8\n    memePos(diplomate,P,jaune,C),         % indice 9\n    memePos(violoniste,P,jus,B),          % indice 10\n    apres(blanche,verte,C),               % indice 11\n    contigu(norvegien,N,bleu,C),          % indice 12\n    contigu(renard,A,medecin,P),          % indice 13\n    contigu(cheval,A,diplomate,P).        % indice 14\n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>En lan\u00e7ant le but&#8230;<\/p>\n<pre><code class=\"language-Prolog\">sol(C,N,B,A,P).\n<\/code><\/pre>\n<p>&#8230;on obtient une seule r\u00e9ponse, mais incompl\u00e8te :<\/p>\n<pre><code>A = [renard, cheval, escargots, chien, _1858],\nB = [_1924, the, lait, jus, caf\u00e9],\nC = [jaune, bleu, rouge, blanche, verte],\nN = [norvegien, italien, anglais, espagnol, japonais],\nP = [diplomate, medecin, sculpteur, violoniste, peintre]\n<\/code><\/pre>\n<p>La raison est qu&rsquo;on \u00e0 oubli\u00e9 de dire que quelqu&rsquo;un boit du vin et qu&rsquo;il y a un z\u00e8bre dans l&rsquo;une des maisons. Vous pouvez v\u00e9rifier que les symboles <code>vin<\/code> et <code>zebre<\/code> n&rsquo;apparaissent pas dans le programme.<\/p>\n<p>Il vous reste donc un dernier d\u00e9fit \u00e0 relever : trouver un moyen simple d&rsquo;ajouter l&rsquo;information manquante.<\/p>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Indice&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<p>Le pr\u00e9dicat standard <code>member<\/code> permet de sp\u00e9cifier qu&rsquo;un \u00e9l\u00e9ment <code>E<\/code> appartient \u00e0 une liste <code>L<\/code> avec le but <code>member(E,L)<\/code>.<\/p>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<div class=\"spoiler-wrap\">\n\t\t\t\t<div class=\"spoiler-head folded\">&quot;Solution&quot;<\/div>\n\t\t\t\t<div class=\"spoiler-body\"><\/p>\n<pre><code class=\"language-Prolog\">sol(C,N,B,A,P) :-\n    C=[_,_,_,_,_],\n    N=[norvegien,_,_,_,_],                % indice 1\n    B=[_,_,lait,_,_],                     % indice 2\n    A=[_,_,_,_,_],\n    P=[_,_,_,_,_],\n    memePos(anglais,N,rouge,C),           % indice 3\n    memePos(chien,A,espagnol,N),          % indice 4\n    memePos(japonais,N,peintre,P),        % indice 5\n    memePos(italien,N,the,B),             % indice 6\n    memePos(verte,C,caf\u00e9,B),              % indice 7\n    memePos(sculpteur,P,escargots,A),     % indice 8\n    memePos(diplomate,P,jaune,C),         % indice 9\n    memePos(violoniste,P,jus,B),          % indice 10\n    apres(blanche,verte,C),               % indice 11\n    contigu(norvegien,N,bleu,C),          % indice 12\n    contigu(renard,A,medecin,P),          % indice 13\n    contigu(cheval,A,diplomate,P),        % indice 14\n    member(zebre,A),\n    member(vin,B). \n<\/code><\/pre>\n<p><\/div>\n\t\t\t<\/div>\n<hr>\n<p>Nous obtenons enfin l&rsquo;unique solution du probl\u00e8me :<\/p>\n<pre><code>A = [renard, cheval, escargots, chien, zebre],\nB = [vin, the, lait, jus, caf\u00e9],\nC = [jaune, bleu, rouge, blanche, verte],\nN = [norvegien, italien, anglais, espagnol, japonais],\nP = [diplomate, medecin, sculpteur, violoniste, peintre]\n<\/code><\/pre>\n<p>Ici encore, le programme qui r\u00e9sout le probl\u00e8me est plus court que l&rsquo;\u00e9nonc\u00e9 du probl\u00e8me ! Sans compter les espaces, l&rsquo;\u00e9nonc\u00e9 contient 1128 caract\u00e8res alors que le programme en contient 559, soit presque deux fois moins. On peut \u00e9videmment r\u00e9duire la taille de l&rsquo;\u00e9nonc\u00e9 (et du programme), mais sans changer le fait que les tailles de l&rsquo;\u00e9nonc\u00e9 et du programme de r\u00e9solution ont le m\u00eame ordre de grandeur.<\/p>\n<hr>\n<\/div>\n","protected":false},"excerpt":{"rendered":"","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"","sticky":false,"template":"","format":"standard","meta":{"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[6],"tags":[],"class_list":["post-477","post","type-post","status-publish","format-standard","hentry","category-prolog","entry"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","_links":{"self":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/477","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/comments?post=477"}],"version-history":[{"count":1,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/477\/revisions"}],"predecessor-version":[{"id":478,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/posts\/477\/revisions\/478"}],"wp:attachment":[{"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/media?parent=477"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/categories?post=477"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/9h15.net\/activ\/wp-json\/wp\/v2\/tags?post=477"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}