Linear recurrences and applications to sudoku

Warning: Spoilers for this puzzle ahead.

I am not a fan of sudoku puzzles.

However there are sudoku variants that are interesting. Usually when they solve nothing like a sudoku.

I want to share something that came up when I solved Lots in Space: Deconstructica by Marty Sears.

The puzzle has lines, where any three consecutive entries along a line have a different residue modulo 3 (which of course implies the sequence is periodic mod 3). And there are blue diamonds, where a digit on a blue diamond tells you how many distinct sums of adjacent pairs of numbers along that line there are.

Now suppose there is a 3 in a blue diamond. Let a_1,a_2,\ldots be the entries along the line. The mod 3 condition, together with the fact that there are only three distinct sums of adjacent pairs tells you that a_i+a_{i+1} is a function of i \pmod{3} only. Thus we get a recurrence

    \[a_i+a_{i+1}=a_{i+3}+a_{i+4}\]

The characteristic equation of this recurrence divides x^6-1, so the solution is 6-periodic. I used this in my solve, but something tells me this was not an intended approach.

Leave a Comment

Filed under Uncategorised

Leave a Reply

Your email address will not be published. Required fields are marked *