<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>3.2 Example: Send More Money</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="node14.html#section.problem.script"><< Prev</A></TD><TD><A href="node13.html">- Up -</A></TD><TD><A href="node16.html#section.problem.explorer">Next >></A></TD></TR></TABLE><DIV id="section.problem.money"><H2><A name="section.problem.money">3.2 Example: Send More Money</A></H2><P> We will now write a script for the Send More Money Puzzle. </P><DIV class="unnumbered"><H3><A name="label42">Problem Specification</A></H3><P>The Send More Money Problem consists in finding distinct digits for the letters <IMG alt="D" src="latex1.png">, <IMG alt="E" src="latex2.png">, <IMG alt="M" src="latex3.png">, <IMG alt="N" src="latex4.png">, <IMG alt="O" src="latex5.png">, <IMG alt="R" src="latex6.png">, <IMG alt="S" src="latex7.png">, <IMG alt="Y" src="latex8.png"> such that <IMG alt="S" src="latex7.png"> and <IMG alt="M" src="latex3.png"> are different from zero (no leading zeros) and the equation </P><BLOCKQUOTE><P><IMG alt="SEND\;+\;MORE\;=\;MONEY" src="latex9.png"></P></BLOCKQUOTE><P> is satisfied. The unique solution of the problem is <IMG alt="9567+1085=10652" src="latex10.png">. </P></DIV><DIV class="unnumbered"><H3><A name="label43">Model</A></H3><P>We model the problem by having a variable for every letter, where the variable stands for the digit associated with the letter. The constraints are obvious from the problem specification. </P></DIV><DIV class="unnumbered"><H3><A name="label44">Distribution Strategy</A></H3><P>We distribute on the variables for the letters with a first-fail strategy. The variables are ordered according to the alphabetic order of the letters. The strategy tries the least possible value of the selected variable. </P><DIV class="figure" id="progmoney"><HR><P><A name="progmoney"></A></P></DIV><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Money</SPAN> Root}<BR> S E N D M O R Y<BR><SPAN class="keyword">in</SPAN> <BR> Root = sol(s:S e:E n:N d:D m:M o:O r:R y:Y) % <SPAN class="comment">1<BR></SPAN> Root <SPAN class="keyword">:::</SPAN> 0<SPAN class="keyword">#</SPAN>9 % <SPAN class="comment">2<BR></SPAN> {FD<SPAN class="keyword">.</SPAN>distinct Root} % <SPAN class="comment">3<BR></SPAN> S <SPAN class="keyword">\=:</SPAN> 0 % <SPAN class="comment">4<BR></SPAN> M <SPAN class="keyword">\=:</SPAN> 0<BR> 1000<SPAN class="keyword">*</SPAN>S <SPAN class="keyword">+</SPAN> 100<SPAN class="keyword">*</SPAN>E <SPAN class="keyword">+</SPAN> 10<SPAN class="keyword">*</SPAN>N <SPAN class="keyword">+</SPAN> D % <SPAN class="comment">5<BR></SPAN> <SPAN class="keyword">+</SPAN> 1000<SPAN class="keyword">*</SPAN>M <SPAN class="keyword">+</SPAN> 100<SPAN class="keyword">*</SPAN>O <SPAN class="keyword">+</SPAN> 10<SPAN class="keyword">*</SPAN>R <SPAN class="keyword">+</SPAN> E<BR> <SPAN class="keyword">=:</SPAN> 10000<SPAN class="keyword">*</SPAN>M <SPAN class="keyword">+</SPAN> 1000<SPAN class="keyword">*</SPAN>O <SPAN class="keyword">+</SPAN> 100<SPAN class="keyword">*</SPAN>N <SPAN class="keyword">+</SPAN> 10<SPAN class="keyword">*</SPAN>E <SPAN class="keyword">+</SPAN> Y<BR> {FD<SPAN class="keyword">.</SPAN>distribute ff Root}<BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><DIV class="figure"><P class="caption"><STRONG>Figure 3.1:</STRONG> A script for the Send More Money Puzzle.</P><HR></DIV><P> </P></DIV><DIV class="unnumbered"><H3><A name="label45">Script</A></H3><P><A href="node15.html#progmoney">Figure 3.1</A> shows a script realizing the model and distribution strategy just discussed. The script first declares a local variable for every letter. Then it posts the following constraints: </P><OL type="1"><LI><P><CODE>Root</CODE> is a record that has a field for every letter. The fields of <CODE>Root</CODE> are the digits for the corresponding letters. This constraint is basic.</P></LI><LI><P>The fields of <CODE>Root</CODE> are integers in the domain <CODE>0<SPAN class="keyword">#</SPAN>9</CODE>. This constraint is basic.</P></LI><LI><P>The fields of <CODE>Root</CODE> are pairwise distinct. This constraint is nonbasic.</P></LI><LI><P>The values of the variables <CODE>S</CODE> and <CODE>M</CODE> are different from zero (no leading zeros). These constraints are nonbasic.</P></LI><LI><P>The digits for the letters satisfy the equation <CODE>SEND<SPAN class="keyword">+</SPAN>MORE=MONEY</CODE>. This constraint is nonbasic.</P></LI></OL><P> </P></DIV><DIV class="unnumbered"><H3><A name="label46">Posting of constraints</A></H3><P><A name="label47"></A><EM>posting of constraints</EM> is defined differently for basic and nonbasic constraints. Basic constraints are posted by telling them to the constraint store. Nonbasic constraints are posted by creating propagators implementing them. </P><P>Note that the propagators for <CODE>S<SPAN class="keyword">\=:</SPAN>0</CODE> and <CODE>M<SPAN class="keyword">\=:</SPAN>0</CODE> can immediately write their complete information into the constraint store since the store already knows domains for <CODE>S</CODE> and <CODE>M</CODE>. </P><P>The last line <CODE>{FD<SPAN class="keyword">.</SPAN>distribute ff Root}</CODE> posts a distributor that will distribute on the field of <CODE>Root</CODE> with the first-fail strategy (specified by the atom <CODE>ff</CODE>). Equivalently, we could write </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>distribute ff [D E M N O R S Y]}</CODE></BLOCKQUOTE><P> and thus specify the variables and their order explicitly. The order of the fields of <I>Root</I> is given by the canonical ordering of the respective features <CODE>d</CODE>, <CODE>e</CODE>, <CODE>m</CODE>, <CODE>n</CODE>, <CODE>o</CODE>, <CODE>r</CODE>, <CODE>s</CODE>, and <CODE>y</CODE>. </P><P>The statement </P><DL class="anonymous"><DD class="code"><CODE>{Browse {SearchAll Money}}</CODE></DD></DL><P> will compute and display the list of all solutions of the Send More Money Puzzle: </P><BLOCKQUOTE class="code"><CODE>[sol(d:7 e:5 m:1 n:6 o:0 r:8 s:9 y:2)]</CODE></BLOCKQUOTE><P> </P><P>To understand the search process defined by <CODE>Money</CODE>, we need more information than just the list of solutions found. Obviously, it would be useful to see a graphical representation of the search tree. It would also be nice if we could see for every node of the search tree what information about the solution was accumulated in the constraint store when the respective space became stable. Finally, it would be nice to see for every arc of the tree with which constraint it was distributed. </P><P><A href="node15.html#figconmoneytree">Figure 3.2</A> shows the search tree explored by <CODE>Money</CODE> together with the information just mentioned. This gives us a good understanding of the search process defined by <CODE>Money</CODE>. Note that the search tree is quite small compared to the <IMG alt="10^8" src="latex96.png"> candidates a naive generate and test method would have to consider.</P><P> </P><DIV id="figconmoneytree"><HR><P><A name="figconmoneytree"></A></P><DIV align="center"><IMG alt="" src="latex97.png"></DIV><P class="caption"><STRONG>Figure 3.2:</STRONG> The search tree explored by <CODE>Money</CODE>.</P><HR></DIV><P></P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node14.html#section.problem.script"><< Prev</A></TD><TD><A href="node13.html">- Up -</A></TD><TD><A href="node16.html#section.problem.explorer">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 (20090610)</SPAN></ADDRESS></BODY></HTML>
distrib
>
Mandriva
>
2010.0
>
i586
>
media
>
contrib-release
>
by-pkgid
>
bd5c3d824c3db63ffd9226c15941e6ad
>
files
>
1187
