Log in

No account? Create an account
15 April 2010 @ 10:29 pm
Friday Puzzle #45 - Just One Cell Sudoku  
(I will not be responding to particular types of comments to this thread, specifically ones such as "where are the WSC instructions?" or any others that really belong on the WPF Forum at the moment.)

So another week and some more WSC stuff to present. A very basic outline of the individual competition is now available online; listed on it is one of the big new projects we've been working on. If Tablecloth Sudoku was the puzzle style that Wei-Hwa and I created at the second WSC, Just One Cell Sudoku is the puzzle that the two of us created at the fourth "WSC", just after the Guinness Record round lunacy. Let me frame the concept in the way I see it first.

Chess Puzzles:Chess::Just One Cell Sudoku:Sudoku

Chess is a game of strategy played between two individuals. However, outside of any individual game, there is an established body of interesting game situations or strategies that can be presented as "puzzles" to someone familiar with Chess to test their powers of deduction and perhaps teach or expand the strategies they can recognize at a given board setting. I wrote several of them for GAMES Puzzlecraft #50 (April 2009), which taught me amongst other things how much I still have to learn about Chess.

Sudoku is a Latin Square-based constraint-satisfaction puzzle with a single solution but multiple cells to fill in to get to that solution. However, outside of any individual grid, there is an established body of solving strategies which can be presented as "puzzles" to someone familiar with sudoku to test their powers of deduction and perhaps teach or expand the strategies they can recognize at a given grid position. I wrote over two dozen of them for the WSC, which taught me amongst other things how few solving strategies I actually use when I'm solving at my fastest.

The hardest sudoku puzzles at a competition are almost always solved for speed using bifurcation and not logic by the best solvers. It is the dirty little secret I freely admit but one that leaves my performance on some puzzles much less satisfying than others. I won the Classic Sudoku title in Goa by guessing on an impossibly difficult puzzle ("Goes to 11") after having an edge in classics on three earlier, much much much more solvable puzzles. I won the overall Sudoku title in Goa by simply solving all of the puzzles very fast using logic, not bifurcation. Only one of the two titles matters a lot to me.

"Goes to 11" and the Guinness puzzle last year are obvious examples of competition "sudoku" where logic ISN'T EVEN POSSIBLE! for a human within the intended time constraints after a very small number of cells. This showcases a general problem with a potential goal of a sudoku competition to identify those solvers who have learned and can use the "fiendish-level" strategies. Sometimes it is not speed that impresses, but the depth of one's wisdom. Just One Cell Sudoku are meant to assess the latter by isolating single "sticking points" in the solving process that require various kinds of observations.

Rules: In Just One Cell Sudoku, each of the puzzles has multiple solutions for the entire grid but has an unfilled cell that is "fixed" in all of the possible solutions. Using standard/advanced solving strategies, identify this single cell that can be specified. For more advanced strategies, candidates will be given in the grids to assist in identifying the necessary deduction.

cyrebjrcyrebjr on April 16th, 2010 06:24 am (UTC)
I was able to do the first two in my head, but... we're supposed to do all this work for one digit?

As the Cockney said of the passenger train crash in Chicago: "Bloody el!"
(Anonymous) on April 16th, 2010 01:33 pm (UTC)
OK - whilst these meta-sudoku are an interesting thought experiment - and I'm glad you make the chess puzzle analogy, I have big big reservations as to their inclusion at the WSC. The biggest is they are no fun to do. The satisfaction in cracking a hard step in a difficult sudoku is that it allows you to go on to finish the puzzle. By definition, you can't do this here. Moreover, the pre-knowledge that you are looking for one hard deduction changes the way you look at a grid. Ditto the fact that most of the things you look for in chess studies are not the sort of things you seriously consider in a game.

Let me ask how exactly do you score something like this? I can only think that you do it by time. Do you rank people by how quickly they get it, or simply give them the points if they get it within a certain time. How long is that certain time - 30s? 1 minute? 2?

