
Task
Problem: you have a standard 8x8 chessboard, empty but for a single knight on some square. Your task is to emit a series of legal knight moves that result in the knight visiting every square on the chessboard exactly once. Note that it is not a requirement that the tour be "closed"; that is, the knight need not end within a single move of its start position.

Input and output may be textual or graphical, according to the conventions of the programming environment. If textual, squares should be indicated in algebraic notation. The output should indicate the order in which the knight visits the squares, starting with the initial position. The form of the output may be a diagram of the board with the squares numbered according to visitation sequence, or a textual list of algebraic coordinates in order, or even an actual animation of the knight moving around the chessboard.

Input: starting square

Output: move sequence



Related tasks
 A* search algorithm
 N-queens problem
 Solve a Hidato puzzle
 Solve a Holy Knight's tour
 Solve a Hopido puzzle
 Solve a Numbrix puzzle
 Solve the no connection puzzle


   // Use Warnsdorff's rule to perform a knights tour of a 8x8 board in 
   // linear time.
   // See Pohl, Ira (July 1967), 
   //   "A method for finding Hamilton paths and Knight's tours"
   //   http://portal.acm.org/citation.cfm?id=363463
   // Uses back tracking as a tie breaker (for the few cases in a 8x8 tour)
class Board{
   var[const]deltas=[[(dx,dy); T(-2,2); T(-1,1); _]].extend(
                    [[(dx,dy); T(-1,1); T(-2,2); _]]);
   fcn init{
      var board=L();
      (0).pump(64,board.append.fpM("1-",Void)); // fill board with Void
   }
   fcn idx(x,y)     { x*8+y }
   fcn isMoveOK(x,y){ (0<=x<8) and (0<=y<8) and Void==board[idx(x,y)] }
   fcn gyrate(x,y,f){   // walk all legal moves from (a,b)
      deltas.pump(List,'wrap([(dx,dy)]){
         x+=dx; y+=dy; if(isMoveOK(x,y)) f(x,y); else Void.Skip 
      });
   }
   fcn count(x,y){ n:=Ref(0); gyrate(x,y,n.inc); n.value }
   fcn moves(x,y){ gyrate(x,y,fcn(x,y){ T(x,y,count(x,y)) })}
   fcn knightsTour(x=0,y=0,n=1){  // using Warnsdorff's rule
      board[idx(x,y)]=n; 
      while(m:=moves(x,y)){
         min:=m.reduce('wrap(pc,[(_,_,c)]){ (pc<c) and pc or c },9);
	 m=m.filter('wrap([(_,_,c)]){ c==min });  // moves with same min moves
	 if(m.len()>1){ // tie breaker time, may need to backtrack
	    bs:=board.copy();
	    if (64==m.pump(Void,'wrap([(a,b)]){
	       board[idx(a,b)]=n;
	       n2:=knightsTour(a,b,n+1);
	       if (n2==64) return(Void.Stop,n2); // found a solution
	       board=bs.copy();
	    })) return(64);
	    return(0);
         }
	 else{
	    x,y=m[0]; n+=1;
	    board[idx(x,y)]=n; 
	 }
      } //while
      return(n);
   }
   fcn toString{ board.pump(String,T(Void.Read,7),
         fcn(ns){ vm.arglist.apply("%2s".fmt).concat(",")+"\n" });
   }
}