Reflections on Intersections, Naked and Hidden.

There's no puzzle in this post I'm afraid, but a few random thoughts.  Some more to do with me, and some more generally on Sudoku Theory.  I'm afraid if you're more interested in one things rather than the other, dearest reader, then you'll just have to bear with me this time.

---

Firstly, something that has been playing on my mind a bit recently was the announcement of a Cracking the Cryptic sudoku book via a kickstarter campaign.  This does look very exciting, and I've paid up my $19 USD to secure a copy for whenever it's ready.  The money they've raised to date is phenomenal and it's exciting to see exactly where Mark and Simon can take Sudoku, particularly when you compare that with what the WPF has been able to achieve.  All the best to them!

And yet when I look at the list of the contributors, it's a bit like seeing all the cool kids running off to play their cool kid game, without being invited.  Don't get me wrong, it's their book and their channel and they can do whatever they like, I have no problem with that.  And I do get that the puzzles I create aren't really the sorts of puzzles that get their viewers' pulses racing, so there's no real reason why I would be included.  And the authors on that list certainly include a few of my favourite authors so absolutely no complaints there.  I suppose the crux of the matter is simply that I'm kidding myself a bit to look at that list as a "Who's Who" of the best sudoku authors.  From that point of view I can console myself with the company of many more of my absolute favourite sudoku authors who didn't make the cut.

I'll leave things there - I do feel a bit better for simply expressing my feelings on the matter to you, dearest reader - I suppose all I'm really saying is that it would have been nice to have been asked.  As presumptuous as I'm sure that sounds to even my most dearest of readers.

---

Moving on, I've been thinking a little more on some of the recent posts and discussions on this blog, particularly to do with intersection theory.  The news thing from that front is that I've created this resource to help any of my interested dearest readers to easily visualise the addition and subtraction of rows, columns and 3x3 boxes.

https://docs.google.com/spreadsheets/d/1dTAJNB-U-5d8bxwFsWwyVHEU9xAGiBf3mjMmUboHzFI/edit?usp=sharing

I've also started fleshing out a list of references which might become the basis of a more permanent article I might put together as and when I get my head around this stuff even more.

Fred's recent comment gives me some hope that there might be some kind of multiplication we can work into this algebra of constraints, but I haven't really given much more thought to it than that.  If anyone else gets there before I do I'd be most interested to hear about it!

---

The final item of business is simply to reflect that all this discussion holds my interest because it's fundamentally about linking different areas of a sudoku grid to each other in interesting ways.  We had started off by thinking about these as partitions of cells, but I did want to discuss something more along the lines of a partition of digits.

At the danger of stating the complete obvious, hidden pairs/triples/etc using a subset of the digits 1-9 are exactly the same thing as naked septuplets/sextuplets/etc, and vice versa.  The way I thought about it was like this:

• Suppose you have a naked triple of 3 cells in a row whose possible candidate placements are some of 1,2,3.  That means there a 6 cells left in the row, and 6 digits which we haven't been able to place - i.e. we have the very definition of a hidden sextuplet.
• Now suppose you have a hidden triple of digits 1,2,3 - each of which can only go in some or all of 3 different cells in a particular row.  This means that for each of the 6 remaining cells, we only have 6 possible digits from which we can choose from - i.e. we have the very definition of a naked sextuplet.

The conclusion is that which ever way you look at things, hidden or naked, you end up making identical deductions.

My next thought is that the naked point of view (i.e. looking at which digits are possibilities for given cells) I've always - perhaps mistakenly - viewed as the basis for some of the more advanced techniques when compared to the hidden point of view (i.e. looking at which cells are possibilities for given digits).

I say perhaps mistakenly because I think I realise now this is probably a misconception I've picked up trying to follow discussions of advanced sudoku solving techniques, where computer assistance is de rigueur and grids are very conveniently displayed with all the possible candidates automatically displayed - an approach to sudoku solving which generally leaves me very cold.  When I tend to solve, the more cells in the grid I label with pencilmarks, the less I generally enjoy solving a puzzle.

Anyhow, the link between naked and hidden and partitions and so on reared its head to me again when I came across Bob Hanson's website, discussing:

• Bent naked subsets (in particular Y-wings)
• Intersection ideas briefly
• Intersection ideas in more detail

