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

(: startcolumn is an integer in the range 07 :)

37


38

declare variable $startcolumn as xs:integer :=

39

xs:integer(translate(substring($start, 1, 1),

40

'abcdefgh', '01234567'));

41


42

(: startrow is an integer in the range 07, with zero at the top :)

43


44

declare variable $startrow 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(stringlength($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 $emptyboard 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 $initialboard as xs:integer* :=

73

tour:placeknight(1, $emptyboard, $startrow * 8 + $startcolumn)

74


75

(: Evaluate the knight's tour :)

76


77

let $finalboard as xs:integer* :=

78

tour:makemoves(2, $initialboard, $startrow * 8 + $startcolumn)

79


80

(: produce the HTML output :)

81


82

return tour:printboard($finalboard)

83

};

84


85

declare function tour:placeknight (

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:makemoves (

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 $possiblemovelist as xs:integer* :=

113

tour:listpossiblemoves($board, $square)

114


115

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

116


117

return tour:trypossiblemoves($move, $board, $square, $possiblemovelist)

118

};

119


120

declare function tour:trypossiblemoves (

121

$move as xs:integer,

122

$board as xs:integer*,

123

$square as xs:integer, (: range 0 to 63 :)

124

$possiblemoves 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 makemoves() to make

133

subsequent moves, returning the final state of the board. :)

134


135

if (count($possiblemoves)!=0)

136

then tour:makebestmove($move, $board, $square, $possiblemoves)

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:makebestmove (

144

$move as xs:integer,

145

$board as xs:integer*,

146

$square as xs:integer, (: range 0 to 63 :)

147

$possiblemoves 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 $bestmove as xs:integer :=

158

tour:findbestmove($board, $possiblemoves, 9, 999)

159


160

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

161


162

let $otherpossiblemoves as xs:integer* :=

163

$possiblemoves[. != $bestmove]

164


165

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

166


167

let $nextboard as xs:integer* :=

168

tour:placeknight($move, $board, $bestmove)

169


170

(: now make further moves using a recursive call, until the board is complete :)

171


172

let $finalboard as xs:integer* :=

173

if ($move < $endd) (:count($nextboard[.=0])!=0:)

174

then tour:makemoves($move+1, $nextboard, $bestmove)

175

else $nextboard

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($finalboard))

184

then tour:trypossiblemoves($move, $board, $square, $otherpossiblemoves)

185

else $finalboard

186


187

};

188


189

declare function tour:findbestmove (

190

$board as xs:integer*,

191

$possiblemoves as xs:integer*,

192

$fewestexits as xs:integer,

193

$bestsofar 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 $trialmove as xs:integer :=

202

$possiblemoves[1]

203


204

let $otherpossiblemoves as xs:integer* :=

205

$possiblemoves[position() > 1]

206


207

(: try making the first move :)

208


209

let $trialboard as xs:integer* :=

210

tour:placeknight(99, $board, $trialmove)

211


212

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

213


214

let $trialmoveexitlist as xs:integer* :=

215

tour:listpossiblemoves($trialboard, $trialmove)

216


217

let $numberofexits as xs:integer :=

218

count($trialmoveexitlist)

219


220

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

221


222

let $minimumexits as xs:integer :=

223

min(($numberofexits, $fewestexits))

224


225

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

226


227

let $newbestsofar as xs:integer :=

228

if ($numberofexits < $fewestexits)

229

then $trialmove

230

else $bestsofar

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($otherpossiblemoves)!=0)

237

then tour:findbestmove($board, $otherpossiblemoves,

238

$minimumexits, $newbestsofar)

239

else $newbestsofar

240


241

};

242


243

declare function tour:listpossiblemoves (

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:printboard (

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 " "

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}&end={$endd+1}">Step</a>

312

else ()

313

}</p>

314

</div>

315

</body>

316

</html>

317

};

318


319

tour:main()

320

