8
$\begingroup$

Here's a map:

Map game

How to play

Legend:

(◾) = Start point

★ = Objective

⚑ = End point

Mission: Collect all the objectives and go to the end with the minimum count of steps.

How the game works:

• The pawn counts its steps that are incremented by the number contained in the boxes it moves on, every box can be walked multiple times.

• The pawn can switch platform, but it has to move only with adiacent platforms, as indicated in gray boxes (the passage of which does not involve further steps).

• The pawn can't stay more than one move out of a platform (this means that it is not possible to cross 2 gray squares consecutively).

• It is not a problem to cross an entire platform (i.e. both boxes of it).

Good luck!

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ To clarify, if I move down two boxes (starting from the start point), will that be a count of only 5 steps? Or is it 7 since it took 2 steps to get to the next box + increment of 5 in the previous box? $\endgroup$
    – oAlt
    Commented May 2, 2020 at 3:16
  • 1
    $\begingroup$ As indicated in How the game works: [...] gray boxes (the passage of which does not involve further steps), you have to count only the numbers contained in the azure boxes $\endgroup$
    – xKobalt
    Commented May 2, 2020 at 9:36
  • 1
    $\begingroup$ Ah, I see. Thx :0 $\endgroup$
    – oAlt
    Commented May 2, 2020 at 9:40

3 Answers 3

Reset to default
4
$\begingroup$

Indeed it can be solved as a traveling salesman problem on 13 nodes, but brute force is not required. First define an undirected graph with 145 nodes, one per box, with an edge between each pair of horizontally or vertically adjacent boxes (unless both are gray). Define each edge weight to be the average of the numbers of its two incident nodes. Now solve a shortest path problem for each pair of start point, objective, or end point. The resulting shortest path distances $d_{i,j}$ are: \begin{matrix} i\backslash j &13 &20 &52 &65 &68 &76 &101 &106 &132 &142 &145\\ \hline 1 &43 &16 &38 &13 &27 &19 &26 &41 &31 &33 &43 \\ 13 &&33 &5 &56 &16 &52 &35 &10 &39 &16 &13 \\ 20 &&&28 &29 &17 &31 &26 &31 &31 &23 &33 \\ 52 &&&&51 &11 &47 &30 &5 &34 &11 &8 \\ 65 &&&&&40 &6 &22 &51 &19 &41 &51 \\ 68 &&&&&&39 &22 &14 &26 &15 &17 \\ 76 &&&&&&&22 &46 &13 &36 &46 \\ 101 &&&&&&&&29 &11 &19 &29 \\ 106 &&&&&&&&&33 &10 &5 \\ 132 &&&&&&&&&&23 &33 \\ 142 &&&&&&&&&&&10 \end{matrix} Now add a dummy node 146 that is adjacent only to the start point 76 and end point 106, with $d_{76,146} = d_{106,146} = 0$. This is a standard trick to convert a TSP path problem with specified start and end points into a TSP tour problem. Finally, solve the TSP on these 13 nodes, yielding optimal tour with edges $$(1,20),(20,68),(13,68),(13,52),(52,142),(142,145),(106,145),(106,146),(76,146),(76,132),(101,132),(65,101),(1,65)$$ and total cost

$139$, as found by @DanielMathias. Here is a plot, omitting the two dummy edges: enter image description here

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ I needed some time to understand this solution, I can say that is the best not only for effectiveness, but also for explanation, for this reason I decided to accept your answer, congratulations :) $\endgroup$
    – xKobalt
    Commented May 4, 2020 at 11:31
3
$\begingroup$

I got to this point after 5 attempts. My score is:

156 steps

Here's my route:

Improve this answer
$\endgroup$
3
  • 1
    $\begingroup$ It's a nice attempt, however at the moment I'm looking for the best solution, I want to see if it is possible to find a more effective one $\endgroup$
    – xKobalt
    Commented May 2, 2020 at 10:15
  • 3
    $\begingroup$ This seems to be the Travelling Salesman problem, and as such, it's NP-hard, so I don't think anything less than a full brute-force solution can provide a conclusive answer. $\endgroup$
    – Bass
    Commented May 2, 2020 at 10:54
  • $\begingroup$ @Bass That's not accurate. The Travelling Salesman requires a return to home. This can be modelled as a Minimum Cost Flow $\endgroup$
    – LeppyR64
    Commented May 2, 2020 at 13:46
2
$\begingroup$

Score:

139

Route:

 . . . D x x x . . . . . . . . . . . H | #-A= 13
 . . . x . . x . E . . . . . . . . . x | A-B= 11
 . . . x . . x x x . . . . . . . . . x | B-C= 22
 . . x x . . . . x . . . . . . . G x x | C-D= 13
 . . x . . . . . x . . . . . . . x . . | D-E= 16
 . . C . . . . . x . . F x x x x x . . | E-F= 17
 # . x x x x . . x . . x . . x x x . . | F-G= 11
 x . . . . x . . x x x x . . x . . . . | G-H=  5
 x . . x x x B . . . . . . x x . x # . | H-I= 16
 x . . x . . . . . . . . . x . . x . . | I-J= 10
 x . . x . . . . . . . x x x x x x . . | J-#=  5
 x A x x . . . . . . . I . . . . x x J | #-#=139

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ The text rendering should be sufficient, but I would prefer to have an image here... hint hint $\endgroup$
    – Daniel Mathias
    Commented May 2, 2020 at 12:42
  • $\begingroup$ After a few minutes, I can say that the path is correct and it's actually a better solution. At the moment, I'm anyway open to better answers $\endgroup$
    – xKobalt
    Commented May 3, 2020 at 13:21

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