Project

Profile

Help

How to connect?
Download (11.4 KB) Statistics
| Branch: | Tag: | Revision:

he / tags / 9.8.0.12 / samples / styles / tour.xsl @ c74fd4aa

1
<xsl:transform
2
 xmlns:xsl="http://www.w3.org/1999/XSL/Transform"
3
 xmlns:xs="http://www.w3.org/2001/XMLSchema"
4
 version="2.0"
5
 xmlns:tour="http://www.wrox.com/5067/tour"
6
 exclude-result-prefixes="tour xs"
7
>
8

    
9
<!--
10
    XSLT stylesheet to perform a knight's tour of the chessboard.
11
    Author: Michael H. Kay
12
    Date: 15 November 2002
13
    
14
    This version modified to use XSLT 2.0 and XPath 2.0, with sequences and functions.
15
    Type declarations added in Nov 2002 version.
16

    
17
    This stylesheet can be run using any XML file as a dummy source document.
18
    There is an optional parameter, start, which can be set to any square on the
19
    chessboard, e.g. a3 or h5. By default the tour starts at a1.
20

    
21
    The output is an HTML display of the completed tour.
22

    
23
    Internally, the following data representations are used:
24
    * A square on the chessboard: represented as a number in the range 0 to 63
25
    * A state of the chessboard: a sequence of 64 integers, each containing a move number. 
26
      A square that has not been visited yet is represented by a zero.
27
    * A set of possible moves: represented as a sequence of integers,
28
    * each integer representing the number of the destination square
29
      
30
-->
31

    
32
<xsl:output method="html" indent="yes"/>
33

    
34
<xsl:param name="start" select="'a1'"/>
35

    
36
<!-- start-column is an integer in the range 0-7 -->
37

    
38
<xsl:variable name="start-column" as="xs:integer"
39
    select="xs:integer(translate(substring($start, 1, 1),
40
            'abcdefgh', '01234567'))"/>
41

    
42
<!-- start-row is an integer in the range 0-7, with zero at the top -->
43

    
44
<xsl:variable name="start-row" as="xs:integer"
45
    select="8 - xs:integer(substring($start, 2, 1))"/>
46

    
47
<xsl:template name="main" match="/">
48

    
49
    <!-- This template controls the processing. It does not access the source document. -->
50

    
51
    <!-- Validate the input parameter -->
52

    
53
    <xsl:if test="not(matches($start, '^[a-h][1-8]$'))">
54
        <xsl:message terminate="yes">
55
             Invalid start parameter: try say 'a1' or 'g6'
56
        </xsl:message>
57

    
58
    </xsl:if>
59

    
60
    <!-- Set up the empty board -->
61

    
62
    <xsl:variable name="empty-board" as="xs:integer*" 
63
        select="for $i in (1 to 64) return 0"/>
64

    
65
    <!-- Place the knight on the board at the chosen starting position -->
66
    
67
    <xsl:variable name="initial-board" as="xs:integer*" 
68
        select="tour:place-knight(1, $empty-board, $start-row * 8 + $start-column)"/>
69

    
70
    <!-- Evaluate the knight's tour -->
71

    
72
    <xsl:variable name="final-board" as="xs:integer*" 
73
       select="tour:make-moves(2, $initial-board, $start-row * 8 + $start-column)"/>
74

    
75
    <!-- produce the HTML output -->
76

    
77
    <xsl:call-template name="print-board">
78
        <xsl:with-param name="board" select="$final-board"/>
79
    </xsl:call-template>
80

    
81
</xsl:template>
82

    
83
<xsl:function name="tour:place-knight" as="xs:integer*">
84

    
85
    <!-- This function places a knight on the board at a given square. The returned value is
86
         the supplied board, modified to indicate that the knight reached a given square at a given
87
         move -->
88

    
89
    <xsl:param name="move" as="xs:integer"/>
90
    <xsl:param name="board" as="xs:integer*"/>
91
    <xsl:param name="square" as="xs:integer" /> <!-- integer in range 0..63 -->
92
    <xsl:sequence select="
93
        for $i in 1 to 64 return
94
            if ($i = $square + 1) then $move else $board[$i]" />
95

    
96
</xsl:function>
97

    
98
<xsl:function name="tour:make-moves" as="xs:integer*">
99

    
100
    <!-- This function takes the board in a given state, decides on the next move to make,
101
         and then calls itself recursively to make further moves, until the knight has completed
102
         his tour of the board. It returns the board in its final state. -->
103

    
104
    <xsl:param name="move" as="xs:integer" />
105
    <xsl:param name="board" as="xs:integer*" />
106
    <xsl:param name="square" as="xs:integer" />
107

    
108
    <!-- determine the possible moves that the knight can make -->
109

    
110
    <xsl:variable name="possible-move-list" as="xs:integer*"  
111
        select="tour:list-possible-moves($board, $square)"/>
112

    
113
    <!-- try these moves in turn until one is found that works -->
114

    
115
    <xsl:sequence 
116
        select="tour:try-possible-moves($move, $board, $square, $possible-move-list)"/>
117

    
118
</xsl:function>
119

    
120
<xsl:function name="tour:try-possible-moves" as="xs:integer*" >
121

    
122
    <!-- This template tries a set of possible moves that the knight can make
123
         from a given position. It determines the best move as the one to the square with
124
         fewest exits. If this is unsuccessful then it can backtrack and
125
         try another move; however this turns out rarely to be necessary. 
126
         
127
         The function makes the selected move, and then calls make-moves() to make
128
         subsequent moves, returning the final state of the board. -->
129

    
130
    <xsl:param name="move" as="xs:integer" />
131
    <xsl:param name="board" as="xs:integer*" />
132
    <xsl:param name="square" as="xs:integer" />
133
    <xsl:param name="possible-moves" as="xs:integer*" />
134

    
135
    <xsl:sequence
136
        select="if (count($possible-moves)!=0)
137
                then tour:make-best-move($move, $board, $square, $possible-moves)
138
                else ()"/>
139

    
140
        <!-- if there is no possible move, we return the special value () as the final state
141
             of the board, to indicate to the caller that we got stuck -->
142
</xsl:function>
143

    
144
<xsl:function name="tour:make-best-move" as="xs:integer*">
145
    <xsl:param name="move" as="xs:integer" />
146
    <xsl:param name="board" as="xs:integer*" />
147
    <xsl:param name="square" as="xs:integer" />
148
    <xsl:param name="possible-moves" as="xs:integer*" />        
149
    <!-- if at least one move is possible, find the best one -->
150

    
151
    <xsl:variable name="best-move"
152
        select="tour:find-best-move($board, $possible-moves, 9, 999)"/>
153

    
154
    <!-- find the list of possible moves excluding the best one -->
155

    
156
    <xsl:variable name="other-possible-moves" as="xs:integer*" 
157
        select="$possible-moves[. != $best-move]"/>
158

    
159
    <!-- update the board to make the move chosen as the best one -->
160

    
161
    <xsl:variable name="next-board" as="xs:integer*" 
162
        select="tour:place-knight($move, $board, $best-move)"/>
163
    
164
    <!-- now make further moves using a recursive call, until the board is complete -->
165

    
166
    <xsl:variable name="final-board" as="xs:integer*" 
167
        select = "if (count($next-board[.=0])!=0) 
168
                    then tour:make-moves($move+1, $next-board, $best-move)
169
                    else $next-board"/>
170

    
171
    <!-- if the final board has the special value '()', we got stuck, and have to choose
172
         the next best of the possible moves. This is done by a recursive call. I thought
173
         that the knight never did get stuck, but it does: if the starting square is f1,
174
         the wrong choice is made at move 58, and needs to be reversed. -->
175

    
176
    <xsl:sequence select="
177
        if (empty($final-board))
178
        then tour:try-possible-moves($move, $board, $square, $other-possible-moves)
179
        else $final-board"/>
180
        
181
</xsl:function>
182

    
183
<xsl:function name="tour:find-best-move" as="xs:integer*" >
184

    
185
    <!-- This function finds from among the possible moves, the one with fewest exits.
186
         It calls itself recursively. -->
187
         
188
    <xsl:param name="board" as="xs:integer*" />            
189
    <xsl:param name="possible-moves" as="xs:integer*" />
190
    <xsl:param name="fewest-exits" as="xs:integer" />
191
    <xsl:param name="best-so-far" as="xs:integer" />
192

    
193
    <!-- split the list of possible moves into the first move and the rest of the moves -->
194

    
195
    <xsl:variable name="trial-move" as="xs:integer" 
196
        select="$possible-moves[1]"/>
197
    <xsl:variable name="other-possible-moves" as="xs:integer*" 
198
        select="$possible-moves[position() &gt; 1]"/>
199

    
200
    <!-- try making the first move -->
201

    
202
    <xsl:variable name="trial-board" as="xs:integer*" 
203
        select="tour:place-knight(99, $board, $trial-move)"/>
204

    
205
    <!-- see how many moves would be possible the next time -->
206

    
207
    <xsl:variable name="trial-move-exit-list" as="xs:integer*" 
208
        select="tour:list-possible-moves($trial-board, $trial-move)"/>
209

    
210
    <xsl:variable name="number-of-exits" as="xs:integer" 
211
        select="count($trial-move-exit-list)"/>
212

    
213
    <!-- determine whether this trial move has fewer exits than those considered up till now -->
214

    
215
    <xsl:variable name="minimum-exits" as="xs:integer" 
216
        select="min(($number-of-exits, $fewest-exits))"/>
217

    
218
    <!-- determine which is the best move (the one with fewest exits) so far -->
219

    
220
    <xsl:variable name="new-best-so-far" as="xs:integer" 
221
        select="if ($number-of-exits &lt; $fewest-exits)
222
                then $trial-move
223
                else $best-so-far"/>    
224

    
225
    <!-- if there are other possible moves, consider them too, using a recursive call.
226
         Otherwise return the best move found. -->
227

    
228
    <xsl:sequence
229
        select="if (count($other-possible-moves)!=0)
230
                then tour:find-best-move($board, $other-possible-moves, 
231
                                            $minimum-exits, $new-best-so-far)
232
                else $new-best-so-far"/>
233

    
234
</xsl:function>
235

    
236
<xsl:function name="tour:list-possible-moves" as="xs:integer*">
237

    
238
    <!-- This function, given the knight's position on the board, returns the set of squares
239
         he can move to. The squares will be ones that have not been visited before -->
240
         
241
    <xsl:param name="board" as="xs:integer*" />
242
    <xsl:param name="square" as="xs:integer" />
243
    
244
    <xsl:variable name="row" as="xs:integer" 
245
        select="$square idiv 8"/>
246
    <xsl:variable name="column" as="xs:integer" 
247
        select="$square mod 8"/>
248

    
249
    <xsl:sequence select="
250
        (if ($row &gt; 1 and $column &gt; 0 and $board[($square - 17) + 1]=0)
251
            then $square - 17 else (),
252
         if ($row &gt; 1 and $column &lt; 7 and $board[($square - 15) + 1]=0)
253
            then $square - 15 else (),
254
         if ($row &gt; 0 and $column &gt; 1 and $board[($square - 10) + 1]=0)
255
            then $square - 10 else (),
256
         if ($row &gt; 0 and $column &lt; 6 and $board[($square - 6) + 1]=0)
257
            then $square - 6 else (),
258
         if ($row &lt; 6 and $column &gt; 0 and $board[($square + 15) + 1]=0)
259
            then $square + 15 else (),
260
         if ($row &lt; 6 and $column &lt; 7 and $board[($square + 17) + 1]=0)
261
            then $square + 17 else (),
262
         if ($row &lt; 7 and $column &gt; 1 and $board[($square + 6) + 1]=0)
263
            then $square + 6 else (),
264
         if ($row &lt; 7 and $column &lt; 6 and $board[($square + 10) + 1]=0)
265
            then $square + 10 else () )"
266
         />        
267

    
268
</xsl:function>
269

    
270
<xsl:template name="print-board">
271

    
272
    <!-- Output the board in HTML format -->
273

    
274
    <xsl:param name="board" as="xs:integer*" />
275

    
276
    <html>
277
    <head>
278
        <title>Knight's tour</title>
279
    </head>
280
    <body>
281
    <div align="center">
282
    <h1>Knight's tour starting at <xsl:value-of select="$start"/></h1>
283
    <table border="1" cellpadding="4">
284
        <xsl:for-each select="0 to 7">
285
           <xsl:variable name="row" select="."/>
286
           <tr>
287
              <xsl:for-each select="0 to 7">
288
                <xsl:variable name="column" select="."/>
289
                <xsl:variable name="color"
290
                  select="if ((($row + $column) mod 2)=1)
291
                          then 'xffff44' else 'white'"/>
292
                <td align="center" bgcolor="{$color}">
293
                  <xsl:value-of select="$board[$row * 8 + $column + 1]"/>
294
                </td>
295
              </xsl:for-each>
296
           </tr>
297
        </xsl:for-each>
298
    </table>
299
    </div>
300
    </body>
301
    </html>
302
</xsl:template>
303

    
304

    
305
</xsl:transform>
(12-12/12)