<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>7.3 Example: Magic Squares</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="node32.html#section.propagators.pythagoras"><< Prev</A></TD><TD><A href="node30.html">- Up -</A></TD><TD><A href="node34.html#section.propagators.exercises">Next >></A></TD></TR></TABLE><DIV id="section.propagators.squares"><H2><A name="section.propagators.squares">7.3 Example: Magic Squares</A></H2><P>This example shows a smart representation of a matrix and a concomitant defined constraint of higher order. The model will eliminate symmetries by imposing order constraints. Propagation will be drastically improved by exploiting a redundant constraint. </P><DIV class="unnumbered"><H3><A name="label96">Problem Specification</A></H3><P>The Magic Square Puzzle consists in finding for given <IMG alt="N" src="latex4.png"> an <IMG alt="N\times N" src="latex113.png">-matrix such that: </P><UL><LI><P>Every field of the matrix is an integer between 1 and <IMG alt="N^2" src="latex150.png">.</P></LI><LI><P>The fields of the matrix are pairwise distinct.</P></LI><LI><P>The sums of the rows, columns, and the two main diagonals are all equal.</P></LI></UL><P> A magic square for <IMG alt="N=3" src="latex151.png"> looks as follows: </P><BLOCKQUOTE><P><IMG alt="\begin{array}{ccc}
2&7&6\\
9&5&1\\
4&3&8
\end{array}" src="latex152.png"></P></BLOCKQUOTE><P> p> The Magic Square Puzzle is extremely hard for large <IMG alt="N" src="latex4.png">. Even for <IMG alt="{N=5}" src="latex153.png">, our script will have to explore almost 8000 nodes to find a solution. </P></DIV><DIV class="unnumbered"><H3><A name="label97">Model</A></H3><P>We model the problem by having a variable <IMG alt="F_{ij}" src="latex154.png"> for every field <IMG alt="(i,j)" src="latex155.png"> of the matrix. Moreover, we have one additional variable <IMG alt="S" src="latex7.png"> and require that the sum of every row, column, and main diagonal equals <IMG alt="S" src="latex7.png">.</P><P>Without loss of generality, we can impose the following order constraints eliminating symmetries: </P><BLOCKQUOTE><P><IMG alt="F_{11}<F_{NN},
\qquad
F_{N1}<F_{1N},
\qquad
F_{11}<F_{N1}." src="latex156.png"></P></BLOCKQUOTE><P></P><P>Since the sum of the sums of the rows must equal the sum of all fields, we have the redundant constraint </P><BLOCKQUOTE><P><IMG alt="{N^2\over 2}\cdot(N^2+1) = N\cdot S" src="latex157.png"></P></BLOCKQUOTE><P> To see this, note that sum of all fields equals </P><BLOCKQUOTE><P><IMG alt="1+2+\ldots+N^2 = {N^2\over 2}\cdot(N^2+1)" src="latex158.png"></P></BLOCKQUOTE><P></P><P>and that the sum of each of the <IMG alt="N" src="latex4.png"> rows must be <IMG alt="S" src="latex7.png">. </P></DIV><DIV class="unnumbered"><H3><A name="label98">Distribution Strategy</A></H3><P>We distribute on the variables <IMG alt="F_{11},\ldots,
F_{NN}" src="latex159.png"> with a first-fail strategy splitting the domain of the selected variable and trying the lower half first. </P><DIV class="figure" id="progmagicsquare"><HR><P><A name="progmagicsquare"></A></P></DIV><DL class="anonymous"><DD class="code"><CODE><SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">MagicSquare</SPAN> N}<BR> NN = N<SPAN class="keyword">*</SPAN>N<BR> L1N = {List<SPAN class="keyword">.</SPAN>number 1 N 1} % <SPAN class="comment">[1 2 3 ... N]<BR></SPAN><SPAN class="keyword">in</SPAN> <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> Square}<BR> <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Field</SPAN> I J}<BR> Square<SPAN class="keyword">.</SPAN>((I<SPAN class="keyword">-</SPAN>1)<SPAN class="keyword">*</SPAN>N <SPAN class="keyword">+</SPAN> J)<BR> <SPAN class="keyword">end</SPAN> <BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">Assert</SPAN> F}<BR> % <SPAN class="comment">{F 1} + {F 2} + ... + {F N} =: Sum<BR></SPAN> {FD<SPAN class="keyword">.</SPAN>sum {Map L1N F} <SPAN class="string">'=:'</SPAN> Sum}<BR> <SPAN class="keyword">end</SPAN> <BR> Sum = {FD<SPAN class="keyword">.</SPAN>decl}<BR> <SPAN class="keyword">in</SPAN> <BR> {FD<SPAN class="keyword">.</SPAN>tuple square NN 1<SPAN class="keyword">#</SPAN>NN Square}<BR> {FD<SPAN class="keyword">.</SPAN>distinct Square}<BR> %% <SPAN class="comment">Diagonals<BR></SPAN> {Assert <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> I} {Field I I} <SPAN class="keyword">end</SPAN>}<BR> {Assert <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> I} {Field I N<SPAN class="keyword">+</SPAN>1<SPAN class="keyword">-</SPAN>I} <SPAN class="keyword">end</SPAN>}<BR> %% <SPAN class="comment">Columns<BR></SPAN> {For 1 N 1<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> I} {Assert <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> J} {Field I J} <SPAN class="keyword">end</SPAN>} <SPAN class="keyword">end</SPAN>}<BR> %% <SPAN class="comment">Rows<BR></SPAN> {For 1 N 1<BR> <SPAN class="keyword">proc</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> J} {Assert <SPAN class="keyword">fun</SPAN><SPAN class="variablename"> </SPAN>{<SPAN class="functionname">$</SPAN> I} {Field I J} <SPAN class="keyword">end</SPAN>} <SPAN class="keyword">end</SPAN>}<BR> %% <SPAN class="comment">Eliminate symmetries<BR></SPAN> {Field 1 1} <SPAN class="keyword"><:</SPAN> {Field N N}<BR> {Field N 1} <SPAN class="keyword"><:</SPAN> {Field 1 N}<BR> {Field 1 1} <SPAN class="keyword"><:</SPAN> {Field N 1}<BR> %% <SPAN class="comment">Redundant: sum of all fields = (number rows) * Sum<BR></SPAN> NN<SPAN class="keyword">*</SPAN>(NN<SPAN class="keyword">+</SPAN>1) <SPAN class="keyword">div</SPAN> 2 <SPAN class="keyword">=:</SPAN> N<SPAN class="keyword">*</SPAN>Sum<BR> %%<SPAN class="comment"> <BR></SPAN> {FD<SPAN class="keyword">.</SPAN>distribute split Square}<BR> <SPAN class="keyword">end</SPAN> <BR><SPAN class="keyword">end</SPAN></CODE></DD></DL><DIV class="figure"><P class="caption"><STRONG>Figure 7.3:</STRONG> A script for the Magic Square Puzzle.</P><HR></DIV><P> </P></DIV><DIV class="unnumbered"><H3><A name="label99">Script</A></H3><P><A href="node33.html#progmagicsquare">Figure 7.3</A> shows a script realizing the model and distribution strategy just discussed. The actual script is created by a procedure <CODE>MagicSquare</CODE> taking <CODE>N</CODE> as parameter.</P><P>The script represents the matrix as a tuple with <IMG alt="N^2" src="latex150.png"> elements. The tuple is the value of the root variable <CODE>Square</CODE>. The function </P><BLOCKQUOTE class="code"><CODE>{Field I J}</CODE></BLOCKQUOTE><P> returns the component of <CODE>Square</CODE> that represents the field at position <CODE>(I<SPAN class="keyword">,</SPAN>J)</CODE>. The variable <CODE>Sum</CODE> takes the sum of the rows, columns, and main diagonals as value. The procedure </P><BLOCKQUOTE class="code"><CODE>{Assert </CODE><I>F</I><CODE>}</CODE></BLOCKQUOTE><P> takes a function <I>F</I> and posts the constraint </P><BLOCKQUOTE class="code"><CODE>{</CODE><I>F</I><CODE> 1} <SPAN class="keyword">+</SPAN> {</CODE><I>F</I><CODE> 2} <SPAN class="keyword">+</SPAN> <SPAN class="keyword">...</SPAN> <SPAN class="keyword">+</SPAN> {</CODE><I>F</I><CODE> N} = Sum</CODE></BLOCKQUOTE><P> Obviously, <CODE>{Assert F}</CODE> is a defined constraint of higher order. With the help of this defined constraint it is straightforward to state that the sums of the rows, columns, and main diagonals are all equal to <CODE>Sum</CODE>. </P><P>With the Explorer you can find out that for <CODE>N=3</CODE> there is exactly one magic square satisfying the ordering constraints of our model. Without the ordering constraints there are 8 different solutions. Omitting the propagator for the redundant constraint will increase the search tree by an order of magnitude.</P><P></P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="node32.html#section.propagators.pythagoras"><< Prev</A></TD><TD><A href="node30.html">- Up -</A></TD><TD><A href="node34.html#section.propagators.exercises">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
>
1207
