
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


 
Function KnightTour$(StartW=1, StartH=1){
    def boolean swapH, swapV=True
    if startW<=4 then swapH=true: StartW=8+1-StartW
    if startH>4 then swapV=False: StartH=8+1-StartH
    Let final=8*8, last=final-1, HighValue=final+1
    Dim Board(1 to 8, 1 to 8), Moves(1 to 8, 1 to 8)=HighValue
    f=stack:=1,2,3,4,5,6,7,8
    if 8-StartW=2 and StartH=2 then stack f {shift 1,-8}
    Function KnightMove(x,w,h) {
        a=2:b=1:z=1:p=1
        if x mod 2=1 then swap a,b
        if x>2 then p-! : if x>4 then swap z, p : if x>6 then p-!
        w+=z*a
        h+=p*b
        if w>=1 and w<=8 and h>=1 and h<=8 then =(w, h) else =(,)
    }
    For j=1 to 8 :For i=1 to 8
    s=stack
    For k=1 to 8
        m=KnightMove(stackitem(f, k),i, j)
        if len(m)>1 then Stack s {data m}
    Next : Board(i,j)=s : Next
           stack f {shift 1,-8}
    Next
    For i=1 to 8 :For j=1 to 8
    s=Board(i, j)
    if len(s)>2 then
        so=queue
        For k=1 to len(s)
            m=stackitem(s, k)
            Append so, Len(Board(m#val(0), m#val(1))) :=m
        Next
        sort ascending so as number
        s=stack
        stack s {for k=0 to len(so)-1:data so(k!):next}
        Board(i,j)=s
    end if
    Next : Next
    s= Board(StartW, StartH)
    n=0
    BackTrack=Stack
    Moves=1
    Moves(StartW, StartH)=1
    Repeat
    n++
    While n>len(s) {
        if Len(BackTrack)=0 then Print "Break", moves : Break
        Moves--
        Stack BackTrack {Read s, n}
        m=stackitem(s, n)
        Moves(m#val(0), m#val(1))=HighValue
        n++
    }
    m=stackitem(s, n)
    w=m#val(0)
    h=m#val(1)
    if Moves(w, h)>=Moves then
        if Moves<last then
        s1=Board(w, h) :ii=-1
        for i=1 to len(s1){m1=stackitem(s1, i) :if Moves(m1#val(0),m1#val(1))>moves then ii=i-1 : exit
        }
        if ii>=0 then
            Moves++
            Moves(w,h)=Moves
            Stack BackTrack {Push n, s}
            s=s1: n=ii
        end if
        else
            Moves++
            Moves(w,h)=Moves
        end if
    end if
    until Moves=final
    Document export$
    Inventory Tour
    letters=stack:="a","b","c","d","e","f","g","h"
    f=stack:=1,2,3,4,5,6,7,8
    if swapV Else stack f {Shift 1,-8}
    if swapH then stack letters {Shift 1,-8}
    For j=1 to 8:For i=1 to 8
        Append Tour, Moves(i,j) :=stackitem$(letters, i)+str$(stackitem(f, j),"")
    Next : Next
    Sort ascending Tour as number
    one=each(Tour)
    While one {
        export$=Eval$(one)
        if not one^=last then export$="->"
        If (one^+1) mod 8=0 then
        export$={
        }
        End if
    }
    =export$
}
Document ex$
ex$= {Knight's Tour from a1
}+KnightTour$()+{Knight's Tour from h1
}+KnightTour$(8,1)+{Knight's Tour from a8
}+KnightTour$(1, 8)+{Knight's Tour from h8
}+KnightTour$(8, 8)
Clipboard ex$
Report ex$
 