There are four directions of moves: Horizontal, Vertical, Downhill and Uphill. For the purposes of notation I will place a letter H, V, D or U at the point in the grid corresponding to the centre of the three coins being flipped. So the grid to the right shows all 24 possible moves.
The solution to POTW #161 is particularly interesting, as the number of coins and the number of moves are the same. This means that for any given starting arrangement, there is exactly one set of moves that will solve it. (We can safely say that performing the same move twice is the same as not performing it at all, so we don’t need to worry about repeating a move; a move is either performed or not).
For any arrangement larger than the solution to POTW #161, there will be some sets of moves, which I will call ‘null sets’, that cancel each other out (the simplest of these to understand would be three horizontal moves and three vertical moves within a 3 by 3 area of the array – each of the 9 coins will be flipped twice and end the same as it began). You can even work out how many ‘null sets’ that will exist:
For example, a 3 by 4 grid has 12 coins, and 14 moves. This means there are 2^12 (4096) possible arrangements and 2^14 (16384) possible sets of moves. This means there are 4 times as many ‘move sets’ as there are arrangements. It follows from that that there are 4 ‘null sets’ (although one of those null sets is the empty set – no moves at all).
I’ll now introduce the concept of an ‘independent null set’. That is a null set that cannot be formed by combining other null sets you’ve already found (so technically any null set might be an independent null set if it happens to be one of the first you find). For the 3 by 4 grid there will be 2 independent null sets (let’s call them a and b), and the total of 4 null sets can be formed by a binary combination of these (that is, ‘a and b’, ‘a only’, ‘b only’, and ‘the empty set’). Below is a possible ‘a’ and ‘b’ for the 3 by 4 grid:
