{VERSION 2 2 "IBM INTEL NT" "2.2" } {USTYLETAB {CSTYLE "Maple Input" -1 0 "Courier New" 0 1 255 0 0 1 0 1 0 0 1 0 0 0 0 }{CSTYLE "" -1 18 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 } {CSTYLE "" 18 20 "" 0 1 0 0 255 1 0 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 256 "" 1 18 0 0 5 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 257 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 258 "" 0 1 0 0 4 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 259 "" 0 1 124 137 109 0 0 0 1 0 0 0 0 0 0 }{CSTYLE " " -1 260 "" 0 1 0 0 2 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 262 "" 0 1 0 0 2 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 263 "" 0 1 123 137 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 264 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 265 "" 0 1 101 118 105 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 266 "" 0 1 135 137 143 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 267 "" 0 1 0 0 24 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 268 "" 0 1 11 144 120 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 269 "" 0 1 0 0 20 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 270 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 271 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 272 "" 0 1 173 137 216 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 273 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 274 "" 0 1 0 0 128 0 0 1 0 0 0 0 0 0 0 }{CSTYLE " " -1 275 "" 0 1 0 0 2 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 276 "" 0 1 0 0 144 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 277 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 278 "" 0 1 121 137 0 0 1 0 0 0 0 0 0 0 0 } {CSTYLE "" -1 279 "" 0 1 133 137 116 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 281 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 282 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 283 "" 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 284 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 285 "" 0 1 0 0 52 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 286 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 288 "" 0 1 0 0 240 0 0 0 1 0 0 0 0 0 0 }{CSTYLE "" -1 289 "" 0 1 101 32 102 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 290 "" 0 1 20 0 4 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 291 "" 0 1 74 0 155 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 292 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 293 "" 0 1 124 14 184 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 294 "" 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 } {CSTYLE "" -1 295 "" 0 1 0 0 24 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 296 "" 0 1 0 0 17 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 297 "" 0 1 0 0 52 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 298 "" 0 1 0 0 0 0 1 0 0 0 0 0 0 0 0 }{CSTYLE "" -1 299 "" 0 1 0 0 2 0 0 1 0 0 0 0 0 0 0 }{CSTYLE "" -1 300 "" 0 1 99 114 111 0 0 1 0 0 0 0 0 0 0 }{PSTYLE "Normal" -1 0 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Text Output" -1 2 1 {CSTYLE "" -1 -1 "Courier N ew" 1 10 0 0 255 1 0 0 0 0 0 1 3 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 2 6 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 2 0 0 } 0 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Output" 0 11 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 3 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "" 11 12 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }1 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }{PSTYLE "Maple Plot" 0 13 1 {CSTYLE "" -1 -1 "" 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 }3 0 0 -1 -1 -1 0 0 0 0 0 0 -1 0 }} {SECT 0 {PARA 0 "" 0 "" {TEXT -1 5 " " }}{PARA 0 "" 0 "" {TEXT -1 30 " " }}{PARA 0 "" 0 "" {TEXT -1 36 " \+ " }{TEXT 256 31 " Knight tours on a \+ chess board" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 8 " The " }{TEXT 257 6 "knight" }{TEXT -1 82 " package contains \+ several routines designed to find knight tours on a chess board." }} {PARA 0 "" 0 "" {TEXT -1 3 " A " }{TEXT 259 11 "knight tour" }{TEXT -1 95 " is a sequence of legal knight moves which does not move onto a square previously occupied. A " }{TEXT 258 20 "complete knight tour " }{TEXT -1 83 " is one in which every square of the chess board has \+ been visited exactly once. A " }{TEXT 260 18 "closed knight tour" } {TEXT -1 62 " is a complete tour which returns to the square it began . An " }{TEXT 288 16 "open knight tour" }{TEXT -1 342 " is a complete \+ tour which does not return to it's starting position. The routines in this package only search for open knight tours (there is a technique \+ due to Bertrand-Euler for obtaining a closed tour from an open one - s ee the book by Ball and Coxeter listed at the end of this worksheet). \+ Some of the procedures in this package include " }}{PARA 0 "" 0 "" {TEXT -1 95 " 1. a routine to list all legal moves from a given square to a square it hasn't been to before," }}{PARA 0 "" 0 "" {TEXT -1 79 " 2. some interactive routines to perform random searches for open kni ght tours," }}{PARA 0 "" 0 "" {TEXT -1 153 " 3. implementations of War nsdorff's rule (which says, roughly speaking, you should always make t he \"worst\" move possible to get a complete knight tour), " }}{PARA 0 "" 0 "" {TEXT -1 90 " 4. a procedure to draw a knight tour as an arr ay of numbers representing the move number," }}{PARA 0 "" 0 "" {TEXT -1 87 " 5. a procedure to add to a graph the vertices representing the moves it can make next," }}{PARA 0 "" 0 "" {TEXT -1 31 " 6. some back tracking routines." }}{PARA 0 "" 0 "" {TEXT -1 61 " We shall illustr ate some of these. First, load the package" }}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 53 "with(networks):\nwith(share):\nreadshare(knight,gam es);" }}{PARA 6 "" 1 "" {TEXT -1 70 "See ?share and ?share,contents fo r information about the share library" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%'knightG" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 93 " A simple initial ization routine defines some global variables, such as a beginning pos ition " }{TEXT 264 2 "AT" }{TEXT -1 1 ":" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 23 "knighttour():\nAT;\nBeen;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"\"\"F$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7\"" }}} {PARA 0 "" 0 "" {TEXT -1 17 " The procedure " }{TEXT 262 5 "cango" } {TEXT -1 173 " tells you the moves you can visit from a given position . It returns a list of moves which are (a) legal, and (b) have not \+ been visited before (in the sense that they do " }}{PARA 0 "" 0 "" {TEXT -1 65 " not belong to the list of moves specified by the gobal v ariable " }{TEXT 294 4 "Been" }{TEXT -1 7 "). The " }{TEXT 297 5 "orde r" }{TEXT -1 44 " of the moves in the list returns by " }{TEXT 295 5 "cango" }{TEXT -1 63 " is as follows: from [x,y], begining with \+ the upper right-hand " }}{PARA 0 "" 0 "" {TEXT -1 47 " square at [x+1, y+2] and continuing clockwise, " }{TEXT 296 5 "cango" }{TEXT -1 43 " r eturns all moves satisfying (a) and (b). " }}{PARA 0 "" 0 "" {TEXT -1 47 " We may manually change the global variable " }{TEXT 263 4 "Bee n" }{TEXT -1 25 " to draw an example tour:" }}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 11 "cango(AT);\n" }{TEXT -1 37 "This tells you where yo u can go from " }{TEXT 266 2 "AT" }{TEXT -1 2 ".\n" }{MPLTEXT 1 0 12 " Been:=[AT];\n" }{TEXT -1 12 "This resets " }{TEXT 265 4 "Been" }{TEXT -1 57 " so that cango knows where you've been for the next move." } {MPLTEXT 1 0 15 "\ncango([2,3]);\n" }{TEXT -1 75 "This tells you where you can go from [2,3] (it knows you've been to [1,1])." }{MPLTEXT 1 0 30 "\nBeen:=[AT,[2,3]];\ndrawtour();" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$7$\"\"#\"\"$7$F&F%" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%BeenG 7#7$\"\"\"F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7'7$\"\"$\"\"&7$\"\"%F (7$F(\"\"#7$F%\"\"\"7$F,F&" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%BeenG 7$7$\"\"\"F'7$\"\"#\"\"$" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG 6#7*7*\"\"!F(F(F(F(F(F(F(F'F'F'F'7*F(\"\"#F(F(F(F(F(F(F'7*\"\"\"F(F(F( F(F(F(F(" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 29 " We have already crea ted (in " }{TEXT 267 13 "knighttour();" }{TEXT -1 17 ") a graph called " }{TEXT 268 11 "KnightTree:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 40 "vertices(KnightTree);\nedges(KnightTree);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<#%$v11G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<\"" }}} {PARA 0 "" 0 "" {TEXT -1 107 " There is a procedure to add the vertic es and edges associated to all the moves returned by the procedure " } {TEXT 269 5 "cango" }{TEXT -1 1 ":" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 10 "Been:=[]:\n" }{TEXT -1 35 "(We must reset the global \+ variable " }{TEXT 271 4 "Been" }{TEXT -1 9 " so that " }{TEXT 270 5 "c ango" }{TEXT -1 39 " thinks we are just starting our tour.)" } {MPLTEXT 1 0 72 "addnodes(AT);\nvertices(KnightTree);\nedges(KnightTre e);\ndraw(KnightTree);" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"#" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#%#e2G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<%%$v11G%$v32G%$v23G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<$%#e1G%#e2 G" }}{PARA 13 "" 1 "" {INLPLOT "6+-%'CURVESG6$7$7$$\"\"\"\"\"!F*7$$!+* )******\\!#5$!+WSDg')F.-%'COLOURG6&%$RGBGF*$\"#5!\"\"F*-F$6$7$F'7$$!+0 +++]F.$\"+NSDg')F.F1-%%TEXTG6$F+%$v32G-%'POINTSG6#F'-FA6$F'%$v11G-FE6# F;-FA6$F;%$v23G-FE6#F+-%*AXESSTYLEG6#%%NONEG" 2 271 271 271 2 0 1 0 2 9 0 1 2 1.000000 45.000000 45.000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 }}}{PARA 0 "" 0 "" {TEXT -1 76 " Notice th at the vertices are indexed by the position on the chess board. " }} {PARA 0 "" 0 "" {TEXT -1 91 " The graph of possible moves after only \+ two moves is already getting to look complicated: " }}{EXCHG {PARA 0 " > " 0 "" {MPLTEXT 1 0 105 "Been:=[1,1]:\naddnodes([3,2]);\naddnodes([2 ,3]);\nvertices(KnightTree);\nedges(KnightTree);\ndraw(KnightTree);" } }{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%#e8G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"\"'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%$e14G" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#<.%$v11G%$ v51G%$v13G%$v32G%$v24G%$v42G%$v31G%$v35G%$v15G%$v44G%$v53G%$v23G" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#<0%#e4G%#e6G%#e5G%#e1G%#e2G%#e7G%#e8G% #e9G%$e10G%$e11G%$e12G%$e13G%$e14G%#e3G" }}{PARA 13 "" 1 "" {INLPLOT " 6I-%'CURVESG6$7$7$$!\"\"\"\"!$!+in?59!#=7$$\"+]SDg')!#5$!+z******\\F1- %'COLOURG6&%$RGBGF*$\"#5F)F*-F$6$7$F'7$$\"\"\"F*F*F4-F$6$7$F'7$$\"+<++ +]F1$!+GSDg')F1F4-F$6$7$F=7$$!+2Q.^?!#>F>F4-F$6$7$F=F'F4-F$6$7$F'7$$\" +PSDg')F1$\"+-+++]F1F4-F$6$7$F'7$$!+0+++]F1$\"+NSDg')F1F4-F$6$7$FK7$$! +HSDg')F1$!+;+++]F1F4-F$6$7$FK7$$\"+U,J:;F-F(F4-%'POINTSG6#FU-%%TEXTG6 $FU%$v13G-F[p6#7$$\"+$*******\\F1$\"+USDg')F1-F^p6$Fcp%$v15G-F[p6#FK-F ^p6$FK%$v23G-F^p6$Fgn%$v24G-F[p6#7$$!+VSDg')F1$\"+\"*******\\F1-F^p6$F eq%$v31G-F[p6#F'-F^p6$F'%$v32G-F[p6#F_o-F^p6$F_o%$v35G-F^p6$7$$!+*)*** ***\\F1$!+WSDg')F1%$v42G-F[p6#Fgo-F^p6$Fgo%$v44G-F[p6#FC-F^p6$FC%$v51G -F[p6#F.-F^p6$F.%$v53G-F$6$7$FKFirF4-F$6$7$FKFeqF4-F$6$7$FKF=F4-F$6$7$ F'FgoF4-F$6$7$FKFcpF4-F[p6#F=-F^p6$F=%$v11G-F[p6#Fgn-F[p6#Fir-%*AXESST YLEG6#%%NONEG" 2 271 271 271 2 0 1 0 2 9 0 1 2 1.000000 45.000000 45.000000 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 }} }{PARA 0 "" 0 "" {TEXT -1 8 " The " }{TEXT 289 8 "nextmove" }{TEXT -1 111 " routine randomly picks a move (and changes the random \"seed \" each time) and then updates the global variable " }{TEXT 290 4 "Be en" }{TEXT -1 1 ":" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 32 "Been:= [];\nnextmove([1,1]);\nBeen;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%Bee nG7\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7$\"\"$\"\"#" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#7#7$\"\"\"F%" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 135 " You may want to try running the above sequence several times to \+ convince yourself that it really can choose different moves each time. " }}{PARA 0 "" 0 "" {TEXT -1 13 " The routine " }{TEXT 291 11 "knightm oves" }{TEXT -1 31 " simply tries to reiterate the " }{TEXT 292 8 "nex tmove" }{TEXT -1 139 " procedure until either it finds a complete tour or no more moves are found. For example, to try to find a tour 60 mov es long, simply type:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 41 "Be en:=[]:\nknightmoves(60,AT);\ndrawtour();" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7K7$\"\"\"F%7$\"\"#\"\"$7$\"\"%F*7$F(F'7$\"\"&F%7$\"\"' F(7$\"\"(F%7$F-F'7$F1F(7$\"\")F%7$F/F'7$F5F(7$F1F-7$F-F*7$F*F'7$F/F%7$ F-F(7$F*F%7$F(F(7$F'F%7$F%F(7$F(F*7$F-F-7$F*F(7$F(F%7$F%F'7$F'F*7$F(F/ 7$F-F17$F1F/7$F5F*7$F/F-7$F1F17$F5F-7$F/F/7$F*F-7$F/F*7$F-F/7$F(F-7$F% F*7$F'F'" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7*7*\"\"!F(F(F (F(F(F(F(7*F(F(F(F(\"#HF(\"#LF(7*F(F(\"#GF(\"#Q\"#N\"#IF(7*F(F(\"#R\"# O\"#B\"#K\"#8\"#M7*\"#S\"#F\"#A\"\"$\"#9\"#PF(\"#J7*\"#@\"\"#\"#>\"#C \"#<\"\"'\"\"*\"#77*\"#E\"#T\"\"%\"#:\"\")\"#6F(F(7*\"\"\"\"#?\"#D\"#= \"\"&\"#;\"\"(\"#5" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 121 "The number of moves it actually found is obtained by either finding the largest \+ number in the above array or by entering " }{MPLTEXT 1 0 11 "nops(Been );" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#T" }}}{PARA 0 "" 0 "" {TEXT -1 166 " You may run the above sequence several times to see what dif ferent kinds of knight tours are possible. There is a procedure to do this for us. To ask MAPLE to run " }{TEXT 272 20 " knightmoves(60,AT) ;" }{TEXT -1 69 " say 20 times and return the largest tour found, use \+ the interactive " }{TEXT 293 9 " findtour" }{TEXT -1 79 " routine. You must enter the number of search tries (in this case 20) yourself:" }} {EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 26 "Been:=[];\nfindtour(60,AT); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>%%BeenG7\"" }}}{EXCHG {PARA 0 "En ter number of searches: " 0 "" {MPLTEXT 1 0 3 "20;" }}{PARA 11 "" 1 " " {XPPMATH 20 "6&%5largest~tour~found:~G\"#a%-~numtries~=~G\"#?" }} {PARA 11 "" 1 "" {XPPMATH 20 "6$%6shortest~tour~found:~G\"#D" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%9Length~of~average~tour:~G#\"$*=\"\"&" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#7X7$\"\"\"F%7$\"\"$\"\"#7$\"\"&F'7$\" \"(\"\"%7$\"\")F(7$\"\"'F'7$F/F-7$F1F*7$F/F17$F,F/7$F*F,7$F-F*7$F'F,7$ F%F17$F(F-7$F%F(7$F'F%7$F(F'7$F-F-7$F*F(7$F,F'7$F/F%7$F1F(7$F-F%7$F'F' 7$F(F%7$F%F'7$F'F-7$F(F17$F-F,7$F'F*7$F%F-7$F(F(7$F-F'7$F*F%7$F,F(7$F1 F-7$F/F*7$F,F,7$F*F/7$F-F17$F(F,7$F%F*7$F'F17$F*F*7$F,F17$F1F/7$F*F17$ F-F/7$F1F,7$F,F*7$F*F-7$F-F(7$F1F%" }}}{PARA 0 "" 0 "" {TEXT -1 237 " \+ Incidently, I don't know what the expected length of a random tour i s or even if the expected value of this random (Markov?) process exi sts. If it exists, some experiments suggest it appears to be approxim ately 33, 34, or maybe 35." }}{PARA 0 "" 0 "" {TEXT -1 95 " In any c ase, to find the picture of the largest tour found in the above search , you can use " }{TEXT 274 12 " drawtour();" }{TEXT -1 12 " as before. " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 11 "drawtour();" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7*7*\"\"!F(F(\"#\\\"#S\"#Z\"#5F( 7*F(\"#U\"#8\"#I\"#6\"#]\"#RF(7*\"#9\"#H\"#W\"#T\"#[F(\"#Y\"\"*7*\"#VF (\"#J\"#7\"#X\"\")\"#^\"#Q7*\"#K\"#:\"#G\"#>\"#_\"#P\"\"%\"\"(7*\"#F\" #=\"#D\"#M\"\"$\"\"'\"#@F(7*\"#;\"#L\"\"#\"#`\"#?\"#B\"#O\"\"&7*\"\"\" \"#E\"#<\"#C\"#N\"#aF(\"#A" }}}{PARA 0 "" 0 "" {TEXT -1 72 " So far , these routines have been simple random move strategies. The " } {TEXT 273 17 "searchknightmoves" }{TEXT -1 110 " r outine combines this random move strategy with a backtracking routine. To try to find a " }}{PARA 0 "" 0 "" {TEXT -1 108 " move say 55 moves long, type (note you must enter the number of search tries, in this c ase 10, yourself): " }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 35 "Been :=[]:\nsearchknightmoves(55,AT);" }}}{EXCHG {PARA 0 "How many tries? ( use semicolon)" 0 "" {MPLTEXT 1 0 3 "10;" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%FKnight~has~no~untoured~squares~after~G\"#X%'~movesG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%FKnight~has~no~untoured~squares~after~G\"#Z %'~movesG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%FKnight~has~no~untoured~ squares~after~G\"#Y%'~movesG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%FKnig ht~has~no~untoured~squares~after~G\"#Z%'~movesG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%FKnight~has~no~untoured~squares~after~G\"#Y%'~movesG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%FKnight~has~no~untoured~squares~aft er~G\"#Z%'~movesG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%FKnight~has~no~u ntoured~squares~after~G\"#Y%'~movesG" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6%%FKnight~has~no~untoured~squares~after~G\"#\\%'~movesG" }}{PARA 11 " " 1 "" {XPPMATH 20 "6%%FKnight~has~no~untoured~squares~after~G\"#\\%'~ movesG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%FKnight~has~no~untoured~squ ares~after~G\"#Y%'~movesG" }}{PARA 11 "" 1 "" {XPPMATH 20 "6$%ANumber~ of~backtracks~performed:~G\"#5" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7S7$ \"\"\"F%7$\"\"$\"\"#7$\"\"&F%7$\"\"'F'7$\"\"%F(7$F(F%7$F%F'7$F'F.7$F(F (7$F.F'7$F'F%7$F*F(7$\"\"(F%7$\"\")F'7$F,F(7$F*F.7$F7F*7$F*F,7$F.F97$F 'F,7$F(F97$F%F,7$F'F*7$F(F77$F%F*7$F(F'7$F.F.7$F(F*7$F%F77$F'F97$F.F,7 $F,F77$F9F,7$F,F*7$F*F77$F7F,7$F,F97$F.F77$F*F*7$F7F.7$F*F'7$F.F*7$F,F .FV7$F9F*7$F7F77$F*F97$F,F,7$F7F9" }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 65 "What is the maximum tour found and what does it look like? Enter \+ " }{MPLTEXT 1 0 22 "nops(Been);drawtour();" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#\"#\\" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#-%'MATRIXG6#7* 7*\"\"!\"#@\"#I\"#>\"#Z\"#P\"#\\F(7*\"#H\"#CF(\"#Q\"#N\"#K\"#YF(7*\"#A F(\"#?\"#J\"#=\"#[\"#O\"#L7*\"#D\"#G\"#B\"#U\"#R\"#M\"#<\"#X7*F(F(\"\" )\"#F\"#;\"#W\"#SF(7*\"\"(\"#EF(\"#5\"#T\"\"%F(\"#97*F(\"\"*\"\"#\"\"& \"#7\"#:F(F(7*\"\"\"\"\"'\"#6F(\"\"$F(\"#8F(" }}}{PARA 0 "" 0 "" {TEXT -1 54 " In general, the list of knight moves returned by " } {TEXT 275 5 "cango" }{TEXT -1 328 " is of length between 0 (if it is e mpty) and 8. Recall that the ordering in this list is clockwise, s tarting at the upper right-hand square. We may specify a knight tour \+ by an initial position [x0,y0] and a sequence of integers m1, m2, ... (with each integer taken between 1 and 8 inclusive) as follows. W e define the " }}{PARA 0 "" 0 "" {TEXT -1 107 " tour inductively: The \+ 0-th move is [x0,y0]. Suppose we are now at the i-th move [x,y] and \+ suppose that " }{TEXT 276 16 "M:=cango([x,y]);" }{TEXT -1 155 " has m elements with m>0 (if m=0 then we can go no further and our tour i s at an end). Then the (i+1)-st move is then k-th element of the list \+ M, where " }}{PARA 0 "" 0 "" {TEXT -1 20 " k=m.i (mod m) (the " } {TEXT 298 15 "representatives" }{TEXT -1 135 " of the residue classes \+ of m are taken to be 1, ..., m so this move always exists). Let us \+ call this notation for a knight tour the " }{TEXT 277 13 "list notatio n" }{TEXT -1 2 ". " }}{PARA 0 "" 0 "" {TEXT -1 14 " There is a " } {TEXT 299 6 "knight" }{TEXT -1 144 " routine to try to move a knight a long any given list. For example, to try to make the \"first move\" \+ 30 times starting from [1,1], simply type:" }}{EXCHG {PARA 0 "> " 0 " " {MPLTEXT 1 0 48 "L:=[seq(1,i=1..30)]:\nlistmove(L,AT);\ndrawtour(); " }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%*Made~all~G\"#I%'~movesG" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#7A7$\"\"\"F%7$\"\"#\"\"$7$F(\"\"&7$\" \"%\"\"(7$\"\"'\"\")7$F0F-7$F-F*7$F0F(7$F-F%7$F*F'7$F/F,7$F-F/7$F0F07$ F/F-7$F0F/7$F-F,7$F0F'7$F/F%7$F-F(7$F0F*7$F/F/7$F-F07$F*F-7$F/F*7$F-F- 7$F*F/7$F,F,7$F/F(7$F0F,7$F-F'7$F*F%" }}{PARA 11 "" 1 "" {XPPMATH 20 " 6#-%'MATRIXG6#7*7*\"\"!F(F(F(F(\"\"&\"#A\"#87*F(F(F(\"\"%\"#B\"#9\"#D \"\"'7*F(F(F(F(\"#E\"#@\"#7\"#:7*F(F(\"\"$F(F(\"#C\"\"(\"#?7*F(F(F(\"# FF(\"#6\"#;\"#H7*F(\"\"#F(F(F(\"#G\"#>\"\")7*F(F(F(F(\"#5F(\"#I\"#<7* \"\"\"F(F(F(\"#J\"#=\"\"*F(" }}}{PARA 0 "" 0 "" {TEXT -1 198 " We c annot choose the \"first move\" 64 times in a row. More generally, we \+ will have to have incredible luck to find a complete knight tour by guessing its list. However, we can combine this " }{TEXT 300 8 "li stmove" }{TEXT -1 37 " routine with a backtracking routine:" }}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 83 "Been:=[];\nL:=[seq(1,i=1..40)]:\nli stmove(L,AT);\nBeen:=[];\nlistmove_with_bt(L,AT,5);\n" }{TEXT -1 67 "T he routine will try to make all 40 moves by backtracking 5 times ." } {MPLTEXT 1 0 13 "\ndrawtour();\n" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#>% %BeenG7\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%&Made~G\"#O%'~movesG" }} {PARA 12 "" 1 "" {XPPMATH 20 "6#7F7$\"\"\"F%7$\"\"#\"\"$7$F(\"\"&7$\" \"%\"\"(7$\"\"'\"\")7$F0F-7$F-F*7$F0F(7$F-F%7$F*F'7$F/F,7$F-F/7$F0F07$ F/F-7$F0F/7$F-F,7$F0F'7$F/F%7$F-F(7$F0F*7$F/F/7$F-F07$F*F-7$F/F*7$F-F- 7$F*F/7$F,F,7$F/F(7$F0F,7$F-F'7$F*F%7$F(F'7$F*F(7$F,F%7$F/F'7$F0F%" }} {PARA 11 "" 1 "" {XPPMATH 20 "6#>%%BeenG7\"" }}{PARA 11 "" 1 "" {XPPMATH 20 "6%%&Made~G\"#O%:~moves~-~backtracking~...G" }}{PARA 11 " " 1 "" {XPPMATH 20 "6&%*Made~all~G\"#S%<~moves.~~Total~backtracks:~G\" \"\"" }}{PARA 12 "" 1 "" {XPPMATH 20 "6#7K7$\"\"\"F%7$\"\"#\"\"$7$F(\" \"&7$\"\"%\"\"(7$\"\"'\"\")7$F0F-7$F-F*7$F0F(7$F-F%7$F*F'7$F/F,7$F-F/7 $F0F07$F/F-7$F0F/7$F-F,7$F0F'7$F/F%7$F-F(7$F0F*7$F/F/7$F-F07$F*F-7$F/F *7$F-F-7$F*F/7$F,F,7$F/F(7$F0F,7$F-F'7$F*F%7$F(F'7$F*F(7$F,F%7$F'F'7$F (F,7$F,F/7$F*F07$F(F-7$F,F*7$F(F(" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#- %'MATRIXG6#7*7*\"\"!F(F(F(\"#Q\"\"&\"#A\"#87*F(F(\"#R\"\"%\"#B\"#9\"#D \"\"'7*F(F(F(\"#P\"#E\"#@\"#7\"#:7*F(F(\"\"$\"#SF(\"#C\"\"(\"#?7*F(F( \"#O\"#FF(\"#6\"#;\"#H7*F(\"\"#\"#TF(\"#L\"#G\"#>\"\")7*F(\"#N\"#KF(\" #5F(\"#I\"#<7*\"\"\"F(F(\"#M\"#J\"#=\"\"*F(" }}}{EXCHG {PARA 0 "" 0 " " {TEXT -1 58 " Last but not least, we can get a complete tour using t he " }{TEXT 282 10 "warnsdorff" }{TEXT -1 46 " routines. There are two versions, each using " }{TEXT 283 17 "Warnsdorff's rule" }{TEXT -1 53 ": at each stage one should make a move which has the " }{TEXT 278 6 "fewest" }{TEXT -1 101 " alternatives to choose from. Sometimes this still leaves several moves to choose from. One routine, " }{TEXT 279 10 "warnsdorff" }{TEXT -1 41 ", always chooses the the first such move :" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 16 "warnsdorff(AT);\n" } {TEXT -1 21 "(The global variable " }{TEXT 281 4 "Been" }{TEXT -1 25 " is automatically reset.)" }{MPLTEXT 1 0 12 "\ndrawtour();" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%\"#c\"#L\"#9\"#<\"#]\"#J7*\"\"\"\"#M\"\"$\"#=\"#\\\"#K\"#8\"#; " }}}{EXCHG {PARA 0 "" 0 "" {TEXT -1 21 " The second routine, " } {TEXT 284 17 "random_warnsdorff" }{TEXT -1 31 ", randomly chooses one \+ of them:" }}}{EXCHG {PARA 0 "> " 0 "" {MPLTEXT 1 0 34 "random_warnsdor ff(AT);\ndrawtour();" }}{PARA 11 "" 1 "" {XPPMATH 20 "6#%\"#A\"\"&\"#S\"\"*\"#C\"\"(7*\" #@\"\"%\"#f\"#c\"#B\"\"'\"#T\"#57*\"#=\"#d\"#?\"#R\"#g\"#j\"\")\"#D7* \"\"$\"#Q\"#`\"#i\"#b\"#U\"#6\"#k7*\"#]\"#<\"#[\"#P\"#_\"#h\"#E\"#N7* \"#J\"\"#\"#^\"#a\"#Z\"#O\"#V\"#77*\"#;\"#\\\"#K\"#H\"#9\"#X\"#M\"#F7* \"\"\"\"#I\"#:\"#Y\"#L\"#G\"#8\"#W" }}}{PARA 0 "" 0 "" {TEXT -1 0 "" } }{PARA 0 "" 0 "" {TEXT -1 3 " " }}{PARA 0 "" 0 "" {TEXT -1 58 " \+ " }{TEXT 286 11 " REFERENCES" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 33 "W.W. R. Ball and H.S.M. Coxeter, " }{TEXT 285 35 "Mathematical \+ Recreations and Essays" }{TEXT -1 32 ", 13th ed, Dover, New York, 1987 " }}{PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 0 "" }} {PARA 0 "" 0 "" {TEXT -1 0 "" }}{PARA 0 "" 0 "" {TEXT -1 20 "D. Joyner , 5-21-1996" }}}{MARK "19 0" 3 }{VIEWOPTS 1 1 0 1 1 1803 }