/usr/share/mozart/doc/fdt/node25.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 13 14 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>5.1 Example: Queens</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="node24.html">- Up -</A></TD><TD><A href="node26.html#section.scripts.change">Next >></A></TD></TR></TABLE><DIV id="section.scripts.queens"><H2><A name="section.scripts.queens">5.1 Example: Queens</A></H2><DIV class="unnumbered"><H3><A name="label71">Problem Specification</A></H3><P> Place <IMG alt="N" src="latex4.png"> queens on an <IMG alt="N\times N" src="latex113.png"> chess board such that no two queens attack each other. The parameter of the problem is <IMG alt="N" src="latex4.png">. A solution for the 8-queens problem looks as follows: </P><DIV class="figure"><HR></DIV><TABLE align="center" bgcolor="#f0f0e0"><TR valign="top"><TH><P> </P></TH><TH><P>1</P></TH><TH><P>2</P></TH><TH><P>3</P></TH><TH><P>4</P></TH><TH><P>5</P></TH><TH><P>6</P></TH><TH><P>7</P></TH><TH><P>8</P></TH></TR><TR valign="top"><TH><P>1</P></TH><TD><P></P><DIV align="center"><IMG alt="" src="queen.gif" id="pic.q1"></DIV><P></P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD></TR><TR valign="top"><TH><P>2</P></TH><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P></P><DIV align="center"><IMG alt="" src="queen.gif" id="pic.q2"></DIV><P></P></TD><TD><P> </P></TD></TR><TR valign="top"><TH><P>3</P></TH><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P></P><DIV align="center"><IMG alt="" src="queen.gif" id="pic.q3"></DIV><P></P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD></TR><TR valign="top"><TH><P>4</P></TH><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P></P><DIV align="center"><IMG alt="" src="queen.gif" id="pic.q4"></DIV><P></P></TD><TD><P> </P></TD><TD><P> </P></TD></TR><TR valign="top"><TH><P>5</P></TH><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P></P><DIV align="center"><IMG alt="" src="queen.gif" id="pic.q5"></DIV><P></P></TD></TR><TR valign="top"><TH><P>6</P></TH><TD><P> </P></TD><TD><P></P><DIV align="center"><IMG alt="" src="queen.gif" id="pic.q6"></DIV><P></P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD></TR><TR valign="top"><TH><P>7</P></TH><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P></P><DIV align="center"><IMG alt="" src="queen.gif" id="pic.q7"></DIV><P></P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD></TR><TR valign="top"><TH><P>8</P></TH><TD><P> </P></TD><TD><P> </P></TD><TD><P></P><DIV align="center"><IMG alt="" src="queen.gif" id="pic.q8"></DIV><P></P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD><TD><P> </P></TD></TR></TABLE><DIV class="figure"><P class="caption"><STRONG>Figure 5.1.</STRONG></P><HR></DIV><P> </P></DIV><DIV class="unnumbered"><H3><A name="label72">Model</A></H3><P>We will use a clever model avoiding possible symmetries and minimizing the number of propagators. </P><P>We assume that the queens are numbered from 1 to <IMG alt="N" src="latex4.png">, and that the <IMG alt="k" src="latex114.png">-th queen is always placed in the <IMG alt="k" src="latex114.png">-th column. For every queen <IMG alt="i" src="latex115.png"> we have one variable <IMG alt="R_i" src="latex116.png"> saying in which row the queen is placed. The model guarantees by construction that two queens are never placed in the same column. To ensure that two queens are never in the same row, we impose the constraint that the variables <IMG alt="R_1,\ldots,R_N" src="latex117.png"> are pairwise distinct. </P><P>To enforce that two queens are never in the same diagonal, we need to impose the constraints </P><BLOCKQUOTE><P><IMG alt="R_i+(j-i)\neq R_j
\qquad
\hbox{and}
\qquad
R_i-(j-i)\neq R_j" src="latex118.png"></P></BLOCKQUOTE><P> for all <IMG alt="i" src="latex115.png">, <IMG alt="j" src="latex119.png"> such that <IMG alt="1\le i<j\le N" src="latex120.png">. Equivalently, we can impose the constraints </P><BLOCKQUOTE><P><IMG alt="R_i-i\neq R_j-j
\qquad
\hbox{and}
\qquad
R_i+i\neq R_j+j" src="latex121.png"></P></BLOCKQUOTE><P> for all <IMG alt="i" src="latex115.png">, <IMG alt="j" src="latex119.png"> such that <IMG alt="1\le i<j\le N" src="latex120.png">. This is equivalent to saying that the sequences </P><BLOCKQUOTE><P><IMG alt="R_1-1\;,\ldots,\;R_N-N
\qquad
\hbox{and}
\qquad
R_1+1\;,\ldots,\;R_N+N" src="latex122.png"></P></BLOCKQUOTE><P> are both nonrepetitive. Since Oz has a special propagator for the constraint stating the nonrepetitiveness of such sequences, this formulation requires only two propagators, one for each sequence. </P></DIV><DIV class="unnumbered"><H3><A name="label73">Distribution Strategy</A></H3><P>We distribute on the variables <IMG alt="R_1,\ldots,R_N" src="latex117.png"> using a first-fail strategy that tries the value in the middle of the domain of the selected variable first. This strategy works well even for large <I>N</I>. </P><P></P><DIV id="progqueens"><HR><P><A name="progqueens"></A></P><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Queens</SPAN> N}<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Row}<BR> L1N ={MakeTuple c N} <BR> LM1N={MakeTuple c N}<BR> <SPAN class="keyword">in</SPAN> <BR> {FD<SPAN class="keyword">.</SPAN>tuple queens N 1<SPAN class="keyword">#</SPAN>N Row}<BR> {For 1 N 1 <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> I}<BR> L1N<SPAN class="keyword">.</SPAN>I=I LM1N<SPAN class="keyword">.</SPAN>I=<SPAN class="keyword">~</SPAN>I<BR> <SPAN class="keyword">end</SPAN>}<BR> {FD<SPAN class="keyword">.</SPAN>distinct Row}<BR> {FD<SPAN class="keyword">.</SPAN>distinctOffset Row LM1N}<BR> {FD<SPAN class="keyword">.</SPAN>distinctOffset Row L1N}<BR> {FD<SPAN class="keyword">.</SPAN>distribute generic(value:mid) Row}<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><P class="caption"><STRONG>Figure 5.2:</STRONG> A script for the <I>N</I>-queens Problem.</P><HR></DIV><P> </P></DIV><DIV class="unnumbered"><H3><A name="label74">Script</A></H3><P><A href="node25.html#progqueens">Figure 5.2</A> shows a parameterized script for the <I>N</I>-Queens Problem. The actual script is created by the procedure <CODE>Queens</CODE>, which takes <CODE>N</CODE> as parameter. The script constrains its root variable <CODE>Row</CODE> to a tuple having a component for every queen. This implicitly creates the variables <IMG alt="R_1,\ldots,R_N" src="latex117.png"> of the model. </P><P>The statements </P><BLOCKQUOTE class="code"><CODE>{FD<SPAN class="keyword">.</SPAN>distinct Row}<BR>{FD<SPAN class="keyword">.</SPAN>distinctOffset Row LM1N}<BR>{FD<SPAN class="keyword">.</SPAN>distinctOffset Row L1N}</CODE></BLOCKQUOTE><P> create propagators for the constraints stating that the sequences </P><TABLE align="center" bgcolor="#f0f0e0"><TR valign="top"><TD><P><CODE>Row<SPAN class="keyword">.</SPAN>1</CODE></P></TD><TD><P>...</P></TD><TD><P><CODE>Row<SPAN class="keyword">.</SPAN>N</CODE></P></TD></TR><TR valign="top"><TD><P><CODE>Row<SPAN class="keyword">.</SPAN>1<SPAN class="keyword">-</SPAN>1</CODE></P></TD><TD><P>...</P></TD><TD><P><CODE>Row<SPAN class="keyword">.</SPAN>N<SPAN class="keyword">-</SPAN>N</CODE></P></TD></TR><TR valign="top"><TD><P><CODE>Row<SPAN class="keyword">.</SPAN>1<SPAN class="keyword">+</SPAN>1</CODE></P></TD><TD><P>...</P></TD><TD><P><CODE>Row<SPAN class="keyword">.</SPAN>N<SPAN class="keyword">+</SPAN>N</CODE></P></TD></TR></TABLE><P> be non repetitive. </P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node24.html">- Up -</A></TD><TD><A href="node26.html#section.scripts.change">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>
|