My point is that I think most if not all people at the WSC will be able to get these - eventually. In which case, it isn't really an absolute test of depth of wisdom after all, and more a test of just how quick you can be with harder techniques. Maybe that's what you were after in the first place, I don't know. I don't think it matters if the puzzles aren't any fun to do.

motrismotris on April 16th, 2010 03:42 pm (UTC)
By looking at our proposed round structure, you should see that with this competition we are trying to include the full range of sudoku difficulties, strategies, and variants, grouped in such a way that the individual disciplines will reveal how well solvers do different things. We have not excluded "impossible" puzzles (see 1500m round), but we have also not excluded "difficult steps" such as most solvers not on the clock would use and enjoy on those weekend Fiendish puzzles. These steps are undeniably part of sudoku - maybe not as you've seen it in the past at competitions - but certainly as would belong in a decathlon of sudoku that tests everything to find the world's greatest sudoku solver.
(Anonymous) on April 16th, 2010 10:08 pm (UTC)
Fell at the fifth hurdle
When I first heard the "just one cell" idea, I liked it. However, I hadn't realised just how hard I would find the puzzles to solve. I cleared the first 4 hurdles without losing stride. But then my stride pattern went to pot and I flattened the next one. In fact, I don't think I would have been able to solve any of the final 3 puzzles logically in a month of Sundays. Having seen the answers, I have subsequently come up with rather ugly deduction paths for each one but I'm convinced there must be more aesthetically pleasing ways of looking at these. Do you intend to publish logical solutions to each puzzle?

Tom will be amused because he knows that I start bifurcating once anything more difficult than an obvious X-wing appears.

By the way, I printed out some copies of the first 3 puzzles and handed them out at a coffee-break in our university common room. I did my best to explain the idea behind the puzzles. Ten minutes later, none of the puzzles had been solved and I had to put my colleagues out of their misery. These puzzles are hard.

But it may be invidious for a WSC competitor to engage in such discussion, so I'll leave it there and not pursue a continuation of this conversation.

David McNeill.

motrismotris on April 16th, 2010 10:14 pm (UTC)
Re: Fell at the fifth hurdle
I don't think we should discuss this much further here, but this Tom is also very amused that you say "I start bifurcating once anything more difficult than an obvious X-wing appears" and then you fell at the fifth hurdle.
(Anonymous) on April 17th, 2010 12:44 pm (UTC)
Re: Fell at the fifth hurdle

#5 took me a long while as well. That's generally since we don't see any xy-wings in any puzzles published in the UK, but actually it's fairly "obvious" in the notations given. #6 and #7 are swordfish (I hope that's not too much of a spoiler btw); the last one in particular seemed fairly reminiscent of all the things I was looking for trying to solve the World record puzzle, but weren't there. I suspect this is no coincidence. Actually, I think I got that one quicker than the triples one. Ever since the Times puzzles got easier (i.e. when they switched back to puzzler) it seems my triple spotting has regressed.

With regards to Jason's comment about 110 hurdles/1500m - If I had the choice, I'd have neither. Both are nice thought experiments to do on a lazy Sunday, but I think that doing either under time pressure will seem like a drag to me. We'll have to see...

motrismotris on April 17th, 2010 04:07 pm (UTC)
Re: Fell at the fifth hurdle
#7 was indeed meant to look like the world record puzzle with ~3 things in all places. I took out two corner digits as I couldn't get required global properties as desired but you are right for the similar feel of both.
motrismotris on April 18th, 2010 08:35 pm (UTC)
Re: Fell at the fifth hurdle
The Wiki now has a more full summary of how to solve these puzzles if you click on the individual strategy pages and the type of steps expected for the two presentations of this puzzle type. #6 is not a swordfish in any manner I am familiar with. It is resolved using Simple Coloring.
(Anonymous) on April 20th, 2010 06:18 pm (UTC)
Re: Fell at the fifth hurdle
I tried looking at this again, couldn't find the swordfish, stuck it into scanraid with only swordfish ticked, and it came up with nothing. Seems I saw what I wanted to see!

