Given knight tour graph $G$ ($8 \times 8$ nodes) and a set of nodes $\{ v_{1}, v_{2}, \dots, v_{n} \} = V \subset V(G)$, find a minimal length tour in $G$ that visits all nodes from $V$ (maybe others too). Each $v \in V$ must be visited exactly once.

We suppose that the graph is unweighted, so tour's length is the same as its edge count.


It comes to mind that we would try to find the shortest path between $v_{1}$ and $v_{2}$, then between $v_{2}$ and $v_{3}$, and so on. Is it true that combining these shortest paths will give the desired tour?

  • $\begingroup$ Your question is not clearly defined because the number of shortest paths between two consecutive vertices is not one, i.e., there are multiple paths. So do you mean to ask "can I take any shortest path between two consecutive vertices and get an optimal tour"? $\endgroup$ – Juho Feb 23 at 19:13
  • $\begingroup$ @Juho, for a start, it's better to consider easier problem - find any shortest tour (so, it doesn't matter which shortest path between consecutive vertices we take). $\endgroup$ – Elman Feb 23 at 19:34
  • $\begingroup$ The answer should be no, and it's probably the easiest to just code this up to see it. $\endgroup$ – Juho Feb 25 at 12:09
  • $\begingroup$ Backtracking comes to mind (just like for finding a tour). $\endgroup$ – vonbrand Feb 29 at 0:40

Your Answer

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

Browse other questions tagged or ask your own question.