Puzzle 8: MUD, GLORIOUS MUD [7 points]

[tjperr]

MudCraft is a bafflingly addictive video game played on a map of 19 hexagonal territories. Initially, all territories are “mud” (brown), as shown in the left-hand image below.

The rules of the game are simple:

If you click on a mud territory, it becomes “forest” (green), and all immediately adjacent territories are flipped (that is, mud becomes forest, and vice versa) If you click on a forest territory, it remains as forest, but all immediately adjacent territories are flipped (that is, mud becomes forest, and vice versa) For instance, starting from the initial map, clicking on the central territory would result in a map with 7 forest territories and 12 mud territories. If we were then to click on a corner territory next – the one in the top-left, say – we would obtain a map with 9 forest territories and 10 mud territories, because the second click would turn three mud territories into forest, and flip one of our forest territories back to being mud.

What is the minimum number of clicks needed to transform the initial map (in which all territories are mud) into the “Christmas tree” map pictured in the right-hand image below?

(Note: In your answer, please provide an example of how the transformation could be achieved in the minimum number of clicks. It may be convenient to number the territories from 1 to 19, proceeding row by row from top to bottom – in other words, the 11 forest territories in the “Christmas tree” map would be numbered 2, 5, 6, 9, 10, 11, 13, 14, 15, 16, and 18.)

Is it possible to transform the “Christmas tree” map back into the initial map in the same number of clicks?

[johnmatthewswift]

There are multiple solutions in 9 clicks, all following a strategy of:

• clicking each of the 4 edge spaces twice to fill each and reverse the effect on surrounding spaces
• filling the central 7 spaces last by clicking the very centre space e.g.: 2, 2, 13, 13, 16, 16, 18, 18, 10

The map can't be transformed back into the original in the same number of clicks. In fact it can't ever be transformed back to the original position. There is no final move available which can result in all spaces being mud; clicking a forest space leaves that space as forest, and clicking a mud space flips that space to forest. This means at least one space (the one clicked) must be forest and we cannot return to the original all mud state.

[johnmatthewswift]

A solution in fewer than 9 clicks, would need to turn the outer spaces (2, 13, 16, 18) to forest and undo the undesirable effects of turning adjacent spaces to forest more efficiently. I can't see an obvious way to improve on 9 clicks, but equally can't readily produce a proof of why it wouldn't be possible.

Notes on the viability of proof by exhaustion:

• To beat the initial solution a solution in 8 clicks or fewer is needed.
• There are 19^8 possible 8-click sequences.
• As the pattern is symmetric down the centre, 8 of the first moves have exact mirror equivalents, leaving 11 effectively unique.
• This leaves 11 * 19^7 sequences to test, i.e. 9,832,589,129 or around 10 billion, so is beyond what could easily run.