Knight's tour — backtracking

The knight must visit every square exactly once. At a dead end, the algorithm backtracks and tries another route.

    \begin{algorithm}
    \caption{KnightsTour}
    \begin{algorithmic}
    \FUNCTION{KnightsTour}{square, visited}
        \IF{all squares are visited}
            \RETURN true
        \ENDIF
        \FOR{each legal unvisited knight move $next$}
            \STATE $visited[next] \gets true$
            \IF{KnightsTour(next, visited)}
                \RETURN true
            \ENDIF
            \STATE $visited[next] \gets false$
        \ENDFOR
        \RETURN false
    \ENDFUNCTION
    \end{algorithmic}
    \end{algorithm}