Мисля, че не е безкраен цикъла, просто изчисляваш ходове, които вече си ги изчислил. Преди рекурсивните колове казваш, че си посетил, като приключиш - размаркираш. Супер, обаче има шанс да попаднеш на същия sequence втори път, от другаде.

Т.е. това маркиране като посетени важи само за текущия сикуенс, но не и за друг. Ако друг сикуенс хитне част от този - ще се наложи да го изчислиш целия.

Освен пазенето на bool visited[x,y], според мен трябва и да пазиш в някакъв масив ходовете от тоя пойнт, до където може да се стигне и евентуално има ли изход. За да може като стъпнеш на полето 4,5 например и преди си изчислиш че от него до края има 600 хода, които водят до нищо. Запиши си го това и когато втори път хитнеш 4,5 да знаеш че няма смисъл например, или ако има смисъл да прибавиш ходовете, които си записал и да продължиш от там от където може.

Според мен задачката трябва да може да се реши линейно, докато твоя код го пуснах с едно принтене в началото на функцията където инкрементирам една глобална променлива, точно преди да почна да пиша този пост и в момента е на 730 000 извиквания на функцията и има мегдан да продължава доста.

Не ти трябва рекурсия ти имаш краен брой стъпки N*N-1 демек всичко може да стане с един прост цикъл. Хвърлих едно око на кода, но не можах да схвана логиката добре, ако искаш обясни с два три реда :) 

Това е моето решение (не че много се чете) :)

https://github.com/IvanMladenov/Algorithms/blob/master/GreedyAlgorithms/KnightsTour/Program.cs

Оставям и моето решение с малко по-ООП подход: https://pastebin.com/9RHtivQJ