As I'm sure you can pick up from the somewhat dated web-design, in some sense all of this way of thinking is not particularly new - indeed it's been around nearly as long as sudoku mania (dating back to 2004) itself has.  My interest remains in thinking about these things from different perspectives.

There's a bit more there for me to get my head around, particularly with a link to almost locked sets (ALS) and what he describes as almost locked ranges, but I want to finish with the two rules that Bob outlines with relations to bent subsets:

1. If a bent naked subset contains one and only one candidate k that is present in both of its nonintersection subdomains, k can be eliminated as a candidate in any cell that sees all the possibilities for k in the subset.
2. When there is no common value k in the two nonintersecting regions of a bent naked subset, the subset behaves as a standard naked subset. That is, candidate k can be eliminated from any cell that can "see" all cells of the subset containing k.

What I'd like to try and work out and see if there's a "hidden" point of view for "naked" subsets that span intersections of a row/column with a box, in the same kind of pleasing way that can alternatively view so-called Schroedinger's cells via intersections as a kind of semi-Phistomefel arrangement.  Again if anyone else gets there before I do, I'd be most interested to hear about it!

The MSLS: Revolutions

Wait. 

I've seen this. 

I stand here, right here, and I'm supposed to say something.

I say, "Every grid with an intersection of partitions deduction has a multi sector locked set, Tom"

A little while back I published a difficult puzzle as a kind of tribute to what I consider one of the greatest Sudoku puzzles of all time.  This puzzle was first published in 2008 in the Botsu Baku section of what was nikoli.com.  Sadly, nikoli.com and its many, many gems are no longer with us, but I do have a screenshot or two in my private records so that there is at least some archive of these puzzles.

To make initial progress with this puzzle, you can place a 3 in R9C6 and 9's in R3C5 and R5C8. And then you grind to a halt.

I suppose it should come as no surprise that this is a puzzle that Cracking the Cryptic has picked up on previously, as wonderfully meticulous as they are.  The position after these three placed digits seems to be where they've picked up on this.  [As an aside, I can't say why they picked up on this non-symmetrical version of the puzzle, to which there isn't the usual attribution - but I'd be interested to hear more about that].  Simon goes on to describe the technique required as a so-called Schroedinger's cell.

R4C1 is identified as the Schroedinger's cell, which seems the natural choice as the ensuing what-if analysis makes use of the fact that the only candidates in R9C5 are 1 and 2.  This mirrors the original explanation given by nikoli in the corresponding solution replay back in 2008, as it happens.  My interpretation of the logic is something like:

• If R9C5 is not a 1, then this means the 1 in Row 9 must go in R9C3.
• This implies the 1 in Column 1 must go in R4C1.
• Equally, if R9C5 is not a 2, this means that R4C1 must be a 2.
• Therefore the only candidates for the Schroedinger's cell R4C1 have to be 1 and 2

The puzzle then continues by noting that the only place for a 4 in Column 1 is at R2C1.

One observation with my interpretation is that we didn't use the fact that the only candidates for R9C5 were 1 and 2.  If R9C5 was neither 1 nor 2, then we'd have to conclude that R4C1 was simultaneously a 1 and 2.  Which, despite all this Schroedinger adjectival being thrown about, is still a contradiction, and so we also deduce that the only candidates for R9C5 are 1 and 2 anyway.

So why not observe that R9C5 is also a Schroedinger's cell?  The logic is something like:

• If R4C1 is not a 1, then this means the 1 in Column 1 must go in R1C7.
• This implies the 1 in Row 9 must go in R9C5.
• Equally, if R4C1 is not a 2, this means that R9C5 must be a 2.
• Therefore the only candidates for the Schroedinger's cell R9C5 have to be 1 and 2

The symmetry is beautiful!  But either way there is still something of the if-this-then-that, or even trial-and-error about this deduction.  Maybe we could make this slightly more satisfying:

 

Let's consider Row 9 and Column 1 simultaneously, which I've circled purple.  Within these 17 cells, we need to place two 1's and two 2's (noting that we already have a 6 placed at the intersection).

Now let's think about where we can possibly place this set of four digits within the confines of the purple cells?

• We can have at most one each in the two cells I've circled red
• We can have at most two cells in the cells I've circled orange (noting that these four cells are contained in one box)
• We can't have a 1 or 2 anywhere else!

