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]

11 comments:

  1. Re. the poor rating on the classic sudoku; I think this is grounded on an certain people having an anathema against classic sudoku on the portal, branding them ‘boring’ and ‘not adding to the thrill of the portal’ (I know at least one user who was openly stated this, whom I shall not name). Which is nonsensical. I personally think that coming up with an original classic sudoku technique which is executed well is far more impressive than most of the puzzles on the portal.

    ReplyDelete
    Replies
    1. I don't think the poor ratings are due to people who don't like classic sudoku. Most probably these people don't solve portal's classic sudoku.
      I think it's most probably some people who didn't read all stuffs concerning the new technique. They just solved the puzzles, probably had to guess the solution, didn't get the trick. In similar conditions, probably I would not give high ratings for these puzzles.

      Delete
  2. I was skeptical concerning the utility of this new technique, thinking wrongly that this new technique could always subsituted by more common easy techniques.
    These sudoku are very impressive !
    What baffles me even more than the discovery of a new classic sudoku technique, is that it applies wider to all latin squares.
    Latin squares are so much known since centuries, I wonder if this trick was documented before or of it is completely new.

    ReplyDelete
  3. This is just a thought I had after a very superficial look at the question, but my feeling is that these "patterns" will not have any practical applications on basic latin squares, but that the third constraint of sudoku is what makes them potentially powerful. In any case I was very impressed by these two classics, especially the fact that the first one goes from pretty tough to trivial in just one application of the theorem. Spectacular!

    ReplyDelete
  4. I've been out of the loop for a long time so I hadn't noticed this "new" technique, but let me tell you, it isn't new!

    It's equivalent to a technique known as the SK loop, named after the person who first observed it, Steve Kurzhals. Back in the day there was a very active forum called the Sudoku Players Forum and they developed a lot of very interesting theory between 2005 and 2010 before the forum crashed. A partial backup was restored but a lot of the old stuff was lost, and only a few of the old members stayed around trying to re-formulate all of the lost theory and come up with new stuff.

    Anyway, if I remember correctly, the SK Loop was first formulated in about 2008, where it was used as the first step in the solution of one of the hardest known puzzles at the time, the Easter Monster. SK Loops were later generalised and are now probably best known as a special case of a technique known either as MSLS or Rank-0 Logic, depending on whose nomenclature you want to use.

    There are plenty of other exotic techniques that were developed between 2005 and (roughly) 2013, after which point the new forum has been more concerned with puzzle generation and classification of low-clue puzzles than it has with Sudoku solving.

    In case you want to start searching for material about the SK-Loop, be aware that SudokuWiki/Scanraid claims to have an implementation of the SK-Loop technique, which it took from another solver called Phil's Folly, but neither of them have implemented it correctly, so take it with a pinch of salt.

    Anyway, here's the SK-Loop you can find in the first puzzle of this post, in the standard SK-Loop notation:

    (34=78)r4c56 - (78=14)r4c78 - (14=59)r56c9 - (59=12)r78c9 - (12=69)r9c78 - (69=23)r9c56 - (23=89)r78c4 - (89=34)r56c4 - SK Loop

    It leads to the following eliminations:

    - 78 eliminated from the cells in Row 4 not part of the loop
    - 14 eliminated from the cells in Box 6 not part of the loop
    - 59 eliminated from the cells in Column 9 not part of the loop
    - 12 eliminated from the cells in Box 9 not part of the loop
    - 69 eliminated from the cells in Row 9 not part of the loop
    - 23 eliminated from the cells in Box 8 not part of the loop
    - 89 eliminated from the cells in Column 4 not part of the loop
    - 34 eliminated from the cells in Box 5 not part of the loop

    As you can see, these are exactly the eliminations you can make from applying the technique as Phistomefel described it.

    The partially-restored forum now lives at http://forum.enjoysudoku.com/, although, as I said, a lot of the posts developing this theory were lost. Most of what is written there is pretty intractable - they don't have a gift for explaining things clearly, and most new posts are written under the assumption that the reader is a long-time inhabitant of the forum. But with enough willpower, you might find the following posts about SK Loops interesting:

    - A summary of lots of known exotic patterns, including SK-Loops and related loops: http://forum.enjoysudoku.com/exotic-patterns-a-resume-t30508.html

    - Some classification of SK-Loops and related loops: http://forum.enjoysudoku.com/sk-and-related-loops-t35883.html

    - An exploration of SK-Loops and related loops: http://forum.enjoysudoku.com/domino-loops-sk-loops-beyond-t32789.html#p247688

    The forum is a very large rabbit hole that it's possible to spend a lot of time in, but you need to be determined to understand some of the wackier techniques. True enthusiasts can try reading David P. Bird's "JExocet Compendium" or getting through the enormous "Ultimate Fish Guide" which (eventually) comes up with a presentation of Fish techniques that generalise a whole host of known solving techniques, including (!) the SK-Loop.

    ReplyDelete
  5. Very interesting, thank you Sam. I had read about SK-loops many years ago, but it was shortly before I lost interest in studying extreme classics, and the bit I read back then made the technique look powerful but hard to spot and inapplicable without having all pencil marks written, so I did not recognize it here.

    I know Qiu Yanzhe and a couple other Chinese authors are users of the forum and I had actually planned to ask him if people there were aware of these patterns; this answers my question.

    Anyway, a bunch of puzzles have been made since the "discovery" (mostly variants) and some of them make use of it in very creative ways, you should really have a look at that when you can.

    ReplyDelete
  6. Hi both - thanks for the post. I am writing a new post on a new discovery which generalises Fred's intersection theory. It's mind blowing!

    What I would say re this not being very new after all is this. Whilst there may be an equivalence to SK Loops (I haven't really looked in to them), the notation and set up for that particular technique is, well, technical and a bit arduous and difficult to follow. I think the way Fred makes his argument in terms of partitioning rows into 2 sets and columns into 4 sets to come up with a 2x2= 4 set partition of the grid is far more elegant and intuitive to understand.

    Put another way, using Fred's theory I can make the initial breakthrough without making any pencilmarks at all - I'm not I can say the same thing re the SK Loop set up.

    ReplyDelete
  7. Hi Tom,

    I mentioned in my post that SK-Loops are now recognised as a special case of something called Rank-0 Logic. I expect this will be very close to your generalisation of Fred's presentation.

    I'd be interested in reading a draft of what you have so far so I can see how much it overlaps and whether it can in fact be made even more general than you will have already discovered!

    ReplyDelete
  8. Yes, this way of visualizing the "loop" makes it infinitely easier to use. It is certainly why I did not recognize it; what I read about SK-loops back then only used chain-style notations and did not convince me that I could ever use them in competitive solving, or for setting up some interesting puzzle.

    The knowledge may not be new, but the perspective is.

    ReplyDelete
  9. To give you a flavour of this Rank-0 logic thing as applied to the puzzle in question...

    Consider the following sets of possible placements:

    Set A
    ------

    - All of the possible placements in r4c5
    - All of the possible placements in r4c6
    - All of the possible placements in r4c7
    - All of the possible placements in r4c8
    - All of the possible placements in r5c9
    - All of the possible placements in r6c9
    - All of the possible placements in r7c9
    - All of the possible placements in r8c9
    - All of the possible placements in r9c8
    - All of the possible placements in r9c7
    - All of the possible placements in r9c6
    - All of the possible placements in r9c5
    - All of the possible placements in r8c4
    - All of the possible placements in r7c4
    - All of the possible placements in r6c4
    - All of the possible placements in r8c4

    Clearly exactly 16 of these possible placements must be true in the solution.

    Now consider the following set of possible placements:

    Set B
    ------

    - All of the places 7 can go in r4
    - All of the places 8 can go in r4
    - All of the places 5 can go in c9
    - All of the places 9 can go in c9
    - All of the places 6 can go in r9
    - All of the places 9 can go in r9
    - All of the places 8 can go in c4
    - All of the places 9 can go in c4
    - All of the places 3 can go in b5
    - All of the places 4 can go in b5
    - All of the places 1 can go in b6
    - All of the places 4 can go in b6
    - All of the places 1 can go in b9
    - All of the places 2 can go in b9
    - All of the places 2 can go in b8
    - All of the places 3 can go in b8

    This second set has two important features. Exactly 16 of them must be true. But also, it includes all of the possible placements from Set A.

    Since Set A also included exactly 16 truths, the conclusion is that all of the placements in Set B that are not in Set A must be false, and can be eliminated.

    That's quite verbose written out, but quite simple to visualise (in my mind, anyway). This is the perspective from which SK-Loops are best understood to the modern solver.

    ReplyDelete
  10. Well I've gone ahead and posted anyway Sam, I only started writing the draft after my comment here :-)

    I do wonder about your explanation, and particularly the reference to boxes that you are making. Fundamentally this intersection theory (as I've understood it so far) works equally well for Latin squares as it does for Sudoku. Granted if you Fred's theory to prove Phistomefel, you end up an equation saying something like (1-9) + 16 cells = a set of 25 cells initially. But then you go one step further because you can subtract a 3x3 box from the 25 cells on the RHS, and then that lets you take off the extra (1-9) from the LHS.

    ReplyDelete

Contact Form

Name

Email *

Message *