OddThinking

Introducing OTTF

OTTF (short for One Two Three Four) is a simple single-person puzzle game.

The playing surface is consists of a 13×7 grid of squares, which starts out empty. There is also a 13×7 template card, which has a smattering of numbers of it (in the range 1-4).

Your job is to place a sequence of numbered tiles onto empty squares, so that the result matches the template card.

Each time you place a new tile, it displays the number 1. Each time you place a new tile directly adjacent to an existing tile, the existing tile’s number increases by one. So, the number shown is one more than the number of neighbours that were placed after this tile was placed.

Except there is one twist: If the value reaches 5, it is reset to 1. The number shown is actually (number of neighbours placed after this tile modulo 4) + 1.

If you enjoy these sorts of puzzles, now is the time to go play it, before I spoil it for you.

(For those who don’t know: I like to kill these sorts of puzzles with software solutions.)

Analysis

Partial Ordering

The first thing to notice about this puzzle is that the solutions are not unique. There are plenty of times that there are many equivalent choices of what tile needs to be placed next, while still meeting the constraints of the puzzle. For example, you might have to place a tile at C5 before C6, and at C7 before C6, but there is no restriction of whether you play C5 or C7 first. Both of the solutions [C5, C7, C6] and [C7, C5, C6] are valid. (For those who studied Maths, you are trying to find an arbitrary linear extension to a partial ordering. For those who studied Computer Science, you are trying to do a topological sort over a directed acyclic graph.)

Modulo = Ambiguity

The second thing to notice is that the modulo rule means that the number 1 is ambiguous – it could represent a freshly placed tile, or it could represent a 5 – a tile that was placed first, and then had 4 neighbours placed around it. If the 1 tile hasn’t got four neighbours, it must be the former. If it has, it is ambiguous. This makes reasoning about the puzzle much harder.

Rule 1

After playing a few games, I observed two rules that I was applying, which I have formalised slightly.

The first rule: If a tile has a count that is one greater than the number of neighbours it has, then it must have been placed before any of those neighbours. It doesn’t affect any other pieces on the board, so there’s no reason not make that tile the first move.

Here’s the magic step: If you note that location as your first move, and simply remove that tile from playing board, you can now recurse – solve the simpler puzzle, and prefix this deleted tile to the resulting sequence.

This rule isn’t smart enough to realise that a 1 might sometimes represent a 5, but it is still pretty powerful. This rule is the workhorse of my solver, and is enough (by itself) to solve the first few puzzles completely.

Rule 2

The second rule is only slightly more complex: If a tile has a count of 1, and it has less than 4 neighbours (so it can’t possibly be a 5 in disguise), then it must have been placed after each of its neighbours. It doesn’t affect any other pieces on the board, so there is no reason not to make that tile the last move.

Again, we use the magic of recursion – note the location, remove the tile, a solve the simpler puzzle, appending this tile to the end of the result.

However, the additional complexity is that when we remove this tile, we have to decrement all of the neighbour tiles around it, to undo the increment that occurred when it was added. The decrement occurs in the mod 4 + 1 universe, so a 1 becomes a 4.

Again, this second rule avoids directly dealing with the issue of ambiguous 1 tiles with 4 neighbours. However, it does help out by nibbling away at the edges. If it can remove one of the neighbours of a 1 tile with 4 neighbours, it becomes a 4 tile with 3 neighbours, and the first rule can attack it directly.

Implementation

No surprises for my regular readers: I grabbed my Python-based Puzzle Game Framework, which I used without any modification at all.

The Game Board consisted of a grid of cells.

The (non-empty) cells stored their tile value and a list of their (non-empty) neighbours.

When the cells were triggered to apply their constraints, they checked whether rule 1 or 2 applied to them. If so, their location was recorded in the Partial Solution object (described below), and the cell notified its neighbours to discount this cell in further calculations. In this notification was a flag to indicate whether the nighbour should also decrement their count (Rule 2) or leave it as is (Rule 1). The cell was then marked as solved, which caused the framework to trigger each of its neighbours to re-apply its constraints.

The Partial Solution object unwound the head- and tail-recursion required by the solution. The Partial Solution object consisted of two lists of references to tiles. The first list represented the tiles solved by Rule 1. Each new move was added to the end of this list. The second list represented the tiles solved by Rule 2. Each new move was added to the front of this list.

When the hurly-burly was done, the total solution could be determined by appending the second list to the end of the first list.

I did not bother implementing a graphical view of the data; this puzzle was simple enough to not require it.

The result was 160 lines of Python (plus another 400 to represent the templates of 40 puzzles to be solved, plus the Framework) which successfully solved all of the puzzles offered by the OTTF developers.

Conclusion

This was a great practical success. The Framework worked perfectly. Two simple rules were able to completely solve all of the puzzles I have encountered. It didn’t take too long. (I encountered this puzzle for the first time, and implemented a solver in one evening, while also doing some other tasks.)

I originally said:

the proof of a framework isn’t in the first application that uses it, but in the third, so I am not crowing about it too much yet.

This was the third, and it behaved perfectly without modification. Crow, crow, crow!

I have a niggling feeling, though, in the back of my mind that I haven’t been thorough enough – I haven’t proven that all solvable OTTF problems are solvable with this approach.