i have ben thinking about this problem for a few weeks now, here is the problem:

given a grid of size n x n and T ammount of starting and ending positions in the grid, for each position determine if its possible to start from the starting position, visit all vertex in the grid exactly once, and finish in the finishing position

for example: n=4, t=3 start=(1,1), end=(4,4)

start=(1,1), end=(3,2)

start=(1,2) end=(2,1)

answer shound be yes,yes,no

(N<=10), (T<=20)

how to solve this problem? i could only think of pruned recursive backtracking (if the current vertex is pos, next vertex we visit is x, check if the degree of adjacent unvisited vertex (other then x), and reduce them by 1, if any of them is less then 2 (less then 1 for target vertex), then we cannot visit x next).