
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


with javascript_semantics
constant size = 8,
         nchars = length(sprintf(" %d",size*size)),
         fmt = sprintf(" %%%dd",nchars-1),
         blank = repeat(' ',nchars)
 
-- to simplify output, each square is nchars
sequence board = repeat(repeat(' ',size*nchars),size)
-- keep current counts, immediately backtrack if any hit 0
-- (in line with the above, we only use every nth entry)
sequence warnsdorffs = repeat(repeat(0,size*nchars),size)
 
constant ROW = 1, COL = 2,
         moves = {{-1,-2},{-2,-1},{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2}}
 
function onboard(integer row, integer col)
    return row>=1 and row<=size and col>=nchars and col<=nchars*size
end function
 
procedure init_warnsdorffs()
    for row=1 to size do
        for col=nchars to nchars*size by nchars do
            for move=1 to length(moves) do
                integer nrow = row+moves[move][ROW],
                        ncol = col+moves[move][COL]*nchars
                if onboard(nrow,ncol) then
                    warnsdorffs[nrow][ncol] += 1
                end if
            end for
        end for
    end for
end procedure
 
atom t0 = time(),
     t1 = time()+1
integer tries = 0 
function solve(integer row, integer col, integer n)
    if time()>t1 and platform()!=JS then
        ?{row,floor(col/nchars),n,tries}
        puts(1,join(board,"\n"))
        t1 = time()+1
    end if
    tries+= 1
    if n>size*size then return 1 end if
    sequence wmoves = {}
    integer nrow, ncol
    for move=1 to length(moves) do
        nrow = row+moves[move][ROW]
        ncol = col+moves[move][COL]*nchars
        if onboard(nrow,ncol)
        and board[nrow][ncol]=' ' then
            wmoves = append(wmoves,{warnsdorffs[nrow][ncol],nrow,ncol})
        end if
    end for
    wmoves = sort(wmoves)
    -- avoid creating orphans
    if length(wmoves)<2 or wmoves[2][1]>1 then
        for m=1 to length(wmoves) do
            {?,nrow,ncol} = wmoves[m]
            warnsdorffs[nrow][ncol] -= 1
        end for
        for m=1 to length(wmoves) do
            {?,nrow,ncol} = wmoves[m]
            integer scol = ncol-nchars+1
            board[nrow][scol..ncol] = sprintf(fmt,n)
            if solve(nrow,ncol,n+1) then return 1 end if
            board[nrow][scol..ncol] = blank
        end for
        for m=1 to length(wmoves) do
            {?,nrow,ncol} = wmoves[m]
            warnsdorffs[nrow][ncol] += 1
        end for
    end if
    return 0
end function
 
init_warnsdorffs()
board[1][nchars] = '1'
if solve(1,nchars,2) then
    puts(1,join(board,"\n"))
    printf(1,"\nsolution found in %d tries (%3.2fs)\n",{tries,time()-t0})
else
    puts(1,"no solutions found\n")
end if
