The New Sudoku Players' Forum

[motris]

CathyW, the logic I used takes advantage of the shape of the pieces to force placements in particular columns. When I look at the puzzle, I see 9 pieces that touch each other along an upper-left to lower-right diagonal. Each of these 9 pieces has a "left" column, a "middle" column, and a "right" column. R5-7 C4 for example is the "left" part of the cruical piece for Hint 1.

In any two pieces that are touching each other (and by touching, I mean sharing 8 cell edges, not just barely touching at the top and bottom of the piece), if the same number occurs in the "left" part of those pieces, then it must occur in the "left" part of all 9 pieces. Similarly, if the same number occurs in the "right" part of those two touching pieces, then it must be in the "right" part of all 9 pieces (the rule does not apply to the "middles"). The reasoning follows:

Consider two touching pieces that both have the number X in the "left" column of those pieces. Now, there is a piece that connects to the left of those two pieces. The X in the two existing pieces blocks the column for the "middle" and "right" part of that piece, so the X in the third piece must be in the "left" as well. As this is on a torus, the logic extends to all 9 pieces.


Let me explain then the placement of the 4 in R2C6. The only other placements of the 4 in that piece are in C4 on the "left" of that piece. This would then force all 4's to be in the "left" because of the 4 at R8C5 in the "left" of the connecting piece. But, looking at R1C1, you see this is a problem.

Here's a detailed reasoning. If you place a 4 in C4 (R5-R7), then in the next piece to the left, you'll see that the only places remaining for a 4 are in C3 (R4 or R5) as both C4 and C5 already have 4's. In the next piece, the 4 must now be in C2 (R3-R5) as both C3 and C4 already have 4's. But now there is no place to put the 4 in the next connecting piece. Because of the 4 in R1C1, in the "middle" of that piece, you cannot put a 4 in C4 at R5-R7. So R2C6 is 4.


The 4 is rather hard to see, I admit. The number I saw very easily is that a 9 cannot be at R4C7. Put the 9 in at R4C7 and then start placing 9's in connecting pieces. You'll hopefully see how the 9's begin to propagate in the "right" of the pieces to form a diagonal, which then causes trouble 5 pieces away. Once you can exclude 9 from R4C7, you can place 9 at R7C5.

Once you have that 9 placed (and eventually the 4 from hint 1), you can really start to solve the puzzle. The early placements I got are almost exactly the same as the ones r.e.s posted so just try to get those logically if you are stuck at where to go.

[CathyW]

Thanks for the comprehensive explanation Tom. It was certainly easier to follow the reasoning for placement of the 9 at r7c5 but once I'd got the hang of the triples in the column sections it flowed quite nicely and I'm pleased to say I do now have a solution Interesting that when reading down the columns the (531) triples are all in that order.

Would it be a general rule in this type of puzzle that you never get consecutive diagonal cells being the same number? This would permit early placement of 2 at r2c5.

[motris]

Your solution sounds correct CathyW - (un)fortunately, the (531) triples don't vary at all in the puzzle. I noticed this my second run-through, not in the competition, but it makes it much much simpler once you have gotten into the puzzle a reasonable bit.

In response to your question, you can certainly have some diagonal cells being the same number - there is certainly the very trivial version of this puzzle in which all the numbers lie along a diagonal - but I am not sure if you can have a couple diagonal neighbors (say just 2 2's that are diagonal neighbors) without the rest lying in similarly fixed positions. What I am interested in looking at now is (i.) can I prove for these toroidal shapes [from the WSC and the 2005 USPC, the two toroidals I've seen] that triples of digits must always repeat and/or (ii.) can I generate a puzzle with these, or other, toroidal shapes where triples (or other fixed numbers of digits based on the shape) need not repeat. My sense is these shapes may be limited, but other tile-able shapes will clearly not be. As a simple demonstration of this, imagine any regular sudoku puzzle but shifted over say one row and one column to make a "toroidal" version with wrapping around the edges. No one would claim a regular sudoku needs to have the same 3 digits in each column piece repeat; there are far too many counterexamples to count.

While I am proud of having solved the toroidal during the competition, I find the repeated occurrence of what I call the "triplet weakness" a little unsatisfying for the puzzle. It turns out, if you just assume that triplets repeat, there is another way into the puzzle that doesn't involve getting 9 at r7c5 or any other digit with clever logic. Basically, after you place the 3 in r3c7, you know that 5's and 3's occur together. This then forces a 5 in r3c5 as it cannot be in r5c5, which forces a 5 in r4c3. This now places a 5 and a 1 together, with an empty space. Using (531) now all linking together, you can fill that empty space with a 3 and then proceed to quickly fill all the 531 triplets. Also, you'll see that filling the (531)'s fills r4c7 which was one of only two options for the 9 so that gives you r7c5 for the 9 which then tells you 4 and 9 link. You have in the givens that 4 and 8 link (c1 at r1, r8). So this gives you (489) and (267) as the remaining triples. Its somewhat dissatisfying that in this puzzle you could "guess" that triples always repeated and get to the answer very fast.

[garethm]

