Sudoku Variants as Playful Proof Practice
by Malte Skarupke
Doing mathematical proofs is kinda fun. Unfortunately they only make you do a few fun ones in school, then they get frustrating and tedious. So I have long been looking for a game that is about doing mathematical proofs. Euclidea was good, but eventually runs into the same problem as the hard proofs you do in school, so I never finished the game. But recently a lot of hard Sudoku variants have come along that feel exactly like doing a mathematical proof, but are designed to be fun.
The Sudoku world is currently going through an explosion of creativity and innovation, something which I have called a “Treasure Hunting System” before. It’s quite joyful to watch, especially since I never really got into Sudokus before. I found that when Sudokus get hard, they get more tedious instead of getting more interesting. They’re only fun until you get good enough to attempt the tedious ones. At least that’s what I thought until Youtube kept on recommending the Cracking the Cryptic channel, which currently features mostly Sudoku variants, and those are much more interesting.
Like many people I first came across their channel when they featured the “Miracle Sudoku” with only two given digits. It is a variant with the following rules:
Normal Sudoku rules apply. Any two cells separated by a knight’s move or a king’s move (in chess) cannot contain the same digit. Any two orthogonally adjacent cells cannot contain consecutive digits.
These are very restrictive rules. I recommend that you try to solve the puzzle here, or watch the video below. Or watch the first 4:40 minutes of the video up to the point where Simon says “If you want to have a go, click on the link” because he does a good job of introducing the puzzle.
Now if you’re like me, you will be pleasantly surprised by this puzzle, and then end slightly disappointed. To me it felt almost like a cheap trick. In hindsight it’s obvious that if change the rules this much, it only takes two given digits to fill the board. There are probably only a few valid ways to set up a board with these rules, so you can only do this puzzle once, and there are no other interesting puzzles with these rules. And it’s disappointingly easy after the initial setup seemed to promise a challenge.
So I ignored the channel until years later, when some other blogger wrote about them and I found that there were much more interesting puzzles. For example this one:
This is a variant with the following rules:
Normal sudoku rules apply. The grey line in the central box is a thermometer. Digits along that thermometer must increase from the bulb to the tip, but the positions of the bulb and the tip are hidden. In the outer three rings, the sum of the digits along a ring between two 9s must always be the same throughout the puzzle. For the avoidance of doubt, those two 9s could be the same 9 if a ring has only a single 9 in it.
The “thermometer” wording is unnecessarily terse and confusing, but “thermometers” are standard building blocks in Sudoko variants. It just means that the ring in the inner box either has increasing numbers clockwise or counter-clockwise, and it won’t tell you where it wraps around. The constraint with the 9s is interesting and requires doing some proofs. So lets do the start of the puzzle in this blog post. You can try it yourself here, you’ll just have to know one advanced technique which you will have no chance of deriving yourself: The Phistomefel Ring, so lets explain that first, because it also involves proving something.
Lets take a random Sudoku, say this one:
The contents don’t really matter, we’ll just use this board to explain the ring. The thing we’ll prove is that if in the picture below the 16 digits that make up the blue ring are identical to the 16 digits that make up the orange squares:
This is true in any Sudoku, not just this one. To prove it lets just highlight the top two rows and the bottom two rows:
These are 36 digits consisting of the numbers from 1 to 9, four times each. This is just given by the rules of Sudoku. Now lets instead highlight column 3, column 6, box 2 and box 8:
This highlight also contains 36 digits, also the numbers from 1 to 9, four times each. (twice in the two columns and twice in the two boxes)
So the blue are and the orange area contain the same digits. This is not very interesting until we overlap them:
Now we have shaded area that both of these regions share. The area contains a 7 and a 8 in this case, but also 14 unknown digits. It doesn’t really matter what’s in there though, we know it’s the same digits in both the orange set and the blue set. So if we just remove them:
We’re left with the ring and the corner squares. And since we removed the same digits from both sets, and both sets started off with the same digits, we know that whatever is left over must still be identical. q.e.d.
Starting on Archery Target
Lets get back to the Archery Target puzzle. You’ll notice that one of the rings in there is the Phistomefel ring. It won’t be useful right away, but eventually you’ll need to use that fact. If you know the Sudoku rules, you now know everything you need to solve it. You can give it a go here. It took me several days to finish.
So how do we solve this? We have too few given digits so the extra rules must be helpful somehow. If you play around with this a little, you’ll find that the extra rule for the middle ring is useless at first. So lets investigate the 9s. I started off by just randomly placing them to get a feeling for how this behaves:
Just counting the areas between nines, I count 8 areas. This makes sense because the outer three rings cover 8 boxes, so there must be 8 nines. I also tried the extreme case: If I have just one nine in a ring, there are still 8 areas between them:
I placed green lines here. There are 8 green lines because there are 8 areas between the nines. The digits along each of these green lines must add to the same number. Just playing around, I noticed that this is quite restrictive: This arrangement almost certainly doesn’t work because the line in the top left is too short. How could four numbers add up to the same sum as the long line in the middle ring?
Doing some math we find that the outer rings cover 8 boxes, each of which contains the numbers from 1 to 9, which add up to 45, so the overall sum is 8*45=360. Subtracting the nines, we’re left with 288, dividing by 8 gives us 36. So each of these lines must add up to 36. Which is the sum of the numbers from 1 to 8. With this we can already rule out a few placements. For example there can’t be a 9 in the bottom right corner:
If there was a 9 there, we’d have the digits from 1 to 8 on its left, which add up to 36, and then we’d get another 3 around the corner, adding up to 39, before we can place another 9. So this wouldn’t work.
If we try placing a 9 in any of the other corners, we run into a different impossible situation:
The 9 in the top right forces the other two 9s around the corner. This leaves too big of a gap between those two 9s. We can’t make that add up to 36, it’s always going to be bigger. So we can rule out all four corners. Lets mark them red to indicate that there won’t be a 9 in there:
This doesn’t help us much though, and it’s actually a detour on the ideal path for the proof, but I find that playing around and ruling out of a few cases helps to become familiar with the problem. It’s worthwhile even if it turns out that ultimately we didn’t need to do it. It’s also necessary because when doing a difficult proof, you have to continually renew your interest in the problem. If you’re just staring at a mostly empty grid, that’s hard, but small wins like this help to maintain interest.
The actual way to work towards the solution is to try to figure out how many nines go on each ring. I start off by pencil-marking the numbers 1234 onto each ring, as our possible options for how many nines can be in each ring. Usually pencil-marking is used to indicate possible digit-values for a cell, but I just want to keep track of how many nines are still possible on each ring. As we eliminate options, we’ll remove numbers:
The easiest options to remove are the 1 options. It’s easy to see that we can’t place a single 9 one the outer ring and middle ring because the sum for that 9 would be too big. We could in theory place digits that add up to less than 36 on the inner ring, but the 7 that’s already placed messes it up:
So with a single 9, we’d always be over 36 because of that 7. So there must be at least two 9s in each ring, which we’ll remember by eliminating 1 from our options in each ring:
The next-easiest options are on the outer ring. We can pretty easily rule out that there are two or three 9s on that outer ring. The sums always ends up being too big because we have to use big digits on the outer ring. So there have to be four 9s on the outer ring:
Now after this we can eliminate the 3s from the other rings because our total has to be 8. So if we have 4 on the outer ring, we can only have 3 on another ring if we had 1 on the last ring, and we already ruled that out:
At this point I want to rule out the 4s on the inner two rings, but thinking about that actually reveals an exciting option: What if there was a 0 on any of the rings? In that case the rules change. We would no longer completely cover 8 boxes, so our overall sum is different, so the areas between 9s don’t have to add up to 36. So lets add that option:
How would we prove this case? If we could eliminate the 2 from any of the two rings, that would also eliminate the 2 from the other ring, so there would have to two 4s and a 0. We can do that on the middle ring. If we tried to place the smallest possible digits there, we find that we can never put digits small enough that would add to 36. The smallest possible digits, after placing two 9s, are the digits from 1 to 6 twice and the digits from 1 to 5 twice, which add up to 21+21+15+15=72=2*36. This seems to barely work, but the pre-placed 3 messes up that plan because it rules out 3 from one row. We have to use a larger digit at least once, so our sum will be too big.
So that means there have to be zero nines on one of the rings, which will change what the sum between 9s has to be:
I will stop here. This should give a feeling for how you attack this Sudoku. There is a lot of proving left to do, even after you figure out which ring has zero nines on it.
Is this a real mathematical proof?
This is similar enough to a real mathematical proof that we can practice all of our techniques in a playful environment. Notice how nobody tells you what you have to prove. Your first goal is to just figure out how to even attack this puzzle. You have to figure out which approach gets you stuck and which approach allows you to make progress. It took me a while to understand that the important part is how many 9s are on each ring. And then it took me a while to understand that I have to prove that one of the rings has no 9 on it. And then nobody tells you how to do it. The rules of Sudoku constrain what you can do, and you can do some of the approaches that you would try in real proofs, like “try the smallest possible thing” or “try the largest possible thing” but you mostly have to do a lot of thinking, which is very unlike the normal Sudoku gameplay of “try to spot the number you missed.”
You can do all of the classic techniques for this like trying to first solve a simpler subproblem, or first try to solve a more general problem (like the Phistomefel Ring, which will become relevant, or you can see Simon try to think if he knows a general proof that each ring has to contain a 9, in the video below) and you can do that in a setup that’s been designed to be helpful (notice how the given digits have added just the right constraint in crucial moments) and interesting to work in.
My solve was noticeably different than Simon’s solve on the youtube channel. He goes through the puzzle at a crazy high speed, solving it in just over 90 minutes. I don’t know how long it took me, but five to ten times that long is a good guess:
Puzzles like this are very common on the channel at the moment. It seems like Simon is playing more puzzles like this, that require interesting proofs, and Mark is playing more puzzles that require advanced Sudoku techniques. So I’ve been playing more of the puzzles that Simon does.
Here are three more that I enjoyed:
Play it here
Play it here
Play it here
I’m sure I’m missing some really good ones, but I don’t have time to play most of the puzzles on the channel, especially since I’m so much slower than Simon is… But this beats playing randomly generated Slitherlinks (which is what I’d do before this) by a lot. If you know of some good puzzles that are like this, please share them because I don’t have time to catch up with the channel and necessarily have to miss most puzzles…
And just as I had this blog post typed up and ready to go, I noticed that today’s video is called “Do You Need Theorems To Be A Sudoku Expert?”, so I guess I’ll try that one next:
You might really like puzz.link. Click on puzzles in their db that were shared on twitter for easy access to them.