1
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

It is highly unlikely that there is any efficient (polynomial-time) algorithm. However, heuristic optimization techniques such as simulated annealing and tabu search will probably be able to obtain very good, if not optimal, solutions.

$\endgroup$
0
$\begingroup$

Yes, the game is solvable in the sense that an optimal move sequence can be found. This follows from the fact that there are only finitely many move sequences.

$\endgroup$
  • $\begingroup$ I mean is it solvable in a way that you visited all "positive" cells and avoided all "negative" cells? $\endgroup$ – Andrew Fount Mar 31 '16 at 12:02
  • $\begingroup$ Oh, you mean: Given a game setup as above, is there always a knight path that visits all originally positve cells exactly once and does not visit any of the originallyl negative cells? - Here the answer is of course "no". Just make all cells but two disant ones negative $\endgroup$ – Hagen von Eitzen Apr 1 '16 at 4:15
  • $\begingroup$ There is certain number of positive and negative cells. Their position is random, but their number is always the same. $\endgroup$ – Andrew Fount Apr 5 '16 at 20:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.