I wouldn't recommend jumping straight into it however, so I'm going to try and post a little bit of background material first. I'm now going to work backwards.
Today (9th October) I was about to write this post, and then I saw Sam Cappleman-Lynes comment on my previous post regarding Phistomefel's theorem being equivalent to SK Loops, and so I am wondering if the Fred's generalisation, and the further generalisation I am about to try and explain, are in fact equivalently explained using some impenetrable notation in a dark corner somewhere over on http://forum.enjoysudoku.com/. Maybe we'll find that out later, dearest reader.
Now let's jump back to the beginning. My attention was piqued over on Cracking the Cryptic by a pair of videos where both Mark and Simon solved the same puzzle by Philip Newman, which comes with the name Tatooine Sunset:
- Mark's guessy solve is here: How I "Cheat" at Sudoku
- Simon's more methodical solve is here: How NOT To Cheat At Sudoku!
- For reference, the puzzle is also discussed here: http://forum.enjoysudoku.com/tatooine-sunset-tatooine-sunrise-t38180.html
I watched Simon's video on Wednesday night (7th October), and saw there were an awful lot of swordfish going on, together with some triples, and that everything was hinting at some extraordinary underlying structure to this puzzle. I messaged Simon to say that there was something sort of Phistomefel-ly with the givens in the 4x4 region of the grid between Rows 2-5 and Columns 2-5 (A). I also saw there was something else going on with some more regions: namely those between Rows 7-8/Columns 2-5 (B), Rows 2-5/Columns 8-9 (C), and then Rows 7-8/Columns 8-9 (D).
This clearly suggested a Fred style partition, grouping together Rows 169 to define one part of the partition, and Columns 167 to define the other. The 9 cell set (E) defined by the intersection of these rows and columns is absolutely fascinating, as it is where the breakthrough in this puzzle is made, after you're done with all the fishing around.
Fred's theory tells us that the set of digits placed in those 9 cells, plus 3 extra copies of 1-9, are equal to the set of 36 numbers placed in the four regions A, B, C and D described above. I'd even got as far as noticing that the digits 5,7,9 occur exactly 3 times each in that ABCD area. Which implies that the set E cannot contain the digits 5,7,9, since:
E + 3 x (1-9) = A + B + C + D
and the 3 copies of each digit on the right hand side are exactly accounted for by the 3 sets of 1-9 on the left. This felt like an exciting deduction, and I'd even managed to have the idea that this was in some sense equivalent to swordfishes, because as Fred has told us, swordfishes are one thing that can be explained by this intersection theory.
At that point I think I'd have been left scrabbling around not knowing what to do next. It was as if I had some of the picture, but not all of it, and I had no idea what I was looking for. However fate then smiled upon me.
On Thursday night (8th October), as I was googling "tatooine sunset sudoku" to try and find the enjoysudoku forum post again, I noticed a link to Trevor Tao's video. [I'm so excited by all of this I am only going to mention in passing that I *think* Trevor may well be the brother of the Fields Medal winner mathematician, Terence Tao]. I also messaged Simon about this video on Thursday, so I'm kind of hoping we might be seeing a video on this in the next week or so. Simon certainly has a talent for clear exposition than I can only dream about!
Trevor's genius observation was that the right way of thinking about this puzzle is not via Fred's inersection theory, and a partition into 4 regions of the grids, but instead to partition rows and columns into 3 (which he does via colours in the video) to end up with a 9 region partition of the grid.
In case you are too lazy to scroll up to see the link to Trevor's video, I'm going to post it again. I can't get over how unbelievably elegant this generalisation of Fred's already very elegant intersection theory actually is!
The video skips over some of the details a bit quickly, so I'm going to add a couple of observations.
- I'm not entirely convinced using the same colours to partition both the rows and the columns is necessarily helpful. When playing around with this in my notebook, I'm labelling the columns ABC and the rows DEF.
- I also don't think displaying the dual view of the 9 resulting intersections as exactly the same grid as the original Sudoku puzzle is all that intuitive. Whilst the two are linked, they do behave very differently. In my notebook I drew a 3x3 array of the partition something like this:DA DB DCEA EB ECFA FB FC
- On the other hand there are some advantages to the colouring, as it does highlight some of the beautiful structures underlying this puzzle - firstly that the red rows/red columns intersection is entirely occupied by givens, which is also the case for the blue rows/blue columns intersection.
- More than that, the digits in the red intersection and the digits in the blue intersection have no overlap! And this imposes further structure into the dual 3x3 array because now it means that, for example, red rows/blue columns is the same set as blue rows/red columns. In other words it's Fred's intersection theory working together simultaneously over 3 different 2x2 partitions!
- What this then means is that you can play a weird sudoku-like game (albeit one with repeated symbols!) in this dual 3x3 array to then try and solve the sets of digits in each of the 9 intersections, noting that each complete set of 3 rows or 3 columns must contain 3 complete copies of the digits 1-9.
- For this particular puzzle, this game is by no means trivial. The step where Trevor places two 8's and two 1's in the green rows/green columns intersection (having first observed that having three of either is impossible) is quite subtle, and relies on some pigeonhole principle style reasoning. For example, if you only have one 8 then this implies three 1s, which we have already seen is impossible. And vice versa.
- It's also worth observing that to solve the sets of digits within the dual 3x3 array, you still need to make some reference to the original grid. It's not easy!
- When you have solved the dual 3x3 array, using all this information to solve the puzzle is also not easy. You'll need to mark up quite a few triples in the grid, noting that cells in some of the intersections have only 4 possible candidates, before you can finish the solve. As in Simon's video, the techniques used after this are simply hidden singles and naked singles, but let me say this again, to actually spot these after all of the above, well, it's not easy!