The Knight’s Tour In 3-Dimensional Chess - SAS

The Knight’s Tour – Implementing a Heuristic Solution, continuedSOLUTION #2 – THE “GLUE” METHODAnother proposed solution, discovered during the research for this paper, is calledthe “Glue” method, which requires a closed tour, that is, the start and end positions of thetour are one knight move away. Table 4 displays two Knight’s Tours using Warnsdorff’smethod, a closed tour where Steps #1 and #64 are one move from each other and an opentour where Steps #1 and #64 are not, yet still a valid tour.Closed 95433621Open 63231h53419583321764Table 4. A closed knight’s tour and an open knight’s tour.This method seems more like cheating because it does little more than clone anexisting closed tour: it does not truly generate a knight’s tour. Instead, the processrecodes the numerical sequence (i.e. steps) in the tour based on the last step and thesubsequent legal move to the next board. So, given a closed tour, how does it recode thesequence of values? First of all, it must discern a legal move with respect to 3-D chess. Forexample, as shown in Table 5, the knight can move from Board #1, Position b3, to Board#2, Position d3, which denotes the knight’s move on the next board, followed by twosquares in perpendicular fashion. There are other possible moves, but for this discussion,the point is to illustrate the cloning process.As shown in Table 5, Position d3 on Board #1 denotes Step #58 (the array elementboard{6,4}), which becomes the pivotal value for the cloning process. Because of aninherent property of a closed tour, it is possible to recode the Step values by computing twoincremental values using the following formulas: INCR1 MAX(of board{*}) – board{6,4} 1 INCR2 MAX(of board{*}) – board{6,4} 65 Board #1: Initial (Closed) 3601530g26234492813421164 – 58 76 65 71Board #2: Successive Tourh458272441102914abcd8 91 76 109 1187 108 121 92 776 75 90 127 1225 126 107 120 1034 89 74 125 683 106 71 104 652 73 88 69 1241 70 105 72 87e931101191281231028366fgh78 97 116117 94 7996 115 98111 80 95114 99 11267 84 8186 113 100101 82 85Table 5. An initial closed knight’s tour and its successor beginning at a proper starting position.6

The Knight’s Tour – Implementing a Heuristic Solution, continuedFollowing the example in Table 5, the variables INCR1 and INCR2 will have the values 7 and71, respectively. Then, simply traverse the first tour (matrix) and increment accordingly,that is, pivoting on the value 58. Thus, steps ranging from 58 to 64 are incremented by 7,thereby ranging from 65 (which is the first step on the successive board) to 71; whereas,those steps below Step #58 are incremented by 71. Thus, Steps #1 through #57 will rangefrom 72 to 128, as shown in Example #1 of Table 6. And, it works!Even more ironic concerning this method – Given a closed tour, Examples 2 and 3 inTable 6 illustrate that any position can be selected as the pivotal position for the recodingprocess, albeit not following the rules for 3-D chess. Also, notice that the result is alwaysanother closed tour.Although the implementation emulates the Solution #1 using the KNIGHTMOVESdata set and the heuristic rule, it is necessary to designate the starting position (row,column) knowing that the result will be a closed tour. Then, the %glue macro generatesthe subsequent tour by transforming the values of the first (closed) tour into a new Knight’sTour.Board #1: (Closed) 3601530Board #2: Example #1g262344928134211h458272441102914abcd8 91 76 109 1187 108 121 92 776 75 90 127 1225 126 107 120 1034 89 74 125 683 106 71 104 652 73 88 69 1241 70 105 72 87Board #2: Example #2e931101191281231028366fgh78 97 116117 94 7996 115 98111 80 95114 99 11267 84 8186 113 100101 82 85Board #2, Example #3abcdefgh8 89 74 107 116 91 76 95 1147 106 119 90 75 108 115 92 776 73 88 125 120 117 94 113 965 124 105 118 101 126 109 78 934 87 72 123 66 121 112 97 1123 104 69 102 127 100 65 82 792 71 86 67 122 81 84 111 981 68 103 70 85 128 99 80 8387654321a10412188751021198683bcdef89 122 67 106 9170 105 90 123 66103 76 71 68 109120 69 116 77 12487 74 81 72 12784 117 78 115 80101 82 73 96 99118 85 100 79 e 6. A closed knight’s tour with three successive closed tours.The %glue macro, shown below, obtains the Step-value of the knight’s nextposition, generates a new tour using the “Glue” method, then displays the new tour.%macro glue(board,r,c);%* Obtain Step-value of the knight’s next position ;;data null ;retain r &r. c &c.;array board{8,8} s11-s18 s21-s28 . . . s81-s88set board%eval(&board.-1);call 7

