{ Knight Tour : obligatory problem for all logic languages. The "Knight's Tour" is an ancient puzzle in which the object is to move a knight, starting from any square on a chess board, to every other square, landing on each square only once. The code shown here works on a chess board of size n x m, with the knight initially placed at any row and column. A sample query for an 8x8 chesboard and the knight at upper left corner would be: all KnightTour(8,8,0,0) The number of solutions obviously depends on the chesboard dimensions. Interestingly, it also depends on the knight's initial position. We found over 50000 solutions in about 2 hours running as an idle thread on an Athlon XP 1600+. This is just a tiny fraction of all possible solutions. As far as we can tell, the exact number of solutions is not known, but is estimated to be more (possibly WAY more) then 122,802,512. The solutions come in bunches, so there may be long periods between solutions. The code shown is very simple and relies on the fact that any "illegal" move results in a backtrack, thus forcing another move and so on, until eventually the move is not illegal. Illegal moves are all those that would leave the chessboard or would land on a previously visited place. This is one solution: 1 8 11 16 3 18 13 64 10 27 2 7 12 15 4 19 53 24 9 28 17 6 63 14 26 39 52 23 62 29 20 5 43 54 25 38 51 22 33 30 40 57 42 61 32 35 48 21 55 44 59 50 37 46 31 34 58 41 56 45 60 49 36 47 } local Board = [0..]->[0..]->I pred KnightTour(rows:<[1..], columns:<I[1..], startrow:<I, startcol:<I) iff pos:.Board & Dupl(rows,Dupl(columns,0),pos) & //Intialize all position as 0 (not visited) pos (startrow,startcol) := 1 & //First step is placing the knight at (startrow,startcol) KnightTour1(pos,startrow,startcol,2) & //Calculate the rest of the steps (starting at step 2) PrintFormattedSolution(pos,0) //Simple formatted printout of the solution // (starting at row 0) local pred KnightTour1(pos:.Board,row:<I,col:<I,step:<I) iff if step <= Len(pos)*Len(pos(0)) then // there are Rows x Columns possible moves MoveKnight(row,col,newrow,newcol) & // If the position is not visited yet, we'll assign the step number to it. // (Otherwise the test for position = 0 fails and forces a backtrack) // If the newcol, newrow are outside the chessboard, we'll get a backtrack as well. pos(newrow,newcol) = 0 & // If we got here, then the newcol,newrow are on the chessboard ande were never visited. // So we mark the plase as visited and continue with trying to find the next move pos(newrow,newcol) := step & KnightTour1(pos,newrow,newcol,step+1) end local pred MoveKnight(row:<I,col:<I,newrow:>I,newcol:>I) iff // Given a knight at position row,col (marked 'k'), the knight can // move to eight different places: // // +---+---+---+---+---+---+---+---+ // | | | | | | | | | // +---+---+---+---+---+---+---+---+ // | | | | | | | | | // +---+---+---+---+---+---+---+---+ // | | | 7 | | 6 | | | | // +---+---+---+---+---+---+---+---+ // | | 8 | | | | 5 | | | // +---+---+---+---+---+---+---+---+ // | | | | k | | | | | // +---+---+---+---+---+---+---+---+ // | | 1 | | | | 4 | | | // +---+---+---+---+---+---+---+---+ // | | | 2 | | 3 | | | | // +---+---+---+---+---+---+---+---+ // | | | | | | | | | // +---+---+---+---+---+---+---+---+ // We don't use any strategies here, just generate all possible moves. newcol = col - 2 & newrow = row + 1 | // 1 newcol = col - 1 & newrow = row + 2 | // 2 newcol = col + 1 & newrow = row + 2 | // 3 newcol = col + 2 & newrow = row + 1 | // 4 newcol = col + 2 & newrow = row - 1 | // 5 newcol = col + 1 & newrow = row - 2 | // 6 newcol = col - 1 & newrow = row - 2 | // 7 newcol = col - 2 & newrow = row - 1 // 8 // Print the double array "pos" as a matrix of M rows by N columns, with each position // formatted to two digits (no leading zeros) local pred PrintFormattedSolution(pos:.Board,row:<I) iff if row < Len(pos) then Print('\n') & PrintOneRow(pos(row),0) & PrintFormattedSolution(pos,row+1) end local proc PrintOneRow(r:<[0..]->I,col:<I) iff if col < Len(r) then if r(col) < 10 then Print(' ') end & Print(r(col),' ') & PrintOneRow(r,col+1) end

*This page was created by F1toHTML*