Pinned post

Thoughts on my place in the puzzling community

This post is going to be a bit of an outpouring, in lieu of my withdrawal from the puzzling community for as long as it takes to get my mojo...

Tuesday, 20 October 2020

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, 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.

Monday, 19 October 2020

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:

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:
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.

Friday, 16 October 2020

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 10/10 [Extra 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.

Friday, 9 October 2020

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.
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:

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.
  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!

Thursday, 10 September 2020

Puzzle 350 Sudoku

So before I really get started, I wanted to draw the attention of my dearest readers to a really remarkable puzzle I've come across in the last day or two, courtesy of 胡蒙汀(Hu Meng Ting) from China.  I'd probably give this one an 8/10 for difficulty on my scale.


Scanraid rates this as a diabolical grade puzzle requiring all sorts of fiddly techniques to get through.  But it is also rendered much easier by a quick application of the so-called Phistomefel's theorem.  This, to the best of my knowledge, is first discussed here.  It's also been picked up and popularised by various cracking the cryptic videos, which I am too lazy to link to but I'm sure all my dearest readers are either already familiar with or else can find for themselves.

For various reasons, Hu's puzzle does not seem to getting the attention I believe it deserves in the logic masters community.  To me, this seems to be the first instance of a puzzle that really makes good use of the solving technique.  Previous versions of puzzles that have attempted to incorporate it have always had equivalent shortcuts using much easier solving techniques, and people had speculated whether this was of any practical solving interest.  Now we know!

Reading on in this thread I was pleasantly surprised to see a generalisation of the theory by Fred Stalder, which is well worth reading as well.

This will also help with another really remarkable puzzle, also courtesy of courtesy of 胡蒙汀(Hu Meng Ting).  This one easily gets a 10/10 for difficulty, and maybe even an 11 for the sheer genius of the puzzle


This one is unsolvable by scanraid, and is certainly not easy even when you are armed with both the theory, and the equally remarkable thread of hints to get you going - there is a lot of work to do to get through this puzzle, but it is just about doable.  I find this fascinating as what it really means is we are now shining a light on some of the hidden complexities underlying the structure of sudoku.  

Anyhow, I am very grateful to cdwg2000 for sharing these puzzles and the theory and I shall certainly keep an eye out for anything else that they share, hoping that they haven't been discouraged too much.

All this talk of new and exciting theory has also made me a little bit nostalgic.  I am going to offer up nothing related to this particular subject (although I'd invite my dearest readers to take another look at one of the classics on the 2020 edition of the UK Sudoku Championship if you're interested).  Instead I feel like I've got a pretty nice execution of an idea that once upon a time was done to death.  Enjoy!
    #350 Sudoku – rated 3/10 [Easy]

Contact Form

Name

Email *

Message *