The Knight’s Tour – Implementing a Heuristic Solution, continued%* Generate new tour by “Glue” method ;;data board%eval(&board. 1);retain &svars. &mvars. pval &pval. incr1 incr2;array board{8,8} &svars.;set board%eval(&board.-1); Process previous tour.if n eq 1then do; L.T. and G.E. Pivotal valueincr1 max(of board{*}) - board{&r.,&c.} 1;incr2 max(of board{*}) - board{&r.,&c.} 65;end;do r 1 to 8; Recode board, accordingly.do c 1 to 8;if board{r,c} ge &pval.then board{r,c} board{r,c} incr1;else board{r,c} board{r,c} incr2;end;end;drop r c incr1 incr2 pval;run;%* Display the new tour ;;%ShowBoard(dsn board%eval&board.,elements &svars.,title Knights Tour on Board #%eval(&board. 1));%mend glue;Table 8 shows a closed tour beginning on Board #1, Position b1. As an exercise for thereader, formulate the successive tour (i.e. Board #2) using the following criteria: PivotalValue 60, INCR1 5, and INCR2 69. Keep in mind that the Pivotal Value wasdetermined by the rules of 3-D chess; whereas, the incremental variables were computedusing formulas.Board #1: (Initial Closed 32475653g728111449543916Board #2 (Next Tour)h101382938154855abc8 94 91 747 73 104 956 90 93 1145 113 72 1274 128 89 1203 71 112 672 88 65 1101 111 70 87d103921051001151266966e96751021196812186109fgh81 76 7978 97 8299 80 77106 83 98101 118 107116 123 84125 108 117122 85 124Table 7. Board #2 created from Board #1 using Step #60 (Position b2) as the pivotalvalue.SOLUTION #3 – TRAVERSING THE BOARDS DURING THE TOURThe first two solutions produce valid tours, albeit in a limited way. The first solutionmerely extended Warnsdorff’s heuristic rule by generating tours independently for eachboard, then moving the knight to a successive board according the rules of 3-D chess andfinding the next tour. The second solution, the so-called “Glue” method, is a scheme torecode a given closed tour in order to produce a new tour. It does not generate a Knight’s8

The Knight’s Tour – Implementing a Heuristic Solution, continuedTour from scratch. The “Glue” method is little more than an isomorphism – and a sham.Neither solution generates the Knight’s Tour as one might imagine, that is, traversingseveral chess boards during the tour.The proposed solution takes Warnsdoff’s heuristic rule to new heights. The idea isthe same: creating and updating the KNIGHTMOVES data set in tandem with the heuristicrule for discerning the next knight move. However, this time the number of possible movesrepresents three chess boards, not just one. In this situation, it is necessary to know apriori the number of possible knight moves from any of 192 possible squares (i.e. 3chess boards each having 64 squares), because now there is a third factor called the Level:Board #1, #2, and #3.Table 8 displays the three boards in juxtaposition and includes several examples ofhow the knight moves from its initial position to all possible moves. The coding conventionclearly indicates rows 1 through 8 and columns a through h that facilitates enumerating thepossible moves. Keep in mind the rules for 3-D chess.Board #1From PositionBoard #2# PossibleMovesBoard #3-------------------- To Position --------------------Board #1Board #2Board #3Board #1 / Position a86Board #2 / Position d5 16b6, c7b5, f5, d7, d3Board #3 / Position b3 10b2, b4, c3a6, c8b4, b6, c3, c7,e3, e7, f4, f6b1, b5, d3a7, b8b5, f5, d7, d3a1, a5, c1, c5,d2, d4Table 8. Listing of possible knight moves.Consider the following important points before proceeding:1. The Knight’s Tour is displayed as a sequence of integers, ranging from 1 to 192.Theoretically, for example, Step #1 begins at Board #1, Position a8 and Step#192 lands on Board #3, Position e1.2. Using three boards, the knight’s second step depends on its initial step, that is,whether the piece moves one or two levels will depend on its initial location. Forexample, the knight cannot jump two levels if it resides initially on the middlechess board, since there are only three boards.9

The Knight’s Tour – Implementing a Heuristic Solution, continued3. The number of possible moves for the knight ranges from 6 to 16 (See Table 9),which is significantly more than the Knight’s Tour problem using a single board.4. When moving to another board, the knight lands on the same-named square(e.g. a8 on one board moves to a8 onto another board) before moving to its finaldestination, accordingly.5. If the initial move begins from Board #2, the knight can move only one level.6. Obviously, the move must be legal and the knight remains on the board.The first task is to calculate the number of possible knight moves from any square onany board, as shown in Table 9. This information would be stored in a data set calledKNIGHTMOVES, which becomes the only input to the proposed SAS solution, implementedas a 3-dimensinal array, called the MOVES matrix. The knight begins its tour from a givenstarting position, seeks the most reasonable next move, and then updates the MOVESmatrix, by decrementing by 1 those places where the knight could go from the new position.The objective is to create a data set that contains 1 observation having 192 variableswhose naming convention intuitively indicates a 3-dimensional array denoting the LEVEL,ROW, and COLUMN. These m-variables (m denotes MOVES) contain the number of possiblemoves from all 192 positions. The abridged Data step below uses three DO-loops toaddress each element in the 3-dimensional - moves{level,r,c}.In order to count the number of possible knight moves, we first focus on the boardwhere the knight resides; thereby considering the traditional L-shaped movements, whichare implemented using two DO-loops and their respective loop control variables: STEP1 andSTEP2. Given that the step is legal, the COUNTER variable is incremented. Then, in orderto count the possible moves onto the other boards, from the same location, there are onlytwo scenarios:1. The knight jumps to the next board, then moves TWO squares in aperpendicular fashion.2. The knight jumps to the second board, then moves ONE square inperpendicular fashion.If the knight resides on level 1 or 3, then both scenarios prevail; however, if the knightresides on level 2, then only the first scenario prevails. Of course, the move must be legalin order to increment the COUNTER.data knightmoves;One observation, keeping only the M-variables.array moves{3,8,8} m111-m118 . . m188 m211-m218 . . m288m311-m318 . . m388;do level 1 to 3;Process all three 8x8 boards.do r 1 to 8;do c 1 to 8;For a given knight position {r,c}.counter 0;Initialize the counter to zero.Knight moves in L-shaped fashion. If legal move then increment counter.select(level);Knight moves one level or two levels.when(1,3)If legal move then increment counter.when(2)If legal move then increment counter.end;moves{level,r,c} counter;Assign # possible moves.end; end; end;run;10

The Knight’s Tour – Implementing a Heuristic Solution, continuedBoard 161310Board 012161616161210f1012161616161210Board 1010101086Table 9. The KNIGHTMOVES metadata for three chess boards. Notice the symmetry.Solution #3 is implemented as a single macro with no parameters. It is designed totraverse all 192 squares in search of the Knight’s Tour, starting from each position. Thislengthy macro follows the same approach of utilizing the KNIGHTMOVES data set andmoving the knight on the board where it resides, then considering the other levels,accordingly. Thus, for a given starting position (Level, Row, Column), a Data step attemptsto generate the Knight’s Tour by initializing the BOARD 3-dimensional matrix with the value1 (denoting Step #1) then traversing the matrix to determine the position of Step #2, andso on. The Data step considers the L-shaped moves on the board where the knight resides,obtaining the “minimal degree” in accordance to the heuristic rule, then considers the 3-Dchess moves to the other boards, likewise. Depending on the level where the knightresides will determine the subsequent checks in search of the “minimal degree.”The following Data null step determines whether the attempt to formulate theKnight’s Tour was successful. If so, then a 3-D version of the %showboard macrogenerates the report. Table 10 shows an example of a successful and a failed tour, thelatter tour getting stuck at Step #189.data null ;array board{3,8,8} s111-s118 s181-s188 s311-s318 s381-s388;set solution;call symput('solved',left(put(n(of board{*}) eq 192,1.)));run;Successful Knight’s TourFailed Knight’s TourBoard #187654321abcde24 29 26 21 4631 22 81 74 8380 73 100 105 18069 104 141 156 18318 101 146 173 192103 68 153 184 15910 17 128 145 17438 27 12 63 56f3510615713618518217725Board #1gh40 4347 38118 107181 48158 119135 8662 911078765432111abcdef23 16 41 32 91 7218 31 90 83 88 7713 40 109 102 115 13630 101 114 137. 17435 108 103 177 139.100 55 138 186 185 1787 52 107 104 176 162296 121 146 157g659287128161175145148h70637413586129154143

The Knight’s Tour – Implementing a Heuristic Solution, continuedBOARD #287654321BOARD #2abcd27 20 55 3454 33 76 11519 96 111 7832 77 148 11395 112 127 144147 142 1491 94 15 1786 132 09 3684 49139 12058 85123 138160 59175 12260 2571081331861691246587654321BOARD #387654321abc30 25 2823 52 7170 79 9853 72 131102 97 1545 130 14716 11 12694 129a142134251257365bcde33 22 27 6026 59 78 4515 46 111 9658 97 164 12751 110 119 17038 123 98 16511 118 169 14056 37 10 60182172155158h64758067134159144149BOARD ble 10. A successful tour and a failed tour (stopping at step #189).FOUR CHESS BOARDSWarnsdorff heuristic rule works for a single chess board and three chess boards, thelatter adhering to 3-D chess rules. What about four chess boards? Is Warnsdorff’s heuristicrule strong enough? It turns out – Yes! Not surprisingly, however, the 4-board solutionrequires a fresh study of how the knight moves between 4-boards. For example, if theknight sits on Board #1, it cannot legally jump to Board #4; that is, it must first jump toeither Board #2 or Board #3 during the tour in order to get to Board #4, which must beincluded as part of the solution. Hence, one might think that this hurdle would make theheuristic rule too weak or biased. Surprisingly, the rule was able to generate 38 tours outof a possible 256 tours; a 46.9% success rate, rather impressive. Also, adding a fourthlevel affects the logic concerning the creation of the KNIGHTMOVES data set. In this case,all four levels must consider perpendicular moves both one step and two steps, unlike the 3board problem. The code below highlights the portion where the knight is moving to anotherboard to discern a legal move in order to increment the COUNTER variable.data knightmovesarray moves{4,8,8} %gen vars(m,4);do level 1 to 4;do r 1 to 8;do c 1 to 8;counter 0;Consider L-shaped moves where the knight resides (not shown).Consider knight moves to the other levels using SELECT/WHEN.select(level);when(1,2,3,4) do;do step2 -2,2;if 1 le (r step2) le 812then counter 1;

The Knight’s Tour – Implementing a Heuristic Solution, continuedif 1 leend;do step2 if 1 leif 1 d;keep m:;run;(c step2) le 8then counter 1;-1,1;(r step2) le 8(c step2) le 8then counter 1;then counter 1; counter;It is interesting to note that the MOVES matrix for 4-boards contains the samevalues for each level, as shown in Table 11, which makes sense because each levelmanifests the same movements on their respective boards, as well as to other appropriateboards. For example, the value of the array element moves{n,3,4} (Position d4 in chessnotation) indicates 16 possible moves regardless of which level the knight resides initially.Boards #1 and 10Boards #2 and 61210h81013131313108Table 11. Possible knight moves for four boards.The solution to the 4-board problem consists of a lengthy Data step (not shown)because of all the steps the knight might consider during the tour. The method is the sameas Solution #3, just more involved. The Knight’s Tour, shown in Table 12, begins at Board#1, Position e8. As mentioned previously, the Steps: 1, 64, 65, 128, 129, 192, 193, 256are highlighted in red in order to facilitate reading the tour. Notice that the knight’smovement traverses all four boards, almost immediately. For example, Step #2 to Step#3: the knight moves from Board #2 to Board #4. Although the integer values indicatehigher values in Board #4, the knight’s tour shown below is valid.13

The Knight’s Tour – Implementing a Heuristic Solution, continuedBoard #1Board #2abcdefg8 81 88 85 1181 10 137 86 95 124 109 120 117 226 125 108 201 160 169 158 735 176 131 178 185 200 151 1444 91 196 199 202 179 172 393 130 175 184 197 194 143 682 55 52 195 138 171 40 711 50 57 104 43 140 135 64h611202372313829abcde8 84 77 80 111 987 79 110 121 116 1556 92 161 154 157 1485 129 192 183 166 1534 162 107 164 173 1703 49 132 193 182 1652 60 163 106 133 1021 47 44 61 136 105Board 79412320418919810346fgh529150 994115 18 25156 149 100147 114 19152 101 28137 34 4142 67 32Board g112775 14146 113167 74142 145181 36134 6365 9210227252255246207218gh163225 26242 17209 226206 243217 208244 3335 66Table 12. The Knight’s Tour using four chess boards. Steps #1, 64, 65, 128, 129, 192,193, and 256 are highlighted in red to facilitate reading the tour

Three dimensional chess typically uses three chess boards such that a chess piece can traverse the several boards according to the rules for that piece. For example, the knight can remain on the board where it resides or move to another successive board, then move in a perpendicular fashion. In three-dimensional chess, the Knight’s Tour is a