/usr/share/mozart/doc/fdt/node1.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 | <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<HTML><HEAD><TITLE>1 Introduction</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="toc.html#label1"><< Prev</A></TD><TD><A href="index.html">- Up -</A></TD><TD><A href="node2.html#chapter.constraints">Next >></A></TD></TR></TABLE><DIV id="chapter.intro"><H1><A name="chapter.intro">1 Introduction</A></H1><P>This document is a first introduction to constraint-based problem solving and its implementation in Oz. We restrict our attention to combinatorial problems that can be stated with variables ranging over finite sets of nonnegative integers. Problems in this class range from puzzles to real world applications as diverse as scheduling, ware house allocation, configuration and placement. </P><P>The two basic techniques of constraint programming are constraint propagation and constraint distribution. Constraint propagation is an efficient inference mechanism obtained with concurrent propagators accumulating information in a constraint store. Constraint distribution splits a problem into complementary cases once constraint propagation cannot advance further. By iterating propagation and distribution, propagation will eventually determine the solutions of a problem. </P><P>Constraint distribution can easily lead to an exponential growth of the number of subproblems to be considered. Fortunately, this potential combinatorial explosion can often be contained by combining strong propagation mechanisms with problem specific heuristics for selecting distribution steps. </P><P>The following puzzles give a first idea of the combinatorial problems we will solve in this document: </P><DIV class="unnumbered"><H2><A name="label2">Money</A></H2><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"><H2><A name="label3">Safe</A></H2><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}{c}
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\neq 1,\ldots, C_9\neq 9
\end{array}" src="latex12.png"></P></BLOCKQUOTE><P> Can you determine the code? </P></DIV><DIV class="unnumbered"><H2><A name="label4">Coloring</A></H2><P>Given a map showing the West European countries Netherlands, Belgium, France, Spain, Portugal, Germany, Luxemburg, Switzerland, Austria, and Italy, find a coloring such that neighboring countries have different color and a minimal number of colors is used. </P></DIV><DIV class="unnumbered"><H2><A name="label5">Grocery</A></H2><P>A kid goes into a grocery store and buys four items. The cashier charges $7.11, the kid pays and is about to leave when the cashier calls the kid back, and says ``Hold on, I multiplied the four items instead of adding them; I'll try again; Hah, with adding them the price still comes to $7.11''. What were the prices of the four items? </P></DIV><DIV class="unnumbered"><H2><A name="label6">Queens</A></H2><P>Place 8 queens on a chess board such that no two queens attack each other. </P><P>The problems have in common that they can be stated with variables that are a priori constrained to finite sets of nonnegative integers. Consequently, the problems could be solved by simply checking all possible combinations of the values of the variables. This naive generate and test method is however infeasible for most realistic problems since there are just too many possible combinations. </P></DIV><DIV class="unnumbered"><H2><A name="label7">More Information</A></H2><P>While this tutorial tries to be as self-contained as possible for constraint programming in Oz, it is expected that the reader has already a working knowledge of functional Oz programming. As an introduction for functional and object-oriented programming in Oz we suggest <A href="../tutorial/index.html">``Tutorial of Oz''</A>. The full functionality of Oz provided for constraint programming is included in the document <A href="../system/index.html#part.constraints">Part II of ``System Modules''</A>. </P></DIV><DIV class="unnumbered"><H2><A name="label8">The Examples</A></H2><P>The tutorial features a large number of examples. To ease the understanding the examples should be tried in the <A href="../opi/index.html">Oz Programming Environment (OPI)</A>. The Oz programs are contained in the following <A href="FiniteDomainTutorial.oz">file</A>. Oz programs for some solutions to the exercises are contained in the following <A href="FiniteDomainTutorialSolutions.oz">file</A>. </P></DIV><DIV class="unnumbered"><H2><A name="label9">Acknowledgements</A></H2><P>The tutorial is based on the document ``Finite Domain Constraint Programming in Oz. A Tutorial'' by Gert Smolka, Christian Schulte, and Jörg Würtz for a previous version of Oz. </P></DIV></DIV><TABLE align="center" border="0" cellpadding="6" cellspacing="6" class="nav"><TR bgcolor="#DDDDDD"><TD><A href="toc.html#label1"><< Prev</A></TD><TD><A href="index.html">- Up -</A></TD><TD><A href="node2.html#chapter.constraints">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>
|