One of my college friends has an interest in Sudoku variants. Generally, that
manifests in the two of us solving puzzles curated by
Cracking the Cryptic,
but occasionally it ends up with me trying to solve a puzzle he’s created.
A while back, he and I were chatting about one of his ideas for the basis of
a puzzle. It’s based around a snake in the grid (for an example of another
puzzle using a snake, check out
this puzzle by CtC). His puzzle
requires that its snake alternates successive even digits and odd digits, is
unambiguous, and visits at least one cell in every box (as well as, of course,
being a valid sudoku puzzle!).
Let’s talk about those rules in a bit more depth:
Snake: A snake is a one-wide orthogonally connected path. Much like in
the classic Snake game, it can’t touch itself anywhere along its length
(although diagonal adjacency is fine). The one in this puzzle has alternating
even and odd digits along its length, represented in this post by red and
blue respectively:
visits a cell in every box: The above snake fills this requirement as
well. The following (shorter) snake does, too:
and the big constraint, is unambiguous: Given the pattern of even and odd
digits in the grid, there is exactly one direction the snake could continue
at any point and still satisfy the parity constraint. To see this happen, we
also have to have some information about the parity of the cells surrounding
the snake. In general, each cell of the snake is touching either one (if it’s
the head/tail) or two (if it’s part of the body) other cells that are snake
cells. These must be of the opposite parity. The other cells must be of the
same parity.
For example, suppose that the head of the snake is even, and continues into
the (odd) cell to its right:
To ensure there’s no ambiguity that the snake continues to the right, all of
the other cells must be invalid for the snake to enter; that is, they must
all have the same parity as the head:
Now, each box must contain a 1 through 9; that is, four even and five odd
digits. This one already contains all four even digits, so the unfilled cells
must be odd:
The only place the snake can proceed, then, is directly into the second box:
If we continue to the right, we would need at least five red cells in the top
middle box (try it out, if you like!) so now we have to move down…
Repeating this logic eventually gets us here. This scenario, however, is already
broken—there simply isn’t a way to get the snake back into the top right box,
if we can’t put a red cell in that middle row.
This type of logic is fairly time-consuming and error prone, but it’s not really
that complex^{1}, so we put together a Python program to
try out paths for us that satisfy the even-odd and uniqueness constraints. Given
that it was written hastily to solve a one-time problem, it’s certainly neither
very neat nor readable, but it seems to do what we want!
Open if you dare!
While the rate my terminal emulator can display the text seems to currently be
the bottleneck, it’s still certainly not slow, so I left the output displayed at
each step the algorithm takes. This was essential as a debugging tool, but now
it’s just nice to watch it run. It’s really a rather pretty visual; I forgot how
much time I could spend staring at visualizations of searches^{2}! If
I’m ever bored for an evening, I may consider porting it to Javascript so it can
run in the browser, but for now if you want to see more, you’ll just have to
download and run it yourself. All you need is Python.
A version of this program with all the print statements removed took about five
minutes to find 3241 possible configurations that satisfied the constraints.
Since we’ve found all the possible combinations (recognized by this program, at
least), we can also figure out the shortest and longest possible paths that
satisfy the constraints—21 and 37, respectively. And both are pretty neat
shapes!
Images from this post were created using
penpa-edit.
Over-optimistic as always, I think I had said we’d
probably have a solution together in an hour. I think by the time we’d
worked out all the bugs and edge cases, we were somewhere between three and
four hours in, but it was a fun challenge to write! ↩
If you also enjoy watching this sort of thing,
Jamis Buck’s page on mazes has a bunch
of really neat animations! ↩