/usr/share/mozart/doc/fdt/node23.html is in mozart-doc 1.4.0-8ubuntu1.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>4.3 Example: Zebra Puzzle</TITLE><LINK href="ozdoc.css" rel="stylesheet" type="text/css"></HEAD><BODY><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node22.html#section.elimination.family"><< Prev</A></TD><TD><A href="node20.html">- Up -</A></TD></TR></TABLE><DIV id="section.elimination.zebra"><H2><A name="section.elimination.zebra">4.3 Example: Zebra Puzzle</A></H2><P>This example shows a clever problem representation avoiding possible symmetries. It also illustrates the use of defined constraints. </P><DIV class="unnumbered"><H3><A name="label67">Problem Specification</A></H3><P>Five men with different nationalities live in the first five houses of a street. There are only houses on one side of the street. The men practice distinct professions, and each of them has a favorite drink and a favorite animal, all of them different. The five houses are painted with different colors. The following facts are known: </P><OL type="1"><LI><P>The Englishman lives in a red house.</P></LI><LI><P>The Spaniard owns a dog.</P></LI><LI><P>The Japanese is a painter.</P></LI><LI><P>The Italian drinks tea.</P></LI><LI><P>The Norwegian lives in the first house.</P></LI><LI><P>The owner of the green house drinks coffee.</P></LI><LI><P>The green house comes after the white one.</P></LI><LI><P>The sculptor breeds snails.</P></LI><LI><P>The diplomat lives in the yellow house.</P></LI><LI><P>Milk is drunk in the third house.</P></LI><LI><P>The Norwegian's house is next to the blue one.</P></LI><LI><P>The violinist drinks juice.</P></LI><LI><P>The fox is in the house next to that of the doctor.</P></LI><LI><P>The horse is in the house next to that of the diplomat.</P></LI><LI><P>The zebra is in the white house.</P></LI><LI><P>One of the men drinks water.</P></LI></OL><P> Who lives where? </P></DIV><DIV class="unnumbered"><H3><A name="label68">Model</A></H3><P>We number the houses from 1 to 5, where 1 is the first and 5 is last house in the street. There are 25 different properties (i. e. hosting an Englishman, being the green house, hosting a painter, hosting a dog, or hosting someone who drinks juice), and each of these properties must hold for exactly one house. The properties are partitioned into five groups of five members each, where the properties within one group must hold for different houses. The model has one variable for each of these properties, where the variable stands for the number of the house for which this property holds. </P></DIV><DIV class="unnumbered"><H3><A name="label69">Distribution Strategy</A></H3><P>We distribute on the variables for the properties with the standard first-fail strategy. </P><DIV id="progzebra"><HR><P><A name="progzebra"></A></P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Zebra</SPAN> Nb}<BR> Groups = [ [english spanish japanese italian norwegian]<BR> [green red yellow blue white]<BR> [painter diplomat violinist doctor sculptor]<BR> [dog zebra fox snails horse]<BR> [juice water tea coffee milk] ]<BR> Properties = {FoldR Groups Append nil}<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Partition</SPAN> Group}<BR> {FD<SPAN class="keyword">.</SPAN>distinct {Map Group <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> P} Nb<SPAN class="keyword">.</SPAN>P <SPAN class="keyword">end</SPAN>}}<BR> <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Adjacent</SPAN> X Y}<BR> {FD<SPAN class="keyword">.</SPAN>distance X Y <SPAN class="string">'=:'</SPAN> 1}<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">in</SPAN> <BR> %% <SPAN class="comment">Nb maps all properties to house numbers<BR></SPAN> {FD<SPAN class="keyword">.</SPAN>record number Properties 1<SPAN class="keyword">#</SPAN>5 Nb}<BR> {ForAll Groups Partition}<BR> Nb<SPAN class="keyword">.</SPAN>english = Nb<SPAN class="keyword">.</SPAN>red<BR> Nb<SPAN class="keyword">.</SPAN>spanish = Nb<SPAN class="keyword">.</SPAN>dog<BR> Nb<SPAN class="keyword">.</SPAN>japanese = Nb<SPAN class="keyword">.</SPAN>painter<BR> Nb<SPAN class="keyword">.</SPAN>italian = Nb<SPAN class="keyword">.</SPAN>tea<BR> Nb<SPAN class="keyword">.</SPAN>norwegian = 1<BR> Nb<SPAN class="keyword">.</SPAN>green = Nb<SPAN class="keyword">.</SPAN>coffee<BR> Nb<SPAN class="keyword">.</SPAN>green <SPAN class="keyword">>:</SPAN> Nb<SPAN class="keyword">.</SPAN>white<BR> Nb<SPAN class="keyword">.</SPAN>sculptor = Nb<SPAN class="keyword">.</SPAN>snails<BR> Nb<SPAN class="keyword">.</SPAN>diplomat = Nb<SPAN class="keyword">.</SPAN>yellow<BR> Nb<SPAN class="keyword">.</SPAN>milk = 3<BR> {Adjacent Nb<SPAN class="keyword">.</SPAN>norwegian Nb<SPAN class="keyword">.</SPAN>blue}<BR> Nb<SPAN class="keyword">.</SPAN>violinist = Nb<SPAN class="keyword">.</SPAN>juice<BR> {Adjacent Nb<SPAN class="keyword">.</SPAN>fox Nb<SPAN class="keyword">.</SPAN>doctor}<BR> {Adjacent Nb<SPAN class="keyword">.</SPAN>horse Nb<SPAN class="keyword">.</SPAN>diplomat}<BR> Nb<SPAN class="keyword">.</SPAN>zebra = Nb<SPAN class="keyword">.</SPAN>white<BR> {FD<SPAN class="keyword">.</SPAN>distribute ff Nb}<BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P class="caption"><STRONG>Figure 4.4:</STRONG> A script for the Zebra Puzzle.</P><HR></DIV><P> </P></DIV><DIV class="unnumbered"><H3><A name="label70">Script</A></H3><P><A href="node23.html#progzebra">Figure 4.4</A> shows a script based on the outlined model and distribution strategy. The script constrains the root variable <CODE>Nb</CODE> to a record that maps every property to a house number between 1 and 5. </P><P>The script introduces two defined constraints. The defined constraint </P><BLOCKQUOTE class="code"><CODE>{Partition Group}</CODE></BLOCKQUOTE><P> says that the properties in the list <CODE>Group</CODE> must hold for pairwise distinct houses. The defined constraint </P><BLOCKQUOTE class="code"><CODE>{Adjacent </CODE><I>X</I><CODE> </CODE><I>Y</I><CODE>}</CODE></BLOCKQUOTE><P> says that the properties <I>X</I> and <I>Y</I> must hold for houses that are next to each other. The statement </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>distance X Y <SPAN class="string">'=:'</SPAN> 1}</CODE></BLOCKQUOTE><P> creates a propagator for <IMG alt="|X-Y|=1" src="latex112.png">.</P><P>The script defines a search tree with 33 nodes. The unique solution is the record </P><BLOCKQUOTE class="code"><CODE>number(<BR> blue:2 coffee:5 diplomat:3 doctor:4 <BR> dog:3 english:4 fox:5 green:5 <BR> horse:4 italian:2 japanese:5 juice:1<BR> milk:3 norwegian:1 painter:5 red:4<BR> sculptor:2 snails:2 spanish:3 tea:2 <BR> violinist:1 water:4 white:1 yellow:3<BR> zebra:1<BR> )</CODE></BLOCKQUOTE><P></P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node22.html#section.elimination.family"><< Prev</A></TD><TD><A href="node20.html">- Up -</A></TD></TR></TABLE><HR><ADDRESS><A href="http://www.ps.uni-sb.de/~schulte/">Christian Schulte</A> and <A href="http://www.ps.uni-sb.de/~smolka/">Gert Smolka</A><BR><SPAN class="version">Version 1.4.0 (20110908185330)</SPAN></ADDRESS></BODY></HTML>
|