Therefore, we can conclude that the "at mosts" are also "at leasts", and subsequently that the only two candidates in each red circled cell have to be 1 or 2.  If either cell was anything other than a 1 or a 2, then we could not fill up Row 9 and Column 1 with their full complements of 1s and 2s.  Put another way, this little trick that unlocks a masterpiece from 2008, is nothing other than an example of MSLS, as first described in 2012.  Which I think is rather extraordinary!

So dearest reader, what are we to make of all of this?  All the recent discussion regarding Phistomefel's theorem, its further generalisation as Fred's intersection theory, its further generalisation as Trevor Tao's "9D Wonkyfish" - as well as Sam Cappelman Lynes' exposition of this in the language of SK Loops and MSLS has certainly got me thinking.

Sam himself said that there is no formal definition of MSLS that is agreed upon, so I thought (at the risk of probably reinventing the wheel) it might be worth sticking my own neck out, and having a fumble in the dark with my own interpretation.

I see MSLS as being a generalisation of hidden pairs/triples etc.  The idea being that we are trying to find areas of the grid where we have:

1. A subset D of the digits 1-9, considered with a multiplicity M, which then makes up a set of (at most) M copies of D.  Let's call that repeated set S, and we'll say that it has a total of N digits to be placed.
2. A collection of (perhaps slightly more than) N cells into which the N (possibly repeated) digits of S need to fit into.
3. The idea then is that the digits in D squeeze out all the other candidates from those cells because there is no room for anything else.

To highlight the generalisation, suppose you have a row where you are looking to place the digits 1,2,3 - and you know that the 1 can only go in C4,9, the 2 can only go in C2,4,9 and the 3 can only go in C2,4.  Then you have a set of three digits (1,2,3), and only three cells in the row in which you can collectively place them.  The hidden triple deduction then lets you say that the possible candidates in C2,4,9 can only be 1,2,3 - and that any other digit can be eliminated as a possibility.

This is easy enough to see in the confines of a single Row (or Column, or 3x3 Box come to think of it) where we don't have the complication of repeated digits.  After all a hidden triple, whilst sometimes very difficult to see when solving by hand, is nevertheless viewed as an elementary sudoku solving technique.  What I find fascinating is that Phistomefel, Fred and Trevor have helped teach us that there are deeper structures within Sudoku, inherited from Latin squares, that link together multiple instances of different rows and columns, and to which we can apply the same kind of thinking.  These structures go beyond the naive understanding that we are simply looking to place each digit from 1-9 both at least once in each Row, Column and 3x3 Box in isolation, and indeed at most once in each Row, Column and 3x3 Box in isolation.

The examples from the Tatooine puzzles (we discuss sunset here), as well as Sam's puzzle (as discussed in Reloaded) involve rather large sets of "hidden" digits with multiplicity that somehow need to be squeezed rather tightly into similarly sized sets of cells within the grid, and both the digits and the cells can be hard to see on the face of it.  The main point of all the recent progress we have made, dearest reader, is to help better visualise when we might be in a situation to uncover one of these hidden multi-pairs, multi-triples or multi-quads.  

I don't think we will ever need anything bigger than quads, in much the same that we never really any thing beyond the 4-way x-wing, a.k.a. "Jellyfish".  In fact, I think the correct way of thinking about all of this is that x-wings, swordfish and jellyfish are basically hidden multi-singles.

I'll begin to conclude.  Hopefully with Revolutions, I have been able to demonstrate that hidden multi-sets don't always have to be big and intimidating beasts.  Once I revisited the nikoli puzzle with the MSLS framework in mind, I was surprised by the simplicity of the deduction - potentially even easier than x-wings and swordfish, and certainly no more difficult.  

Equally interesting is that within this simplicity lies something else that I haven't been able to grasp in terms of intersection theory alone - and I think it's because now we're mixing in 3x3 boxes alongside rows and columns.  As I've hinted previously, I do have other ideas about how this might equivalently end up, but on that note, dearest reader, I'm going to leave things there and simply say I much prefer Sudoku to Column Dance.

The MSLS: Reloaded

"And now here I stand, because of you Mr. Stalder, because of you.  I'm no longer an agent of this system, because of you.  I've changed.  I'm unplugged.  A new man, so to speak, like you, apparently free."

