17
$\begingroup$

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

enter image description here


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

enter image description here


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.

$\endgroup$

7 Answers 7

12
$\begingroup$

Optimal : 111 moves

enter image description here

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'.

enter image description here

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

$\endgroup$
5
  • 2
    $\begingroup$ now we're cookin! +1 sweet. if someone beats 111, I will be surprised. My best was also 111, although quite a bit different than this exact solution. $\endgroup$
    – JLee
    Jul 15 at 14:00
  • $\begingroup$ @JLee Yeah on second thought 110 is unlikely, though I wouldn't say out the question. I'm going to try and either find some other 111s, or try prove 110 possible/impossible :) $\endgroup$ Jul 15 at 14:02
  • $\begingroup$ If anyone finds 110, I will throw them 100 pts (not like you need it! haha) $\endgroup$
    – JLee
    Jul 15 at 14:05
  • $\begingroup$ @JLee added a rough proof that 111 is optimal, it's by no means thorough, but I think its intuitive enough to show 110 is not possible $\endgroup$ Jul 15 at 14:30
  • 1
    $\begingroup$ @JLee improved my 'proof' if you can call it that, much easier to read. I'm incredibly confident that 111 is optimal - the only real tricky bit is showing that the pink squares must be a +3 $\endgroup$ Jul 15 at 15:34
24
$\begingroup$

Proof of optimality for the solutions given

enter image description here

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.

$\endgroup$
1
  • $\begingroup$ Nice way of thinking about it! 7 regions, each creating an extra move, and the start and end each saving a move for a +5! $\endgroup$ Jul 15 at 15:53
9
$\begingroup$

Here's a path that uses just 111 mows:

1

Proof of optimal starting and ending points and lower bound:

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

2 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:

3 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:

4 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: 5 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.

$\endgroup$
5
  • 1
    $\begingroup$ +1 Those 5 squares are the exact same 5 squares that I got, although my path is slightly different. This is the number to beat, and if it can be beat, I think I can prove that 110 has to be optimal. BTW BeastlyGerbil was first to post the 111. $\endgroup$
    – JLee
    Jul 15 at 14:02
  • 1
    $\begingroup$ Very similar to my 111 path! 75 and 90 seem like they will always be yellow, unless starting in the S - I reckon 111 may be optimal $\endgroup$ Jul 15 at 14:03
  • $\begingroup$ Yes, it looks like this is optimal -- the five yellow squares here, plus square 39 and the inside of the P, will need to be either be yellow or taken care of by one of the two endpoints running into it. Unless maybe 75/71/39 can be taken care of together with only two yellows and/or endpoints? $\endgroup$
    – xnor
    Jul 15 at 14:06
  • 1
    $\begingroup$ What you call "less obvious dead ends" I would call "T junctions". If a closed space have 3 entries that are 1 unit wide, you must start or end inside or pass one exit twice. The E forms another such large space. In fact, any closed space with an odd number of entries is a problem, which covers dead ends and T junctions. $\endgroup$
    – Florian F
    Jul 15 at 15:17
  • $\begingroup$ Correct, answer updated to reflect the E. $\endgroup$
    – SQLnoob
    Jul 15 at 15:37
5
$\begingroup$

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:

enter image description here

$\endgroup$
1
  • 1
    $\begingroup$ Nice. I will dig into this later tonight $\endgroup$
    – JLee
    Jul 15 at 21:05
4
$\begingroup$

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

you can see the overlapping squares better here.

However, this is not optimal.

$\endgroup$
3
  • 1
    $\begingroup$ Very nice. +1, but it isn't optimal. $\endgroup$
    – JLee
    Jul 15 at 13:54
  • $\begingroup$ @JLee whoops, I commented on the wrong answer! $\endgroup$ Jul 15 at 14:12
  • $\begingroup$ @BeastlyGerbil :D Haha, no worries! I was wondering where I went wrong in my counting! It's hard to find the right answer when they're all the same lawn with slightly different red lines on them :-). $\endgroup$ Jul 15 at 14:13
2
$\begingroup$

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

enter image description here
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

$\endgroup$
1
  • 2
    $\begingroup$ A great start, for sure. I won't say any more right now. $\endgroup$
    – JLee
    Jul 15 at 13:52
1
$\begingroup$

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

squares wow

$\endgroup$
3
  • 1
    $\begingroup$ +1 nice. but count again. the 40 needs to be 41, and i think there are more $\endgroup$
    – JLee
    Jul 15 at 13:57
  • $\begingroup$ @JLee ahh you're right, and I was trying to be so careful about keeping count! $\endgroup$ Jul 15 at 13:58
  • 3
    $\begingroup$ Think this is 114, you can just add how many oranges to 106 to get the total score $\endgroup$ Jul 15 at 14:12

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.