Efficient Mowing at PSE

Question

Your task:
Find the most efficient mowing path around the dark green bushes that mows (passes over) all of the grass (light green).

---

For those who cannot view the image above, there are 9 rows of 16, as follows:

 - dark squares signify grass
 - stars signify bushes  

■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■  
■ * * * * ■ ■ * * * ■ * * * * ■  
■ * ■ ■ * ■ * ■ ■ ■ ■ * ■ ■ ■ ■  
■ * ■ ■ * ■ ■ * ■ ■ ■ * ■ ■ ■ ■  
■ * ■ * * ■ ■ ■ ■ ■ ■ ■ ■ * * ■  
■ * ■ ■ ■ ■ ■ ■ * ■ ■ * ■ ■ ■ ■  
■ * ■ ■ ■ ■ ■ ■ ■ * ■ * ■ ■ ■ ■  
■ * ■ ■ ■ ■ * * * ■ ■ * * * * ■  
■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■ ■  

---

Rules:

1. The mower can move only horizontally and vertically.
2. "Efficient" means the fewest number of total moves made.
3. You can start from any square you pick.
4. You must stay in bounds and cannot mow over, under, or through any bushes.

"Efficient" can also be thought of as minimizing the number of squares that are mowed more than once.

Example:
Here is an example of a 128-move mowing:

• orange squares mowed twice, red square mowed 3 times
• squares mowed more than once remain marked with their original number

---

For those who cannot view images:

 - *** signifies a bush 
 - ### signifies the order mowed 
 - squares mowed more than once remain marked with their original number

001 002 003 004 005 006 007 008 009 010 011 012 013 014 015 016  
128 *** *** *** *** 073 074 *** *** *** 056 *** *** *** *** 017  
127 *** 093 094 *** 072 *** 060 059 058 055 *** 037 038 039 018  
126 *** 092 095 *** 071 070 *** 062 063 054 *** 036 041 040 019  
125 *** 091 *** *** 078 069 068 067 064 033 034 035 *** *** 020
124 *** 090 089 088 079 080 081 *** 065 032 *** 044 045 046 021
123 *** 099 100 087 086 085 082 083 *** 031 *** 049 048 047 022
122 *** 118 101 102 103 *** *** *** 109 030 *** *** *** *** 023
121 120 117 116 115 104 105 106 107 108 029 028 027 026 025 024

---

There are 106 squares to be mowed, however, the optimal score is greater than 106.

If your answer uses less moves than the lowest-move answer so far AND you suspect it could be optimal, then post it!

Otherwise, please don't post it, even if it is significantly different than any other answer posted. The idea behind this request is to prevent answers that do not trend toward the optimal solution.

Answer 1

Optimal : 111 moves



Visual of path

Others of the same length exist, such as this, this and SQLNoob's, and several more.

---

Proof of optimality (see FlorianF's for a more concrete proof:

This problem can be split up in to certain areas, conveniently around the P, S and E, and we can deal with 'entrances' and 'exits'.



We must start in the P or the yellow squares would all have to be covered twice. Starting elsewhere may save 1/2, but would cost 3, whereas starting in the P saves 3, and costs 1.

We must also end on a red square (you can technically end in several places in the E, such as in the middle, but they all have the same result and just navigate the E slightly differently) as ending elsewhere will cause massive costs around the top/bottom of the E.

The blue squares are always a +2, which is obvious as we are starting in the P.

Now the pink squares are less obvious, but they best way to cover them is to dip in and out of them for a +3. By cutting through them you enter the edge, and no matter how you re-enter the inside areas, you will create a new isolated area that is more than +3 to cover, as no length along the edge is shorter than +3, they are all minimum 5 squares.

So optimal paths that start in the P, dip in and out of the pinks for a +3, take the unavoidable +2 on the blues, and finish in the E can have a best score of 111 moves

TL;DR:

An optimal path must start inside the P and finish around one of the red squares at the end of the E. The blue squares in the S are then always a +2, and a +3 arises from dipping in and out of the pinks meaning that 111 is optimal

Answer 2

Proof of optimality for the solutions given

There are 7 regions that have an odd number of accesses.

For each such region you either have an endpoint inside the region or you lose a move going thru an already-used access. The reason is that you need to mow all accesses but you need to use an even number of accesses if you don't end inside.

One important thing is that in the larger regions the accesses are squares that connect to only 2 other squares. If you decide to enter the square and turn around, you must retrace your steps to an already-visited square. So you still lose a point.

Since there are 7 such regions and you have only 2 endpoints, you need to double at least 5 squares.

Examples of such solutions have been given already.

Answer 3

Here's a path that uses just 111 mows:

Proof of optimal starting and ending points and lower bound:

First note that there are two obvious "dead ends":

If you don't start (or end) your path in those squares, they will cost you one extra move to get in and out of them. There are two other slightly less obvious dead ends nearby:

Here we see the blue square is adjacent to three areas that need to be mowed, and whichever direction we choose to move through the blue square (thus mowing two of the three adjacent squares), the third will become another dead end. Similarly:

Here we find another spot where no matter which way we choose to move through, we create a dead end.

So we have four dead ends. We can only start and end our path in two of them, so the other two are going to cost us one square each. Additionally, if we DO start and end in two of them, then it's going to cost us three squares to get in and out of the P: Therefore if we don't start inside the P, we will incur a cost of (at least) 5 additional squares, so 111 is the minimum. In order to improve on this solution, then, we need to start in the P. Now consider the entire right had side of the grid comprising the E. There are three distinct entrance/exit points that are one square wide, meaning we must either end our path within the E (which incurs the cost of all 4 of the aforementioned "dead ends") or we have to traverse one of these entrance/exit points twice, which would incur an even greater cost. Therefore we must end our path "inside" the E, and therefore the theoretical lower bound on a solution is 110. It just remains to be shown that there is 1 more additional point elsewhere in the grid that incurs a mandatory 1-square cost to prove that 111 is optimal.

Answer 4

Because of the [no-computers] tag, I waited to post this answer until somebody else already proved optimality.

A graph-based approach to this problem is to first compute all-pairs shortest-path distances in an undirected graph with a node for each grassy square and an edge between nodes that are horizontal or vertical neighbors. Then solve a traveling salesman problem on a complete graph where the shortest-path distances are the edge weights. As in my answer to a similar problem, introduce a dummy node adjacent to all other nodes to allow the starting and ending squares to be anywhere.

As expected, the resulting optimal objective value is $110$, which corresponds to $111$ squares mowed:

Answer 5

I got 112 squares (assuming I counted correctly), visiting every one:

However, this is not optimal.

Answer 6

Here is a pretty long path that does not visit any square twice, but misses a few spots:

The path visits 96 squares.

To turn this into a solution, we have to add a few extra moves to mow those missed spots:

The five squares inside of the P will take 8 extra moves to mow.
The other five loose unmowed squares can be done individually using 2 moves each.

That gives a total number of moves of:

96+8+10=114 moves

I don't know if this is optimal

Answer 7

I was able to get 111 moves (assuming I counted correctly):