jdyer on April 16th, 2010 09:40 pm (UTC)
I'm wondering if this would be better in a computer game format, like a Puzzle-RPG where you attack enemies by clicking on particular squares on a Sudoku board.
(Anonymous) on April 17th, 2010 03:50 am (UTC)
That reminds me...
... of a puzzle type I thought of and which I have not seen implemented. Take a sudoku, place the possible candidates in all the unfilled cells, and then erase all the filled cells. Arrange it so that the filled cells can be uniquely determined, and the sudoku completed.

Perhaps you can construct some of this type?

Gerhard Paseman, 2010.04.16
motrismotris on April 17th, 2010 03:57 am (UTC)
Re: That reminds me...
Do you mean "Pencilmark sudoku"? Where all you get are candidates? That already exists but unfortunately I cannot find a quick example with Google and I don't have time to track down an example from past events. It was certainly part of WSC3 and WSC4.
cyrebjrcyrebjr on April 17th, 2010 07:05 pm (UTC)
Re: That reminds me...
It sounds like a variant (or rather, a further variant) of Pencilmark sudoku.

I believe the proposed rules go like this: The grid starts with a few empty squares; call these the "un-givens." The rest are filled with the pencil marks that would result from only the basic row/column/nonet constraints and the un-presence of the un-givens. The solver must fill in the entire sudoku grid, identifying the digits in both the pencilmark cells and the un-given cells.

But it seems to me that this just splits a sudoku grid into two independently-solvable quasi-sudoku. If a digit is present among the pencil marks in a nonet, it is obviously absent among the un-givens in that nonet, and vice versa. This means that a second grid can be filled in with pencilmarks for only the un-givens of the first grid.

In short, I don't see how deducing an un-given can impact the grid's pencilmarks, or how deducing the value for a pencilmark cell can alter the candidates for an un-given.
cyrebjrcyrebjr on April 17th, 2010 07:09 pm (UTC)
Re: That reminds me...
Oh wait, you already said that in response to zundevil below. Never mind.
(Deleted comment)
motrismotris on April 17th, 2010 04:04 pm (UTC)
I can see what you and Bastien are saying as what Gerhard meant. I do think that potential variation is not going to amount to much, simply because there is too much information in the sets of digits that tell you what is in that box, that column, or that row. I could take any particular one of those scanning directions in the examples I see above minus the large numbers and reconstruct the grid in half a minute. I'm not sure if there is any additional ripple to put to it to make it more interesting, but it is a novel suggestion.

