# What is the minimum count of steps required to complete this dominoes maze?

Here's a map:

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!

• 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? – oAlt May 2 '20 at 3:16
• 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 – xKobalt May 2 '20 at 9:36
• Ah, I see. Thx :0 – oAlt May 2 '20 at 9:40

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:

• 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 :) – xKobalt May 4 '20 at 11:31

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

156 steps

Here's my route:

• 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 – xKobalt May 2 '20 at 10:15
• 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. – Bass May 2 '20 at 10:54
• @Bass That's not accurate. The Travelling Salesman requires a return to home. This can be modelled as a Minimum Cost Flow – LeppyR64 May 2 '20 at 13:46

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

• The text rendering should be sufficient, but I would prefer to have an image here... hint hint – Daniel Mathias May 2 '20 at 12:42
• 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 – xKobalt May 3 '20 at 13:21