"Congratulations."

"Thank you."

So I was originally going to add one more post on this topic, but this morning it's become clear there's the opportunity to add two related posts, and add in more neat nods to pop culture I enjoy.

This one was prompted by last night's video on cracking the cryptic, which is very much presenting the MSLS interpretation of the discussion.  I'm not entirely sure whether Simon actually reads this blog, or gets the information via separate conversations he may (or may not!) be having with Sam, but in the videos he is vaguely referencing conversations between myself and Sam.  My discussions with Sam have only happened here on this blog, so one way or the other they have to be the source.  I haven't heard back from Simon since pointing him in the direction of Trevor Tao's wonderful video, which I'm sad to say has not (to date) even had a vague reference on cracking the cryptic, so I can't say for sure whether it's a conscious decision to present this theory from one angle, or whether he is simply unaware of the extent to which all this discussion is influenced by many different contributions, Trevor’s certainly not withstanding.

Anyhow, I hope at least that my dearest readers will agree that all this stuff is far too interesting to not explore in plenty of detail and from multiple different angles. 

On to business.  Sam has come up with a wonderful puzzle which I'm pretty sure has been designed to completely bamboozle scanraid.  And it does.  For reference:

• The video is here: https://www.youtube.com/watch?v=uvTV_Wivxmo
• You can play the puzzle here: https://app.crackingthecryptic.com/webapp/dqTM27jm3P

However, I’d like to present it to you again with a bit of colouring in:

As I'm sure all my dearest readers are aware, this looks very much like one of Fred Stalder's examples as discussed in a previous post.  To recap:

• Here's my post: https://tcollyer.blogspot.com/2020/09/puzzle-350-sudoku.html
• Here's Fred's original post: http://forum.logic-masters.de/showthread.php?tid=1811&pid=32019#pid32019

The punchline to all of this is that instead of doing all the elegant MSLS stuff that Simon does in the video, you can instead make the following (simpler!) observations:

1. Thanks to Fred, we know that the digits placed in the blue cells plus a copy of (1-9) are precisely the same digits that need to be placed in the red cells.
2. There are 15 red cells with odd digit givens, and 10 red cells with no givens
3. There are 6 blue cells with even digit givens, and 4 further even digits in the copy of (1-9)
4. Therefore the 10 empty red cells must contain 10 even digits.

As Sam has pointed out on a youtube comment discussion, Fred gives you even more than that, but the observations above are all you need to serenely solve a diabolical-rated sudoku.

That's all for now folks - I still have one further follow up on this subject, again linking together some of the subject matter I've been discussing recently.

There shined a shiny demon, in the middle of the road

And I made the first grid that came to my head

Just so happened to be

The best grid in the world

It was the best grid in the world

Look into my eyes, is it easy to see?

One and One go where?

Two and One must be?

It was destiny

More on this one later, especially for my dearest readers whose memory might not go back quite as far as 2008, but also for all my dearest readers who have enjoyed the recent discussions.  

And although this is just a tribute to a legend of nikoli.com, I also think it's one of the better Sudokus I've ever put together.  For whatever that's worth.  Enjoy!

   #351 Sudoku – rated 8/10 [Very Hard]

Edit: I'm having second thoughts about the rating of this puzzle.  I initially thought I wouldn't have the balls to put something like this into a sudoku competition, because people might end up guessing anyway.  But on second thoughts (see the comments for more thoughts), maybe I would.  In which case that 10 might get downgraded to an 8 or 9.

All puzzles © Tom Collyer 2009-20.

Tatooine Sunsets and Partitions of Latin Squares

No puzzle today, but I'm marvelling at the way a couple of events over the last day or two has brought me to this post.  I am very excited about all of it, and I'm probably going to have a bit of trouble keeping this post clear and coherent, so let me first post the main link to this video by Trevor Tao, which is a demonstration of unbelievable genius sudoku solving.

• Tatooine Sunset Sudoku and the 9-Dimensional Wonkyfish

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!

• Tatooine Sunset Sudoku and the 9-Dimensional Wonkyfish

The video skips over some of the details a bit quickly, so I'm going to add a couple of observations.

1. 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.
2. 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 DC
   EA EB EC
   FA FB FC
3. 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.
4. 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!
5. 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.
6. 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.
7. 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!
8. 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!