Wednesday, March 12, 2014

Zen Garden Puzzle: Three Moves Suffice

Today it's three months since the release of my last game Zen Garden Puzzle. While financially it has been a failure, and is orders of magnitude away from recovering the development costs, it has been appreciated by players, receiving nothing but 5-star reviews on the App Store.

A few people have been engaged enough to solve hundreds of puzzles, but only a handful have reached the elusive 10th Dan achivement. To earn that achievement, you have to take advantage of one of the selling points mentioned in the App Store blurb: "no matter what you do, you will never be more than three moves away from the puzzle's only solution."

After seeing the game for the first time, most people doubt that this is actually possible. Some asked me if you need some amount of luck to be able to do so. The answer is: it's always possible, and you don't need any luck, only skill. I could provide a mathematical proof, but I don't want to be more boring than usual, so I'll just show how to solve one puzzle.
The first thing we have to do is solve the puzzle in our head, determining the correct position of all the stones before even touching them. This requires some observation and memory skills and is certainly harder than starting to move the stones right away; but you can't expect to reach 10th Dan without effort, can you?
Typically you don't need to solve the whole puzzle in your head: you just need to find the position of 3-4 stones in order to make the first move. For simplicity, however, I will solve the whole puzzle.

So, in the puzzle above, the first thing we can do is note that in the first column there is a vertical area, which must contain one stone. We take a mental note that the other cells of the column cannot contain a stone:
Now we note that the rightmost three columns contain cells from only three areas. Therefore the stones contained in those areas must be in those columns, and we mentally exclude their other cells:
Now we can see that the first row only contains usable cells from one area, so we exclude all the other cells of that area:
We now see that in the second row there's only one space left, so it must contain a stone. We mentally put it there, and exclude all the other cells in the same row, column, area:
Now we can put a stone in the second to last row:
The other stones follow easily, so we now have a mental picture of the solution:
All we have to do now is turn this mental picture into actual moves that will solve the puzzle in three steps. But that's the easy part.

To see how this works, the key is to understand how the stones move. Remember that the game guarantees that there always is exactly one stone in every row and one in every column of the board. When you move a stone, you can do so in a straight line horizontally or vertically, like a rook in chess: in that case, another stone will move in the opposite direction to keep the balance.
But you can also move a stone diagonally: in that case, two other stones will move to fill the row and column left empty by the stone you moved.

Look at the stones. Every one of them could be moved horizontally to reach a correct position in the same row, or vertically to reach a correct position in the same column. Conversely, every correct position can be covered by two stones, one in the row and one in the column.

What we want to do is a diagonal move which will make two stones move to their correct position.
Let's pick the stone in the second to last row, for example. I've drawn a blue arrow to show the move that we need to do; the green arrows show the consequential moves that will be done by the game.
With the first move done, we just need to repeat the process with another stone; let's use the one in the second column:
Now the third move will bring three stones in the correct place, and solve the puzzle:
Why is it guaranteed that the last move will solve the puzzle? Because with our diagonal moves we put six stones in the correct place. The seventh stone is automatically forced to be in the only row and column not used by the other sixwhich is necessarily its correct place.
So there you go. I have shown that 10th Dan is achievable; getting there, however, will still be up to you.

©2014 Nicola Salmoria. Unauthorized use and/or duplication without express and written permission is strictly prohibited. Excerpts and links may be used, provided that full and clear credit is given to Nicola Salmoria and with appropriate and specific direction to the original content.