What I am interested in looking at now is (i.) can I prove for these toroidal shapes [from the WSC and the 2005 USPC, the two toroidals I've seen] that triples of digits must always repeat and/or (ii.) can I generate a puzzle with these, or other, toroidal shapes where triples (or other fixed numbers of digits based on the shape) need not repeat.

I just came across this discussion and thought I'd try generating some of these puzzles with my creator, so I entered the wrapping polyomino tile pattern into my creator and made a few (well, 72 was how many I got in a minute or so) puzzles - the actual puzzles have the number of givens going as low as 12, interestingly, out of just those 72 samples.

Of the solutions I've checked, some but not all have the same four triplet pairs as highlighted earlier in this thread. For example puzzle 72 doesn't seem to show any patterns that I've spotted yet.

Anyway, I thought I could attach stuff to this message but apparently not so I've put them up on my website:
http://www.dosudoku.com/toroids.php


Gareth

[motris]

Thank you so very much for posting this Gareth - it is really exciting to see that the hypothesized triplet problem is not at all real (a comment on another sudoku forum I read before the WSC made a claim that it was always the case but I never chose to believe it). I'm glad to see that assuming triplets repeat cannot be safely done on a toroidal puzzle. I'll try my hand at your 12 given puzzle later when I have some time.[/i]

[r.e.s.]

garethm ...
Thanks for the enlightening counterexamples to my toroidal mis-application of the "Law of Leftovers".
(I've edited those postings.) Your example #71 is especially good:


[2007-04-05: Updated link address.]

[garethm]

Your example #71

Thanks! Glad it was of use. Just for completeness here's the puzzle I have that goes with that solution:



Gareth

[garethm]

Well I've now tried solving "puzzle 72" and after 50 minutes I had filled in 21 numbers, at which point I decided that was enough (and I couldn't see anything else to do).

The creator was set to only use simple solving rules - it doesn't even require consideration of tuplet sets or anything like that. Basic eliminations and looking at region intersection is all that is needed. But even knowing that, I still can't see what move to make next...


Gareth

[motris]

I got your 72 in about 18-20 minutes, but I did use the "left" and "right" rule I discovered in Lucca to help, seeing that one number was always in the lefts and one number always in the rights pretty early on. Its an awesome puzzle (I guess I'm a sadistic one). The shape makes it much harder to apply standard rules and the wrapping around the edges makes the visualization that much harder. These are real toughies, and having no "cheat" like triplets that keep popping up makes you work for each and every placement until the end. Kudos to writing such a versatile sudoku generator that you can do irregulars and toroidals this easily.

71 is not as satisfying as it has two repeated diagonals which you can (almost instantly) fill in. Then it gets to the same difficulty as the other, possibly a little harder, but with the quicker first 14 or so placements, my time was about 16 minutes. Again, the "left" and "right" rule helped, with two forced left digits and two forced right digits, but otherwise these two puzzles were great.

It seems that the flavor of the puzzles is that either 0, 1, 2, or 3 [ the last of these being a trivial puzzle and never occurring in your set] of the left and right digits must always repeat (but the same number of matched on each side). However, the left/right rule will still apply provided you can learn which of these 3 classes the puzzle fits into. If its 0, then you can always eliminate particular boxes for some of the digits. If its 1, then you have 2 numbers that are always in some set of boxes. And so on. I hope someone else understands this, but I find this discovery interesting. I would guess from my experience solving these two from Gareth that the 0 left/right class is the hardest to solve, provided it is not trivially using repeating triples like the one from Lucca.

[RW]

Thanks Tom for bringing up this toroidal puzzle. It's a very interesting variant, especially with this "left" and "right" rule you are introducing.

I found this thread last night and decided to try the puzzle before reading any hints, never seen a puzzle like this before. First 15 minutes gave me 4 numbers (maybe I should have went to Lucca...). The next 15 minutes gave me 15 more solved numbers and then I suddenly saw the repeating triplet pattern - 2 minutes to solve the rest of the puzzle. I guess you are right, the triplet pattern is a weakness in the sence that it makes the puzzle a lot easier. At no point did I consider the left and right rule, so after reading the rest of this thread I think any toroidal puzzle I do in the future will be a lot easier.

I still want to point out that these puzzles can also be solved with normal techiques. If you have a twisted mind that can handle these twisted boxes, you can find singles, pairs, triplets, forcing chains, nishio reductions and even uniqueness reductions just as well as in any other puzzle.

RW

[Pi]

I just got the final puzzle and wondered if anyone knows the winning times. I did it in 14:12.

I think that's quite good. I used 2 X-wings

[Pi]

Sorry to double post:

The Toroidal beat me. i only got 1 number in 12 mins, then gave up

[motris]

The world champion, Jana Tylova, finished the final puzzle just under the 15 minute time limit (actually, she left one square blank in her hurry as the time was running out on the round, but it was as done as it needed to be to win the round and therefore the competition).

I would state a word of caution though before you compare your times with pencil and paper on a puzzle in front of you to solving on an easel in marker. I certainly found that the combination of having to move my head to see all the numbers and/or needing to step back from the easel made it both much harder to apply my usual solving style and certainly slowed me a fair bit. Still, 14+ minutes on this puzzle is a very respectable time and beats my own on stage time by several minutes (if they had let me finish the puzzle to completion, instead of stopping at 15 minutes, I would have likely taken ~18 minutes).