Sujiko is a puzzle often featured in British newspapers. The idea is simple: arrange the digits 1-9 in a 3x3 grid, using each digit exactly once, such that each 2x2 square’s sum matches a given value. To start the reader off, one or two of the cells are filled with clues.

My immediate reaction to discovering these puzzles yesterday is that they are ‘boring’, by which I mean trivially solvable by a computer. Secondly, I noted that the state search space for a potential solution is remarkably small compared to other common ‘newspaper puzzles’ like sudoku: there are around 6.67 × 10²¹ possible sudoku puzzles, but just 9! = 362,880 possible Sujiko puzzles. However, with 2 clues it is only necessary to check 7! = 5,040 possible digit permutations.

But the state search space can be further reduced! Once values for the five non-corner squares we can determine the values we would have to select for the corners (per the sum constraint); the solution is valid if we can select four values for the corners that have not already been used. Assuming two clues are given, this reduces the search space to 7 × 6 × 5 × 4 × 3 = 2,520 permutations in the worst case, but we can still do better!

Wikipedia notes two identities that can further reduce the search space:

In the case of the puzzle at the beginning of the article we only need to select one of 7 possible values for the centre square (x₄), which then gives a value for the square to its right (x₅). With a centre value selected and the opposite corner already known, we can find the value of the bottom-left corner (x₆). From there we only need to fill x₇ with one of four remaining digits: this will then constrain all other cells. Therefore there are only 28 permutations to check for the above puzzle — or any other puzzle with clues in the same position (including symmetry).

For any arrangement where the two clues are directly opposite (e.g. in x₁ and x₇ or x₃ and x₅) we should firstly fill the centre (x₄) with one of 7 possibilities and then another non-corner (e.g. x₇) with one of 6 possibilities. From there we can derive all other cells.

For arrangements where the 2 clues are on the same diagonal, It is then only necessary to select one of 6 values for one of the non-corner cells, from there another cell value can be derived, and after that only of four values needs to be selected for another non-corner cell: after this all other cell values can be derived: 24 permutations should be checked in all.

For puzzles with only one clue it is only necessary to place one value (of a possible 8), and preferably to minimise the number of subsequent permutations to check. In the worst case only 8 × 42 = 336 possibilities need to be checked.

From what I’ve seen, puzzles with 2 clues are labelled ‘hard’ whilst puzzles with a single clue are ‘extreme’ in difficulty. Clearly enumerating these by hand would be incredibly dull, but these can be enumerated in well under a micro second on a computer.

Last night I threw together a general purpose solver for these puzzles, and in my experiments it can solve the general case in under 3 μs (alternatively: it could solve every single Sujiko puzzle ever published in a British newspaper in under a thirtieth of a second). The main algorithm is just a recursive backtracking search with constraint propagation.

To accelerate the solver I wound up on a journey into SSE instructions (most of the puzzle state is stored in a single xmm register) at about 3AM, but I’m happy with the results. The solver could be accelerated further with a little more inline assembly to reduce main memory interaction and specialisation for each possible starting layout.