<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>3.6 Example: Safe</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="node18.html#section.problem.watching"><< Prev</A></TD><TD><A href="node13.html">- Up -</A></TD></TR></TABLE><DIV id="section.problem.safe"><H2><A name="section.problem.safe">3.6 Example: Safe</A></H2><P></P><DIV class="unnumbered"><H3><A name="label52">Problem Specification</A></H3><P>The code of Professor Smart's safe is a sequence of 9 distinct nonzero digits <IMG alt="C_1,\ldots,C_9" src="latex11.png"> such that the following equations and inequations are satisfied: </P><BLOCKQUOTE><P><IMG alt="\begin{array}{rcl}
& C_4 - C_6 = C_7\\
& C_1 * C_2 * C_3 = C_8 + C_9\\
& C_2 + C_3 + C_6 < C_8\\
& C_9 < C_8\\
& C_1\neq1,\ldots, C_9\neq9
\end{array}" src="latex103.png"></P></BLOCKQUOTE><P> Can you determine the code? </P></DIV><DIV class="unnumbered"><H3><A name="label53">Model and Distribution Strategy</A></H3><P>We choose the obvious model that has a variable for every digit <IMG alt="C_1,\ldots,C_9" src="latex11.png">. We distribute over these variables with the standard first-fail strategy. </P><P></P><DIV class="figure" id="progsafe"><HR><P><A name="progsafe"></A></P></DIV><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Safe</SPAN> C}<BR> {FD<SPAN class="keyword">.</SPAN>tuple code 9 1<SPAN class="keyword">#</SPAN>9 C}<BR> {FD<SPAN class="keyword">.</SPAN>distinct C}<BR> C<SPAN class="keyword">.</SPAN>4 <SPAN class="keyword">-</SPAN> C<SPAN class="keyword">.</SPAN>6 <SPAN class="keyword">=:</SPAN> C<SPAN class="keyword">.</SPAN>7<BR> C<SPAN class="keyword">.</SPAN>1 <SPAN class="keyword">*</SPAN> C<SPAN class="keyword">.</SPAN>2 <SPAN class="keyword">*</SPAN> C<SPAN class="keyword">.</SPAN>3 <SPAN class="keyword">=:</SPAN> C<SPAN class="keyword">.</SPAN>8 <SPAN class="keyword">+</SPAN> C<SPAN class="keyword">.</SPAN>9<BR> C<SPAN class="keyword">.</SPAN>2 <SPAN class="keyword">+</SPAN> C<SPAN class="keyword">.</SPAN>3 <SPAN class="keyword">+</SPAN> C<SPAN class="keyword">.</SPAN>6 <SPAN class="keyword"><:</SPAN> C<SPAN class="keyword">.</SPAN>8<BR> C<SPAN class="keyword">.</SPAN>9 <SPAN class="keyword"><:</SPAN> C<SPAN class="keyword">.</SPAN>8<BR> {For 1 9 1 <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> I} C<SPAN class="keyword">.</SPAN>I <SPAN class="keyword">\=:</SPAN> I <SPAN class="keyword">end</SPAN>}<BR> {FD<SPAN class="keyword">.</SPAN>distribute ff C}<BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><DIV class="figure"><P class="caption"><STRONG>Figure 3.5:</STRONG> A script for the Safe Puzzle.</P><HR></DIV><P> </P></DIV><DIV class="unnumbered"><H3><A name="label54">Script</A></H3><P><A href="node19.html#progsafe">Figure 3.5</A> shows a script for the Safe Puzzle. The statement </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>tuple code 9 1<SPAN class="keyword">#</SPAN>9 C}</CODE></BLOCKQUOTE><P> constrains the root variable <CODE>C</CODE> to a tuple with label <CODE>code</CODE> whose components are integers in the domain <CODE>1<SPAN class="keyword">#</SPAN>9</CODE>. The statement </P><BLOCKQUOTE class="code"><CODE>{For 1 9 1 <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> I} C<SPAN class="keyword">.</SPAN>I <SPAN class="keyword">\=:</SPAN> I <SPAN class="keyword">end</SPAN>}</CODE></BLOCKQUOTE><P> posts the constraint <IMG alt="c.i\neq i" src="latex104.png"> for every <IMG alt="i=1,\ldots,9" src="latex105.png">. </P><P>The full search tree of <CODE>Safe</CODE> has 23 nodes and contains the unique solution: </P><BLOCKQUOTE class="code"><CODE>code(4 3 1 8 9 2 6 7 5)</CODE></BLOCKQUOTE><P></P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node18.html#section.problem.watching"><< Prev</A></TD><TD><A href="node13.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 (20090610)</SPAN></ADDRESS></BODY></HTML>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
bd5c3d824c3db63ffd9226c15941e6ad
>
files
>
1191
