/usr/share/mozart/doc/fdt/node31.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 3 4 5 6 7 8 9 10 11 12 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>7.1 Example: Fractions</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="node30.html">- Up -</A></TD><TD><A href="node32.html#section.propagators.pythagoras">Next >></A></TD></TR></TABLE><DIV id="section.propagators.fractions"><H2><A name="section.propagators.fractions">7.1 Example: Fractions</A></H2><DIV class="unnumbered"><H3><A name="label88">Problem Specification</A></H3><P>The Fractions Puzzle consists in finding distinct nonzero digits such that the following equation holds: </P><BLOCKQUOTE><P><IMG alt="{A\over{BC}} +
{D\over{EF}} +
{G\over{HI}}
=
1" src="latex140.png"></P></BLOCKQUOTE><P> </P></DIV><DIV class="unnumbered"><H3><A name="label89">Model</A></H3><P>We have a variable for every letter, similar as in the Send More Money Puzzle. Since the three fractions are symmetric, we can impose the order </P><BLOCKQUOTE><P><IMG alt="{A\over{BC}} \ge
{D\over{EF}} \ge
{G\over{HI}}" src="latex141.png"></P></BLOCKQUOTE><P> From the order constraints we obtain the redundant constraints </P><BLOCKQUOTE><P><IMG alt="3{A\over{BC}}\ge1
\qquad
\hbox{and}
\qquad
3{G\over{HI}}\le1" src="latex142.png"></P></BLOCKQUOTE><P> The order constraints together with the redundant constraints reduce the size of the search tree by one order of magnitude. </P></DIV><DIV class="unnumbered"><H3><A name="label90">Distribution Strategy</A></H3><P>We distribute on the list of letters using the standard first-fail strategy. </P><DIV id="progfractions"><HR><P><A name="progfractions"></A></P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Fractions</SPAN> Root}<BR> sol(a:A b:B c:C d:D e:E f:F g:G h:H i:I) = Root<BR> BC = {FD<SPAN class="keyword">.</SPAN>decl}<BR> EF = {FD<SPAN class="keyword">.</SPAN>decl}<BR> HI = {FD<SPAN class="keyword">.</SPAN>decl}<BR><SPAN class="keyword">in</SPAN> <BR> Root <SPAN class="keyword">:::</SPAN> 1<SPAN class="keyword">#</SPAN>9<BR> {FD<SPAN class="keyword">.</SPAN>distinct Root}<BR> BC <SPAN class="keyword">=:</SPAN> 10<SPAN class="keyword">*</SPAN>B <SPAN class="keyword">+</SPAN> C<BR> EF <SPAN class="keyword">=:</SPAN> 10<SPAN class="keyword">*</SPAN>E <SPAN class="keyword">+</SPAN> F<BR> HI <SPAN class="keyword">=:</SPAN> 10<SPAN class="keyword">*</SPAN>H <SPAN class="keyword">+</SPAN> I <BR> A<SPAN class="keyword">*</SPAN>EF<SPAN class="keyword">*</SPAN>HI <SPAN class="keyword">+</SPAN> D<SPAN class="keyword">*</SPAN>BC<SPAN class="keyword">*</SPAN>HI <SPAN class="keyword">+</SPAN> G<SPAN class="keyword">*</SPAN>BC<SPAN class="keyword">*</SPAN>EF <SPAN class="keyword">=:</SPAN> BC<SPAN class="keyword">*</SPAN>EF<SPAN class="keyword">*</SPAN>HI<BR> %% <SPAN class="comment">impose canonical order<BR></SPAN> A<SPAN class="keyword">*</SPAN>EF <SPAN class="keyword">>=:</SPAN> D<SPAN class="keyword">*</SPAN>BC <BR> D<SPAN class="keyword">*</SPAN>HI <SPAN class="keyword">>=:</SPAN> G<SPAN class="keyword">*</SPAN>EF<BR> %% <SPAN class="comment">redundant constraints<BR></SPAN> 3<SPAN class="keyword">*</SPAN>A <SPAN class="keyword">>=:</SPAN> BC<BR> 3<SPAN class="keyword">*</SPAN>G <SPAN class="keyword">=<:</SPAN> HI<BR> {FD<SPAN class="keyword">.</SPAN>distribute ff Root}<BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P class="caption"><STRONG>Figure 7.1:</STRONG> A script for the Fractions Puzzle.</P><HR></DIV><P> </P></DIV><DIV class="unnumbered"><H3><A name="label91">Script</A></H3><P>The script in <A href="node31.html#progfractions">Figure 7.1</A> constrains its root variable to a record having a field for every letter. Since Oz has no finite domain propagators for fractions, we eliminate the fractions by multiplying with the denominators. For every denominator we introduce an auxiliary variable. Since a finite domain propagator starts its work only after all variables of the constraint implemented by the propagator are constrained to finite domains in the constraint store, the script constrains the auxiliary variables for the denominators to the maximal finite domain using the procedure <CODE>FD<SPAN class="keyword">.</SPAN>decl</CODE>.</P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node30.html">- Up -</A></TD><TD><A href="node32.html#section.propagators.pythagoras">Next >></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>
|