[Edit: Actually, it was trivial on the most sparse grid. There may be an intermediate spot with ~40 digits in the grid where it becomes interesting. I'll explore this some other time and post here.]

Edited at 2010-04-17 04:14 pm (UTC)
(Anonymous) on April 17th, 2010 12:49 pm (UTC)
Tom.C said "The satisfaction in cracking a hard step in a difficult sudoku is that it allows you to go on to finish the puzzle."

I don't agree with this. For me the satisfaction is double when cracking a hard step : of course I'm happy because it allows me to solve the entire puzzle, but the simple fact of having cracked this step gives me a large amount of pleasure.

Despite of this, I am very mixed about "Just One Cell" sudoku. I like the idea of "countering the use of bifurcation", and I also find the rule itself interesting, but I am not sure that I would enjoy solving this kind of puzzles on a tournament. I would probably have more fun solving them without time constraint ; that's the way I like harder puzzles.
And I just hate given pencils marks...

Concerning Gerhard's question, I understood it just as Jason did. Basing on pencil marks, you would have to find out what were the givens. Don't know if one can build something interesting with this, but why not ?

Bastien Vial-Jaime - Ours brun
(Anonymous) on April 18th, 2010 12:01 am (UTC)
I only mention this because getting one hard step on a hard puzzle is often not enough to finish the hard puzzle; indeed you can make a reasonably clever deduction on one of these puzzles only to get stumped by something that requires even more which is beyond you - or at least beyond you in any sort of reasonable time.

In my opinion, that's even more frustrating: I'd have preferred to throw the puzzle away in disgust before the initial step (although being the puzzling addict I am I'd have doubtless come back to it anyway - the unfinished puzzle is the ultimate frustration!!)

(Anonymous) on April 21st, 2010 11:56 pm (UTC)
You can still use bifurcation!
I think these puzzles are an interesting experiment. They are really great in honing strategies, and if there was a ton available, I would use them to train my eye in finding the correct starting point into a puzzle. The 4th one is the best example of an X Wing that I have seen/used. But I found myself solving 5 and 6 by bifurcation. Each in 3 minutes time (which sounds like reasonable time for the championship). So, while your goal is to test solvers knowledge of advanced techniques, you might end up testing their ability to bifurcate. I mean choosing where to start, which subset of cells to cover, which configuration forces a solution vs. a contradiction in a smaller amount of writes is a skill, and whoever is good at it calls it simple coloring or forced chains or whatever based on the situation, but it is a type of skilled bifurcation for me. Probably somewhere there the line between a conscious advanced technique and bifurcation gets fuzzy.
So, while I am sweating anticipating these puzzles in Philadelphia ;-), I think I would like to have more to try at home - both for improving my eye for the available strategies and clues, but also for improving my bifurcation skill.
motrismotris on April 22nd, 2010 03:57 am (UTC)
Re: You can still use bifurcation!
This is an interesting point and deserves further comment. There is no set line at where logic ends and "guessing" begins. A technique such as the Y-wing is easy to prove is logically true, but may not readily be seen by many solvers. Because its deduction is fairly compact (involving 4 cells), and requires bivalue cells for the specific elimination, it also tends to occur at spots where bifurcations may begin. Therefore discovering a Y-wing by guessing is not going to be an uncommon occurrence, but at the same time a Y-wing is probably not a technique of guessing but a technique of logic.

My co-author onigame created the terminology for a puzzle solvable by just logical steps as "Sledgehammer-complete"; the name arises from whether his programmed solver, Sledgehammer, can solve the grid. He further diagrammed the concept here. It basically involves considering all possible relations between cells in a number placement set, and encompasses a majority of solving techniques including X-wings and Swordfish which arise from such set limitations. However, a Y-wing is not a deduction based upon such direct connections and is not part of Sledgehammer. Simple Coloring will not be either. This may place such steps in a grayer area of logic compared to other techniques. Certainly all techniques in Sledgehammer are based on logical deductions; the question is how many deductions not contained in the rule space of Sledgehammer are based on logic and which are not.

I personally consider a step bifurcation if you physically write the numbers down on the paper and work forward to see if it works or you need to erase. However, if you can find the contradiction by considering numbers in your head alone, then it is not guesswork. Simple Coloring and Y-wings fit into this latter area, where I can see them by imagining some placements, but I have not yet made a committed step to starting to write on a second grid, switching from pen to pencil or from black lead to a color, or any other means that would allow me to erase if my guess is wrong. I'd say any puzzle I can solve making all deductions in my head and just writing down correct numbers and no notes is a puzzle that contains only logical steps. This won't exclude bifurcation as a route to solve the puzzle or break through any particular step.

Edited at 2010-04-22 04:09 am (UTC)
(Anonymous) on April 29th, 2010 01:42 pm (UTC)
When I saw this type of grid, my first reaction was mistrust, perhaps because, as David, I don't overcome advanced techniques. But I try to do some, and I saw that, like classical grids, it is not impossible to solve them without knowing all those techniques. Perhaps it is more easy for someone who knows all these "wings" et "fish". It took me a long time to solve the last one, for example. Last grids are difficult, if you consider that hard classical grids have perhaps 1 or 2 difficult steps, if you solve it in, say, 15 minutes, perhaps without these 2 difficult steps, you could solve the grid in 3-5 minutes. This example to say that perhaps it take more time to solve "just one cell sudoku" than a classical grid not so difficult.

My only regret on that grids is that we can't use uniqueness techniques. Or more specifically, the uniqueness of solution (of the problem, not of the grid !) has to be used in a very different way.
For example, the fact that there is only one cell which has only one digit possible, says to you that if a digit in a cell involve others digits elsewhere, it is not the solution. I don't know if it can be very useful, but it deserves to be thought about.