<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>7.4 Exercises</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="node33.html#section.propagators.squares"><< Prev</A></TD><TD><A href="node30.html">- Up -</A></TD></TR></TABLE><DIV id="section.propagators.exercises"><H2><A name="section.propagators.exercises">7.4 Exercises</A></H2><DIV class="exercise" id="propagators.ex.a"><P><B>Exercise 7.1</B> (<A href="answers.html#label189">See solution</A>)</P><BLOCKQUOTE><P></P><DIV class="apropos"><P class="margin">Magic Sequence</P><P> A magic sequence of length <IMG alt="n" src="latex43.png"> is a sequence </P><BLOCKQUOTE><P><IMG alt="x_0,\;x_1,\;\ldots\;,\;x_{n-1}" src="latex160.png"></P></BLOCKQUOTE><P> of integers such that for every <IMG alt="i=0,\ldots,n-1" src="latex161.png"> </P><UL><LI><P><IMG alt="x_i" src="latex162.png"> is an integer between 0 and <IMG alt="n-1" src="latex163.png">.</P></LI><LI><P>the number <IMG alt="i" src="latex115.png"> occurs exactly <IMG alt="x_i" src="latex162.png"> times in the sequence.</P></LI></UL><P> </P></DIV><P>Write a parameterized script that, given <IMG alt="n" src="latex43.png">, can enumerate all magic sequences of length <IMG alt="n" src="latex43.png">. </P><P> The script should use the procedure </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>exactly </CODE><I>K</I><CODE> </CODE><I>S</I><CODE> </CODE><I>I</I><CODE>}</CODE></BLOCKQUOTE><P> that creates a propagator for the constraint saying that exactly <I>K</I> fields of the record <I>S</I> are equal to the integer <I>I</I>. </P><P>You can drastically reduce the search space of the script by having propagators for the redundant constraints </P><BLOCKQUOTE><P><IMG alt="x_0\;+\;\ldots\;+\;x_{n-1}\;=\;n" src="latex164.png"></P></BLOCKQUOTE><P> and </P><BLOCKQUOTE><P><IMG alt="(-1)\cdot x_0\;+\;\ldots\;+\;(n-2)\cdot
x_{n-1}\;=\;0" src="latex165.png"></P></BLOCKQUOTE><P> Explain why these constraints are redundant.</P></BLOCKQUOTE></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node33.html#section.propagators.squares"><< Prev</A></TD><TD><A href="node30.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
>
1208
