1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/exercises/solutions/sol04.tex Thu May 31 01:17:45 2012 +0200
1.3 @@ -0,0 +1,170 @@
1.4 +\documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
1.5 +\usepackage{graphicx}
1.6 +%\usepackage[latin1]{inputenc}
1.7 +\usepackage{amsmath, amsthm, amssymb}
1.8 +\usepackage{typearea}
1.9 +\usepackage{algorithm}
1.10 +\usepackage{algorithmic}
1.11 +\usepackage{fullpage}
1.12 +\usepackage{mathtools}
1.13 +\usepackage[all]{xy}
1.14 +\usepackage{tikz}
1.15 +\usepackage{tikz-qtree}
1.16 +\usetikzlibrary{decorations.pathmorphing} % noisy shapes
1.17 +\usetikzlibrary{fit} % fitting shapes to coordinates
1.18 +\usetikzlibrary{backgrounds} % drawin
1.19 +\usetikzlibrary{shapes,snakes}
1.20 +\addtolength{\voffset}{-20pt}
1.21 +\title{CSP Exercise 04 Solution}
1.22 +\author{Eugen Sawin}
1.23 +\renewcommand{\familydefault}{\sfdefault}
1.24 +\newcommand{\R}{\mathcal{R}}
1.25 +\newcommand{\N}{\mathbb{N}}
1.26 +
1.27 +%\include{pythonlisting}
1.28 +
1.29 +\pagestyle{empty}
1.30 +\begin{document}
1.31 +\maketitle
1.32 +
1.33 +\section*{Exercise 4.1}
1.34 +(a) The zebra problem is the constraint network $N=\langle V,D,C\rangle$ with
1.35 +\begin{align*}
1.36 + V=&(english,spanish,ukrainian,norwegian,japanese,\\
1.37 + &red,green,ivory,yellow,blue\\
1.38 + &dog,snail,fox,horse,zebra\\
1.39 + &coffee,tea,milk,juice,water\\
1.40 + &oldgold,kools,chesterfield,lucky,parliament)\\
1.41 + D=&(D_v)_{v\in V}\text{ where } D_v=\left\{\begin{array}{l l}
1.42 + \{1\} & v = norwegian\\
1.43 + \{3\} & v = milk\\
1.44 + \{1, 2, 3, 4, 5\} & otherwise\\
1.45 + \end{array} \right.\\
1.46 + R_{eq}=&\{(a,a)\mid a\in \N\}\\
1.47 + R_{next}=&\{(a,b)\mid a,b\in\N, |a-b| = 1\}\\
1.48 + R_{rightof}=&\{(a+1,a)\mid a\in \N\}\\
1.49 + C=&\{R_{v_1, v_2\in\{english,spanish,ukrainian,norwegian,japanese\}}=(D_{v_1}\times D_{v_j})\setminus R_{eq},\\
1.50 + &R_{v_1, v_2\in\{red,green,ivory,yellow,blue\}}=(D_{v_1}\times D_{v_j})\setminus R_{eq},\\
1.51 + &R_{v_1, v_2\in\{dog,snail,fox,horse,zebra\}}=(D_{v_1}\times D_{v_j})\setminus R_{eq},\\
1.52 + &R_{v_1, v_2\in\{coffee,tea,milk,juice,water\}}=(D_{v_1}\times D_{v_j})\setminus R_{eq},\\
1.53 + &R_{v_1, v_2\in\{oldgold,kools,chesterfield,lucky,parliament\}}=(D_{v_1}\times D_{v_j})\setminus R_{eq},\\
1.54 + &R_{english, red}=(D_{english}\times D_{red}) \cap R_{eq},\\
1.55 + &R_{spanish, dog}=(D_{spanish}\times D_{dog}) \cap R_{eq},\\
1.56 + &R_{coffee, green}=(D_{coffee}\times D_{green}) \cap R_{eq},\\
1.57 + &R_{ukrainian, tea}=(D_{ukrainian}\times D_{tea}) \cap R_{eq},\\
1.58 + &R_{oldgold, snail}=(D_{oldgold}\times D_{snail}) \cap R_{eq},\\
1.59 + &R_{kool, yellow}=(D_{kool}\times D_{yellow}) \cap R_{eq},\\
1.60 + &R_{lucky, juice}=(D_{lucky}\times D_{juice}) \cap R_{eq},\\
1.61 + &R_{japanese, parliament}=(D_{japanese}\times D_{parliament}) \cap R_{eq},\\
1.62 + &R_{chesterfield, fox}=(D_{chesterfield}\times D_{fox}) \cap R_{next},\\
1.63 + &R_{yellow, horse}=(D_{yellow}\times D_{horse}) \cap R_{next},\\
1.64 + &R_{norwegian, blue}=(D_{norwegian}\times D_{blue}) \cap R_{next},\\
1.65 + &R_{green, ivory}=(D_{green}\times D_{ivory}) \cap R_{rightof}\}
1.66 +\end{align*}
1.67 +To answer the questions, the Norwegian drinks water and the Japanese owns the zebra. I have added the corresponding problem file in XCSP2.1 format to my project repository \emph{(xcsp2\_examples/zebra.xml)}.\\\\
1.68 +(b) See figure 1 (names are abbreviated).
1.69 +\begin{figure}[h]
1.70 +\centering
1.71 +\tikzstyle{var}=[circle,
1.72 + draw=black!100,
1.73 + fill=black!0]
1.74 +\begin{tikzpicture}[>=latex,text height=1.5ex,text depth=0.25ex]
1.75 + \matrix[row sep=1.1cm,column sep=0.7cm] {
1.76 + \node(eng)[var]{$eng$}; &\node(spa)[var]{$spa$}; &\node(ukr)[var]{$ukr$}; &\node(nor)[var]{$nor$}; &\node(jap)[var]{$jap$};\\
1.77 + \node(red)[var]{$red$}; &\node(gre)[var]{$gre$}; &\node(ivo)[var]{$ivo$}; &\node(yel)[var]{$yel$}; &\node(blu)[var]{$blu$};\\
1.78 + \node(dog)[var]{$dog$}; &\node(sna)[var]{$sna$}; &\node(fox)[var]{$fox$}; &\node(hor)[var]{$hor$}; &\node(zeb)[var]{$zeb$};\\
1.79 + \node(cof)[var]{$cof$}; &\node(tea)[var]{$tea$}; &\node(mil)[var]{$mil$}; &\node(jui)[var]{$jui$}; &\node(wat)[var]{$wat$};\\
1.80 + \node(old)[var]{$old$}; &\node(koo)[var]{$koo$}; &\node(che)[var]{$che$}; &\node(luc)[var]{$luc$}; &\node(par)[var]{$par$};\\
1.81 + };
1.82 + \path[-]
1.83 + (eng) edge (red)
1.84 + (spa) edge[bend right=60] (dog)
1.85 + (cof) edge (gre)
1.86 + (ukr) edge (tea)
1.87 + (old) edge (sna)
1.88 + (koo) edge (yel)
1.89 + (luc) edge (jui)
1.90 + (jap) edge[bend left] (par)
1.91 + (che) edge[bend left] (fox)
1.92 + (yel) edge (hor)
1.93 + (nor) edge (blu)
1.94 + (gre) edge (ivo)
1.95 +
1.96 + (eng) edge (spa)
1.97 + (eng) edge[bend left] (ukr)
1.98 + (eng) edge[bend left] (nor)
1.99 + (eng) edge[bend left] (jap)
1.100 + (spa) edge (ukr)
1.101 + (spa) edge[bend right] (nor)
1.102 + (spa) edge[bend right] (jap)
1.103 + (ukr) edge (nor)
1.104 + (ukr) edge[bend left] (jap)
1.105 + (nor) edge (jap)
1.106 +
1.107 + (red) edge (gre)
1.108 + (red) edge[bend left] (ivo)
1.109 + (red) edge[bend left] (yel)
1.110 + (red) edge[bend left] (blu)
1.111 + (gre) edge (ivo)
1.112 + (gre) edge[bend right] (yel)
1.113 + (gre) edge[bend right] (blu)
1.114 + (ivo) edge (yel)
1.115 + (ivo) edge[bend left] (blu)
1.116 + (yel) edge (blu)
1.117 +
1.118 + (dog) edge (sna)
1.119 + (dog) edge[bend left] (fox)
1.120 + (dog) edge[bend left] (hor)
1.121 + (dog) edge[bend left] (zeb)
1.122 + (sna) edge (fox)
1.123 + (sna) edge[bend right] (hor)
1.124 + (sna) edge[bend right] (zeb)
1.125 + (fox) edge (hor)
1.126 + (fox) edge[bend left] (zeb)
1.127 + (hor) edge (zeb)
1.128 +
1.129 + (cof) edge (tea)
1.130 + (cof) edge[bend left] (mil)
1.131 + (cof) edge[bend left] (jui)
1.132 + (cof) edge[bend left] (wat)
1.133 + (tea) edge (mil)
1.134 + (tea) edge[bend right] (jui)
1.135 + (tea) edge[bend right] (wat)
1.136 + (mil) edge (jui)
1.137 + (mil) edge[bend left] (wat)
1.138 + (jui) edge (wat)
1.139 +
1.140 + (old) edge (koo)
1.141 + (old) edge[bend left] (che)
1.142 + (old) edge[bend left] (luc)
1.143 + (old) edge[bend left] (par)
1.144 + (koo) edge (che)
1.145 + (koo) edge[bend right] (luc)
1.146 + (koo) edge[bend right] (par)
1.147 + (che) edge (luc)
1.148 + (che) edge[bend left] (par)
1.149 + (luc) edge (par)
1.150 + ;
1.151 +\end{tikzpicture}
1.152 +\caption{(3.1b) primal constraint graph of $N$}
1.153 +\end{figure}\\
1.154 +(c) No, $N$ is not arc-consistent. We provide the arc-consistent constraint network $N^c=\langle V, D^c, C\rangle$ with
1.155 +\begin{align*}
1.156 + D^c_{v}=\left\{
1.157 + \begin{array}{l l}
1.158 + \{1\} & v = norwegian\\
1.159 + \{3\} & v = milk\\
1.160 + \{2\} & v = blue\\
1.161 + \{3,4\} & v = ivory\\
1.162 + \{4,5\} & v \in \{coffee,green\}\\
1.163 + \{2,3,4\} & v = horse\\
1.164 + \{3,4,5\} & v \in \{english,red\}\\
1.165 + \{2,4,5\} & v \in \{ukrainian,tea\}\\
1.166 + \{2,3,4,5\} & v \in \{spanish,japanese,dog,parliament\}\\
1.167 + \{1,2,4,5\} & v \in \{juice,water,lucky\}\\
1.168 + \{1,3,4,5\} & v \in \{yellow,kool\}\\
1.169 + \{1, 2, 3, 4, 5\} & otherwise\\
1.170 + \end{array} \right.\\
1.171 +\end{align*}
1.172 +That makes 32 domain values less and one hour less of my life. My solver spent full 1.5ms on this task. I'm glad we have the power to build machines for doing such tedious work instead of doing it by hand.
1.173 +\end{document}