cws/cw02.tex
author Christian Urban <urbanc@in.tum.de>
Sat, 26 Nov 2016 17:02:52 +0000
changeset 74 fb2d8012ed08
parent 60 f099bcf9cff1
child 79 2d57b0d43a0f
permissions -rw-r--r--
updated
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
6
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     1
\documentclass{article}
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     2
\usepackage{chessboard}
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     3
\usepackage[LSBC4,T1]{fontenc}
39
c6fe374a5fca updated
Christian Urban <urbanc@in.tum.de>
parents: 38
diff changeset
     4
\usepackage{../style}
6
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     5
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     6
\begin{document}
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     7
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
     8
\setchessboard{smallboard,
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
     9
               zero,
6
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    10
               showmover=false,
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    11
               boardfontencoding=LSBC4,
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    12
               hlabelformat=\arabic{ranklabel},
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    13
               vlabelformat=\arabic{filelabel}}
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    14
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    15
\mbox{}\\[-18mm]\mbox{}
6
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    16
36
f5ed0fef41b3 updated
Christian Urban <urbanc@in.tum.de>
parents: 6
diff changeset
    17
\section*{Coursework 7 (Scala, Knight's Tour)}
6
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    18
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
    19
This coursework is worth 10\%. It is about searching and
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
    20
backtracking. The first part is due on 23 November at 11pm; the
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
    21
second, more advanced part, is due on 30 November at 11pm. You are
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
    22
asked to implement Scala programs that solve various versions of the
42
a5106bc13db6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 39
diff changeset
    23
\textit{Knight's Tour Problem} on a chessboard. Make sure the files
a5106bc13db6 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 39
diff changeset
    24
you submit can be processed by just calling \texttt{scala
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
    25
  <<filename.scala>>}.\bigskip
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
    26
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
    27
\noindent
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
    28
\textbf{Important:} Do not use any mutable data structures in your
74
fb2d8012ed08 updated
Christian Urban <urbanc@in.tum.de>
parents: 60
diff changeset
    29
submissions! They are not needed. This excludes the use of
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
    30
\texttt{ListBuffer}s, for example. Do not use \texttt{return} in your
59
8e866d0af03a updated
Christian Urban <urbanc@in.tum.de>
parents: 50
diff changeset
    31
code! It has a different meaning in Scala, than in Java.
8e866d0af03a updated
Christian Urban <urbanc@in.tum.de>
parents: 50
diff changeset
    32
Do not use \texttt{var}! This declares a mutable variable. Feel free to
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
    33
copy any code you need from files \texttt{knight1.scala},
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
    34
\texttt{knight2.scala} and \texttt{knight3.scala}. Make sure the
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
    35
functions you submit are defined on the ``top-level'' of Scala, not
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
    36
inside a class or object.
39
c6fe374a5fca updated
Christian Urban <urbanc@in.tum.de>
parents: 38
diff changeset
    37
 
c6fe374a5fca updated
Christian Urban <urbanc@in.tum.de>
parents: 38
diff changeset
    38
\subsection*{Disclaimer}
c6fe374a5fca updated
Christian Urban <urbanc@in.tum.de>
parents: 38
diff changeset
    39
c6fe374a5fca updated
Christian Urban <urbanc@in.tum.de>
parents: 38
diff changeset
    40
It should be understood that the work you submit represents
c6fe374a5fca updated
Christian Urban <urbanc@in.tum.de>
parents: 38
diff changeset
    41
your own effort. You have not copied from anyone else. An
c6fe374a5fca updated
Christian Urban <urbanc@in.tum.de>
parents: 38
diff changeset
    42
exception is the Scala code I showed during the lectures or
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    43
uploaded to KEATS, which you can freely use.\medskip
39
c6fe374a5fca updated
Christian Urban <urbanc@in.tum.de>
parents: 38
diff changeset
    44
c6fe374a5fca updated
Christian Urban <urbanc@in.tum.de>
parents: 38
diff changeset
    45
\subsection*{Background}
c6fe374a5fca updated
Christian Urban <urbanc@in.tum.de>
parents: 38
diff changeset
    46
c6fe374a5fca updated
Christian Urban <urbanc@in.tum.de>
parents: 38
diff changeset
    47
The \textit{Knight's Tour Problem} is about finding a tour such that
74
fb2d8012ed08 updated
Christian Urban <urbanc@in.tum.de>
parents: 60
diff changeset
    48
the knight visits every field on an $n\times n$ chessboard once. Such
fb2d8012ed08 updated
Christian Urban <urbanc@in.tum.de>
parents: 60
diff changeset
    49
a tour is called \emph{open} tour. For example on a $5\times 5$
fb2d8012ed08 updated
Christian Urban <urbanc@in.tum.de>
parents: 60
diff changeset
    50
chessboard, an open  knight's tour is:
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    51
39
c6fe374a5fca updated
Christian Urban <urbanc@in.tum.de>
parents: 38
diff changeset
    52
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    53
\chessboard[maxfield=d4, 
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    54
            pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    55
            text = \small 24, markfield=Z4,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    56
            text = \small 11, markfield=a4,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    57
            text = \small  6, markfield=b4,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    58
            text = \small 17, markfield=c4,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    59
            text = \small  0, markfield=d4,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    60
            text = \small 19, markfield=Z3,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    61
            text = \small 16, markfield=a3,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    62
            text = \small 23, markfield=b3,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    63
            text = \small 12, markfield=c3,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    64
            text = \small  7, markfield=d3,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    65
            text = \small 10, markfield=Z2,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    66
            text = \small  5, markfield=a2,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    67
            text = \small 18, markfield=b2,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    68
            text = \small  1, markfield=c2,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    69
            text = \small 22, markfield=d2,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    70
            text = \small 15, markfield=Z1,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    71
            text = \small 20, markfield=a1,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    72
            text = \small  3, markfield=b1,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    73
            text = \small  8, markfield=c1,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    74
            text = \small 13, markfield=d1,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    75
            text = \small  4, markfield=Z0,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    76
            text = \small  9, markfield=a0,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    77
            text = \small 14, markfield=b0,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    78
            text = \small 21, markfield=c0,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    79
            text = \small  2, markfield=d0
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    80
           ]
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    81
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    82
\noindent
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    83
The tour starts in the right-upper corner, then moves to field
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    84
$(3,2)$, then $(4,0)$ and so on. There are no knight's tours on
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    85
$2\times 2$, $3\times 3$ and $4\times 4$ chessboards, but for every
74
fb2d8012ed08 updated
Christian Urban <urbanc@in.tum.de>
parents: 60
diff changeset
    86
bigger board there is. 
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    87
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    88
A knight's tour is called \emph{closed}, if the last step in the tour
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    89
is within a knight's move to the beginning of the tour. So the above
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    90
knight's tour is \underline{not} closed (it is open) because the last
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    91
step on field $(0, 4)$ is not within the reach of the first step on
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    92
$(4, 4)$. It turns out there is no closed knight's tour on a $5\times
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
    93
5$ board. But there are on a $6\times 6$ board and on bigger ones, for
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
    94
example
6
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    95
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    96
\chessboard[maxfield=e5, 
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
    97
            pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    98
            text = \small 10, markfield=Z5,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
    99
            text = \small  5, markfield=a5,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   100
            text = \small 18, markfield=b5,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   101
            text = \small 25, markfield=c5,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   102
            text = \small 16, markfield=d5,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   103
            text = \small  7, markfield=e5,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   104
            text = \small 31, markfield=Z4,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   105
            text = \small 26, markfield=a4,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   106
            text = \small  9, markfield=b4,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   107
            text = \small  6, markfield=c4,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   108
            text = \small 19, markfield=d4,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   109
            text = \small 24, markfield=e4,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   110
            % 4  11  30  17   8  15 
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   111
            text = \small  4, markfield=Z3,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   112
            text = \small 11, markfield=a3,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   113
            text = \small 30, markfield=b3,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   114
            text = \small 17, markfield=c3,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   115
            text = \small  8, markfield=d3,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   116
            text = \small 15, markfield=e3,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   117
            %29  32  27   0  23  20 
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   118
            text = \small 29, markfield=Z2,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   119
            text = \small 32, markfield=a2,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   120
            text = \small 27, markfield=b2,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   121
            text = \small  0, markfield=c2,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   122
            text = \small 23, markfield=d2,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   123
            text = \small 20, markfield=e2,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   124
            %12   3  34  21  14   1 
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   125
            text = \small 12, markfield=Z1,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   126
            text = \small  3, markfield=a1,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   127
            text = \small 34, markfield=b1,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   128
            text = \small 21, markfield=c1,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   129
            text = \small 14, markfield=d1,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   130
            text = \small  1, markfield=e1,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   131
            %33  28  13   2  35  22 
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   132
            text = \small 33, markfield=Z0,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   133
            text = \small 28, markfield=a0,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   134
            text = \small 13, markfield=b0,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   135
            text = \small  2, markfield=c0,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   136
            text = \small 35, markfield=d0,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   137
            text = \small 22, markfield=e0,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   138
            vlabel=false,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   139
            hlabel=false
6
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   140
           ]
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   141
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   142
6
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   143
\noindent
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   144
where the 35th move can join up again with the 0th move.
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   145
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   146
If you cannot remember how a knight moves in chess, or never played
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   147
chess, below are all potential moves indicated for two knights, one on
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   148
field $(2, 2)$ (blue moves) and another on $(7, 7)$ (red moves):
39
c6fe374a5fca updated
Christian Urban <urbanc@in.tum.de>
parents: 38
diff changeset
   149
c6fe374a5fca updated
Christian Urban <urbanc@in.tum.de>
parents: 38
diff changeset
   150
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   151
\chessboard[maxfield=g7,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   152
            color=blue!50,
6
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   153
            linewidth=0.2em,
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   154
            shortenstart=0.5ex,
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   155
            shortenend=0.5ex,
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   156
            markstyle=cross,
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   157
            markfields={a4, c4, Z3, d3, Z1, d1, a0, c0},
6
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   158
            color=red!50,
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   159
            markfields={f5, e6},
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   160
            setpieces={Ng7, Nb2}]
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   161
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   162
\subsection*{Part 1 (7 Marks)}
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   163
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   164
You are asked to implement the knight's tour problem such that the
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   165
dimension of the board can be changed.  Therefore most functions will
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   166
take the dimension of the board as an argument.  The fun with this
60
f099bcf9cff1 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 59
diff changeset
   167
problem is that even for small chessboard dimensions it has already an
f099bcf9cff1 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 59
diff changeset
   168
incredibly large search space---finding a tour is like finding a
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   169
needle in a haystack. In the first task we want to see how far we get
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   170
with exhaustively exploring the complete search space for small
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   171
chessboards.\medskip
6
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   172
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   173
\noindent
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   174
Let us first fix the basic datastructures for the implementation.  The
60
f099bcf9cff1 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 59
diff changeset
   175
board dimension is an integer (we will never go beyond board sizes of
74
fb2d8012ed08 updated
Christian Urban <urbanc@in.tum.de>
parents: 60
diff changeset
   176
$50 \times 50$).  A \emph{position} (or field) on the chessboard is
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   177
a pair of integers, like $(0, 0)$. A \emph{path} is a list of
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   178
positions. The first (or 0th move) in a path is the last element in
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   179
this list; and the last move in the path is the first element. For
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   180
example the path for the $5\times 5$ chessboard above is represented
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   181
by
6
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   182
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   183
\[
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   184
\texttt{List($\underbrace{\texttt{(0, 4)}}_{24}$,
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   185
  $\underbrace{\texttt{(2, 3)}}_{23}$, ...,
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   186
  $\underbrace{\texttt{(3, 2)}}_1$, $\underbrace{\texttt{(4, 4)}}_0$)}
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   187
\]
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   188
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   189
\noindent
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   190
Suppose the dimension of a chessboard is $n$, then a path is a
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   191
\emph{tour} if the length of the path is $n \times n$, each element
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   192
occurs only once in the path, and each move follows the rules of how a
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   193
knight moves (see above for the rules).
6
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   194
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   195
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   196
\subsubsection*{Tasks (file knight1.scala)}
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   197
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   198
\begin{itemize}
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   199
\item[(1a)] Implement an is-legal-move function that takes a
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   200
  dimension, a path and a position as argument and tests whether the
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   201
  position is inside the board and not yet element in the
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   202
  path. \hfill[1 Mark]
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   203
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   204
\item[(1b)] Implement a legal-moves function that calculates for a
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   205
  position all legal onward moves. If the onward moves are
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   206
  placed on a circle, you should produce them starting from
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   207
  ``12-oclock'' following in clockwise order.  For example on an
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   208
  $8\times 8$ board for a knight on position $(2, 2)$ and otherwise
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   209
  empty board, the legal-moves function should produce the onward
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   210
  positions in this order:
6
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   211
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   212
  \begin{center}
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   213
  \texttt{List((3,4), (4,3), (4,1), (3,0), (1,0), (0,1), (0,3), (1,4))}
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   214
  \end{center}
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   215
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   216
  If the board is not empty, then maybe some of the moves need to be
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   217
  filtered out from this list.  For a knight on field $(7, 7)$ and an
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   218
  empty board, the legal moves are
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   219
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   220
  \begin{center}
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   221
  \texttt{List((6,5), (5,6))}
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   222
  \end{center}
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   223
  \mbox{}\hfill[1 Mark]
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   224
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   225
\item[(1c)] Implement two recursive functions (count-tours and
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   226
  enum-tours). They each take a dimension and a path as
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   227
  arguments. They exhaustively search for {\bf open} tours starting
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   228
  from the given path. The first function counts all possible open
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   229
  tours (there can be none for certain board sizes) and the second
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   230
  collects all open tours in a list of paths.\hfill[2 Marks]
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   231
\end{itemize}
6
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   232
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   233
\noindent \textbf{Test data:} For the marking, the functions in (1c)
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   234
will be called with board sizes up to $5 \times 5$. If you search
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   235
for open tours on a $5 \times 5$ board starting only from field $(0, 0)$,
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   236
there are 304 of tours. If you try out every field of a $5 \times
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   237
5$-board as a starting field and add up all open tours, you obtain
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   238
1728. A $6\times 6$ board is already too large to be searched
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   239
exhaustively.\footnote{For your interest, the number of open tours on
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   240
  $6\times 6$, $7\times 7$ and $8\times 8$ are 6637920, 165575218320,
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   241
  19591828170979904, respectively.}
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   242
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   243
\subsubsection*{Tasks (file knight2.scala)}
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   244
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   245
\begin{itemize}
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   246
\item[(2a)] Implement a first-function. This function takes a list of
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   247
  positions and a function $f$ as arguments. The function $f$ takes a
74
fb2d8012ed08 updated
Christian Urban <urbanc@in.tum.de>
parents: 60
diff changeset
   248
  position as argument and produces an optional path. So $f$'s type is
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   249
  \texttt{Pos => Option[Path]}. The idea behind the first-function is
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   250
  as follows:
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   251
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   252
  \[
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   253
  \begin{array}{lcl}
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   254
  \textit{first}(\texttt{Nil}, f) & \dn & \texttt{None}\\  
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   255
  \textit{first}(x\!::\!xs, f) & \dn & \begin{cases}
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   256
    f(x) & \textit{if}\;f(x) \not=\texttt{None}\\
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   257
    \textit{first}(xs, f) & \textit{otherwise}\\
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   258
                              \end{cases}
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   259
  \end{array}
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   260
  \]
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   261
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   262
  \noindent That is, we want to find the first position where the
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   263
  result of $f$ is not \texttt{None}, if there is one.\mbox{}\hfill[1 Mark]
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   264
  
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   265
\item[(2b)] Implement a first-tour function that uses the
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   266
  first-function from (2a), and searches recursively for an open tour.
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   267
  As there might not be such a tour at all, the first-tour function
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   268
  needs to return an \texttt{Option[Path]}.\hfill[2 Marks]
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   269
\end{itemize}
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   270
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   271
\noindent
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   272
\textbf{Testing} The first tour function will be called with board
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   273
sizes of up to $8 \times 8$. 
6
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   274
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   275
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   276
\subsection*{Part 2 (3 Marks)}
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   277
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   278
As you should have seen in Part 1, a naive search for open tours
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   279
beyond $8 \times 8$ boards and also searching for closed tours
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   280
takes too much time. There is a heuristic (called Warnsdorf's rule)
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   281
that can speed up finding a tour. This heuristic states that a knight
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   282
is moved so that it always proceeds to the field from which the
48
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   283
knight will have the \underline{fewest} onward moves.  For example for
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   284
a knight on field $(1, 3)$, the field $(0, 1)$ has the fewest possible
7a6a75ea9738 updated
Christian Urban <urbanc@in.tum.de>
parents: 46
diff changeset
   285
onward moves, namely 2.
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   286
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   287
\chessboard[maxfield=g7,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   288
            pgfstyle= {[base,at={\pgfpoint{0pt}{-0.5ex}}]text},
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   289
            text = \small 3, markfield=Z5,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   290
            text = \small 7, markfield=b5,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   291
            text = \small 7, markfield=c4,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   292
            text = \small 7, markfield=c2,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   293
            text = \small 5, markfield=b1,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   294
            text = \small 2, markfield=Z1,
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   295
            setpieces={Na3}]
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   296
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   297
\noindent
60
f099bcf9cff1 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 59
diff changeset
   298
Warnsdorf's rule states that the moves on the board above should be
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   299
tried in the order
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   300
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   301
\[
46
48d2cbe8ee5e updated
Christian Urban <urbanc@in.tum.de>
parents: 45
diff changeset
   302
(0, 1), (0, 5), (2, 1), (2, 5), (3, 4), (3, 2)
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   303
\]
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   304
46
48d2cbe8ee5e updated
Christian Urban <urbanc@in.tum.de>
parents: 45
diff changeset
   305
\noindent
60
f099bcf9cff1 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 59
diff changeset
   306
Whenever there are ties, the corresponding onward moves can be in any
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   307
order.  When calculating the number of onward moves for each field, we
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   308
do not count moves that revisit any field already visited.
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   309
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   310
\subsubsection*{Tasks (file knight3.scala)}
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   311
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   312
\begin{itemize}
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   313
\item[(3a)] Write a function ordered-moves that calculates a list of
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   314
  onward moves like in (1b) but orders them according to the
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   315
  Warnsdorf’s rule. That means moves with the fewest legal onward moves
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   316
  should come first (in order to be tried out first).
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   317
  
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   318
\item[(3b)] Implement a first-closed-tour-heuristic function that searches for a
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   319
  \textbf{closed} tour on a $6\times 6$ board. It should use the
60
f099bcf9cff1 updated
Christian Urban <christian dot urban at kcl dot ac dot uk>
parents: 59
diff changeset
   320
  first-function from (2a) and tries out onward moves according to
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   321
  the ordered-moves function from (3a). It is more likely to find
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   322
  a solution when started in the middle of the board (that is
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   323
  position $(dimension / 2, dimension / 2)$).
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   324
50
9891c9fac37e updated
Christian Urban <urbanc@in.tum.de>
parents: 48
diff changeset
   325
\item[(3c)] Implement a first-tour-heuristic function for boards up to $50\times 50$.
74
fb2d8012ed08 updated
Christian Urban <urbanc@in.tum.de>
parents: 60
diff changeset
   326
  It is the same function  as in (3b) but searches for \textbf{open} tours. You have
fb2d8012ed08 updated
Christian Urban <urbanc@in.tum.de>
parents: 60
diff changeset
   327
  to be careful to write a tail-recursive version of the first-tour-heuristic
fb2d8012ed08 updated
Christian Urban <urbanc@in.tum.de>
parents: 60
diff changeset
   328
  function otherwise you will get problems with stack-overflows.
45
8399976b77fe updated
Christian Urban <urbanc@in.tum.de>
parents: 42
diff changeset
   329
\end{itemize}  
6
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   330
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   331
\end{document}
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   332
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   333
%%% Local Variables: 
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   334
%%% mode: latex
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   335
%%% TeX-master: t
aae256985251 updated
Christian Urban <urbanc@in.tum.de>
parents:
diff changeset
   336
%%% End: