Project

Profile

Help

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

he / latest10 / samples / query / tour.xq @ b660dcd9

1
xquery version "3.0";
2
declare namespace tour="http://wrox.com/tour";
3

    
4
(:
5
    XQuery program to perform a knight's tour of the chessboard.
6
    Author: Michael H. Kay
7
    Date: 26 June 2003
8
    Modified: 25 Sept 2014
9
    
10
    This version modified to use XQuery 3.0, with sequences and functions.
11

    
12
    This query does not use a source document.
13
    There is an optional parameter, start, which can be set to any square on the
14
    chessboard, e.g. a3 or h5. By default the tour starts at a1.
15
    
16
    There is a second optional parameter, end, which indicates that the processing should stop
17
    after a given number of steps (the default value is 64). This can be used to animate the 
18
    display of the tour. This works especially well when the query is compiled into a Java servlet.
19

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

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

    
31
declare variable $start as xs:string external :='a1';
32

    
33
declare variable $end as xs:string external :='64';
34
declare variable $endd as xs:integer := xs:integer($end); 
35

    
36
(: start-column is an integer in the range 0-7 :)
37

    
38
declare variable $start-column as xs:integer :=
39
    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
declare variable $start-row as xs:integer :=
45
    8 - xs:integer(substring($start, 2, 1));
46
    
47
declare function tour:main () as element() {
48

    
49
    (: This function controls the processing. It does not access the source document. :)
50

    
51
    (: Validate the input parameter :)
52

    
53
    if (not(string-length($start)=2) or
54
        not(translate(substring($start,1,1), 'abcdefgh', 'aaaaaaaa')='a') or
55
        not(translate(substring($start,2,1), '12345678', '11111111')='1'))
56
    then
57
        error((), "Invalid start parameter: try say 'a1' or 'g6'")
58
    else
59
    
60
    if (not($endd = 1 to 64)) 
61
    then
62
        error((), "Invalid end parameter: must be in range 1 to 64")
63
    else
64

    
65
    (: Set up the empty board :)
66

    
67
    let $empty-board as xs:integer* := 
68
        for $i in (1 to 64) return 0
69
    
70
    (: Place the knight on the board at the chosen starting position :)
71
    
72
    let $initial-board as xs:integer* :=
73
        tour:place-knight(1, $empty-board, $start-row * 8 + $start-column)
74
    
75
    (: Evaluate the knight's tour :)
76

    
77
    let $final-board as xs:integer* :=
78
       tour:make-moves(2, $initial-board, $start-row * 8 + $start-column)
79

    
80
    (: produce the HTML output :)
81
    
82
    return tour:print-board($final-board)
83
};
84

    
85
declare function tour:place-knight (
86
                    $move as xs:integer,
87
                    $board as xs:integer*,
88
                    $square as xs:integer (: range 0 to 63 :)
89
                  ) as xs:integer* {
90

    
91
    (: This function places a knight on the board at a given square. The returned value is
92
         the supplied board, modified to indicate that the knight reached a given square at a given
93
         move :)
94

    
95
    for $i in 1 to 64 return
96
        if ($i = $square + 1) then $move else $board[$i]
97

    
98
};
99

    
100
declare function tour:make-moves (
101
                    $move as xs:integer,
102
                    $board as xs:integer*,
103
                    $square as xs:integer (: range 0 to 63 :)
104
                ) as xs:integer* {
105

    
106
    (: This function takes the board in a given state, decides on the next move to make,
107
         and then calls itself recursively to make further moves, until the knight has completed
108
         his tour of the board. It returns the board in its final state. :)
109

    
110
    (: determine the possible moves that the knight can make :)
111

    
112
    let $possible-move-list as xs:integer* := 
113
        tour:list-possible-moves($board, $square)
114

    
115
    (: try these moves in turn until one is found that works :)
116

    
117
    return tour:try-possible-moves($move, $board, $square, $possible-move-list)
118
};
119

    
120
declare function tour:try-possible-moves (
121
                    $move as xs:integer,
122
                    $board as xs:integer*,
123
                    $square as xs:integer, (: range 0 to 63 :)
124
                    $possible-moves as xs:integer* )
125
                as xs:integer* {
126

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

    
135
         if (count($possible-moves)!=0)
136
                then tour:make-best-move($move, $board, $square, $possible-moves)
137
                else ()
138

    
139
         (: if there is no possible move, we return the special value () as the final state
140
             of the board, to indicate to the caller that we got stuck :)
141
};
142

    
143
declare function tour:make-best-move (
144
                    $move as xs:integer,
145
                    $board as xs:integer*,
146
                    $square as xs:integer, (: range 0 to 63 :)
147
                    $possible-moves as xs:integer* )
148
                as xs:integer* {
149
                
150
    (: this function, given the state of the board and a set of possible moves,
151
       determines which of the moves is the best one. It then makes this move,
152
       and proceeds recursively to make further moves, eventually returning the
153
       final state of the board. :)            
154
        
155
    (:  if at least one move is possible, find the best one :)
156

    
157
    let $best-move as xs:integer :=
158
        tour:find-best-move($board, $possible-moves, 9, 999)
159

    
160
    (: find the list of possible moves excluding the best one :)
161

    
162
    let $other-possible-moves as xs:integer* :=
163
        $possible-moves[. != $best-move]
164

    
165
    (: update the board to make the move chosen as the best one :)
166

    
167
    let $next-board as xs:integer* :=
168
        tour:place-knight($move, $board, $best-move)
169
    
170
    (: now make further moves using a recursive call, until the board is complete :)
171

    
172
    let $final-board as xs:integer* :=
173
        if ($move < $endd) (:count($next-board[.=0])!=0:) 
174
                    then tour:make-moves($move+1, $next-board, $best-move)
175
                    else $next-board
176

    
177
    (:   if the final board has the special value '()', we got stuck, and have to choose
178
         the next best of the possible moves. This is done by a recursive call. I thought
179
         that the knight never did get stuck, but it does: if the starting square is f1,
180
         the wrong choice is made at move 58, and needs to be reversed. :)
181

    
182
    return
183
        if (empty($final-board))
184
        then tour:try-possible-moves($move, $board, $square, $other-possible-moves)
185
        else $final-board
186
        
187
};
188

    
189
declare function tour:find-best-move (
190
                    $board as xs:integer*,
191
                    $possible-moves as xs:integer*,
192
                    $fewest-exits as xs:integer,
193
                    $best-so-far as xs:integer )
194
                as xs:integer {
195

    
196
    (:  This function finds from among the possible moves, the one with fewest exits.
197
         It calls itself recursively. :)
198
         
199
    (:  split the list of possible moves into the first move and the rest of the moves :)
200

    
201
    let $trial-move as xs:integer := 
202
        $possible-moves[1]
203
    
204
    let $other-possible-moves as xs:integer* :=
205
        $possible-moves[position() > 1]
206

    
207
    (: try making the first move :)
208

    
209
    let $trial-board as xs:integer* :=
210
        tour:place-knight(99, $board, $trial-move)
211

    
212
    (: see how many moves would be possible the next time :)
213

    
214
    let $trial-move-exit-list as xs:integer* :=
215
        tour:list-possible-moves($trial-board, $trial-move)
216

    
217
    let $number-of-exits as xs:integer :=
218
        count($trial-move-exit-list)
219

    
220
    (:  determine whether this trial move has fewer exits than those considered up till now :)
221

    
222
    let $minimum-exits as xs:integer :=
223
        min(($number-of-exits, $fewest-exits))
224

    
225
    (:  determine which is the best move (the one with fewest exits) so far :)
226

    
227
    let $new-best-so-far as xs:integer :=
228
        if ($number-of-exits < $fewest-exits)
229
            then $trial-move
230
            else $best-so-far  
231

    
232
    (:  if there are other possible moves, consider them too, using a recursive call.
233
        Otherwise return the best move found. :)
234

    
235
    return
236
        if (count($other-possible-moves)!=0)
237
            then tour:find-best-move($board, $other-possible-moves, 
238
                                            $minimum-exits, $new-best-so-far)
239
            else $new-best-so-far
240

    
241
};
242

    
243
declare function tour:list-possible-moves (
244
                $board as xs:integer*,
245
                $square as xs:integer )
246
            as xs:integer* {
247

    
248
    (:   This function, given the knight's position on the board, returns the set of squares
249
         he can move to. The squares will be ones that have not been visited before :)
250
            
251
    let $row as xs:integer := $square idiv 8
252
    let $column as xs:integer := $square mod 8
253

    
254
    return
255
        (if ($row > 1 and $column > 0 and $board[($square - 17) + 1]=0)
256
            then $square - 17 else (),
257
         if ($row > 1 and $column < 7 and $board[($square - 15) + 1]=0)
258
            then $square - 15 else (),
259
         if ($row > 0 and $column > 1 and $board[($square - 10) + 1]=0)
260
            then $square - 10 else (),
261
         if ($row > 0 and $column < 6 and $board[($square - 6) + 1]=0)
262
            then $square - 6 else (),
263
         if ($row < 6 and $column > 0 and $board[($square + 15) + 1]=0)
264
            then $square + 15 else (),
265
         if ($row < 6 and $column < 7 and $board[($square + 17) + 1]=0)
266
            then $square + 17 else (),
267
         if ($row < 7 and $column > 1 and $board[($square + 6) + 1]=0)
268
            then $square + 6 else (),
269
         if ($row < 7 and $column < 6 and $board[($square + 10) + 1]=0)
270
            then $square + 10 else () )
271

    
272
};
273

    
274
declare function tour:print-board (
275
                $board as xs:integer* )
276
            as element()
277
{
278
    (: Output the board in HTML format :)
279

    
280
    <html>
281
    <head>
282
        <title>Knight's tour</title>
283
    </head>
284
    <body>
285
    <div align="center">
286
    <h1>Knight's tour starting at {$start}</h1>
287
    <table border="1" cellpadding="4">
288
        {for $row in 0 to 7 return
289
           <tr>
290
              {for $column in 0 to 7
291
                let $color :=
292
                          if ((($row + $column) mod 2)=1)
293
                          then 'xffff44' 
294
                          else 'white' return
295
                <td align="center" bgcolor="{$color}" width="22">{
296
                  let $n := $board[$row * 8 + $column + 1]
297
                  return 
298
                      if ($endd != 64 and $n = $endd)
299
                      then <b>{$n}</b>
300
                      else if ($n = 0)
301
                      then "&#xa0;"
302
                      else $n
303
                }</td>
304
              }
305
           </tr>
306
        }
307
    </table>
308
    <p>{
309
        if ($endd != 64) 
310
        then
311
          <a href="Tour?start={$start}&amp;end={$endd+1}">Step</a>
312
        else ()
313
    }</p>    
314
    </div>
315
    </body>
316
    </html>
317
};
318

    
319
tour:main()
320

    
(3-3/3)