# Knight's Tour with Obstacles

Found a game related to knight's tour Knight's Score

The basic idea is to gather as much points as possible, avoiding some cells.

What is the math of this? Can algorithm be constructed to visit all cells except certain ones (to avoid negative values in the game)?

Is the problem always solvable?

As Hagen noted, because there are only finitely many cells and you can't visit a cell more than once, the game is finite. Thus there is a "brute-force" algorithm to find an optimal path by examining all possible paths; of course, depending on the particular instance, the optimal value may turn out to be positive, negative or zero. However, on a reasonably-sized board (the one given is $10 \times 10$) the number of possible paths is so huge that brute force is not a realistic option.