Toroidal from World Sudoku Championships

For fans of Killer Sudoku, Samurai Sudoku and other variants

Toroidal from World Sudoku Championships

Postby motris » Tue Mar 14, 2006 4:27 pm

I'd like to thank Wayne for his excellent retrospective on the World Sudoku Championships. You can read it here.

I promised in an earlier message to try to post the toroidal puzzle from the playoff round that resulted in 3 solvers with 1 square and me with a correct solution but barely in the 15 minute time limit. Wayne's description of my "crumpling" came from two things - one, finally finishing the puzzle in time after rushing during the last minutes to cleanup the final cells and two, knowing I had just made the finals which was always my goal. I would only learn a couple minutes later that no one else had filled more than 1 square.

The basic premise of the toroidal puzzle is that, in addition to the irregular shape, the puzzle's left and right edges and top and bottom edges must wrap together. The shapes still must uniquely hold just 1 to 9 as do the rows and the columns. For example, the 4 in R1C1 is connected as a region to these 8 squares (R9C1, R8C1, R8C2, R7C2, R6C2, and, in the other direction, R1C9, R2C9, R3C9).

I do not recommend this puzzle for the faint of heart. I will gradually give some "hints" to work into this puzzle for those who are interested. I am personally interested to see what logical routes into the puzzle exist. I've found two but only one that is actually satisfying and which also happens to be the route I used in the competition.

Image

Thomas Snyder
motris.livejournal.com
"All Work and No Sudoku Make Jack a Dull Boy"
Last edited by motris on Mon Feb 04, 2008 4:20 pm, edited 1 time in total.
motris
 
Posts: 71
Joined: 13 March 2006

Postby emm » Tue Mar 14, 2006 11:33 pm

Thomas, thanks for your riveting accounts of the championship – they’re as gripping and well written as some of the best fiction I’ve read lately! I’m not sure how the other competitors got past the penultimate round – how did they eliminate the slowest if 3 didn’t even finish? I certainly think you should have won and if I was you I’d feel a bit hard done by, but anyway congratulations on reaching the final.

I’m congratulating myself on finding the one single that I suppose was the one everybody got and showing a huge amount of will power and common sense, I’m putting this toroidal ( why is it ‘ doughnut-shaped’? ) away until you or someone gives me a hint. A new rule of logic is very intriguing.
emm
 
Posts: 987
Joined: 02 July 2005

Postby Moschopulus » Tue Mar 14, 2006 11:46 pm

em wrote:I’m putting this toroidal ( why is it ‘ doughnut-shaped’? )


Imagine making a doughnut out of a square piece of paper, as follows:

First you tape two opposite sides together, making a tube/cylinder.
The two ends are circles.
Then you bend it (imagining the paper is magically rubber) and attach the two circles to each other.
Hey presto, you have a doughnut....

See here for example
http://www.southernct.edu/~fields/anim/torus.html

Now imagine the sudoku is written on the paper.
The groups that go off the top reappear at the bottom, and those that go off at the right reappear at the left.
Moschopulus
 
Posts: 256
Joined: 16 July 2005

Postby motris » Wed Mar 15, 2006 12:21 am

The playoff structure was very flat. It started with 9 competitors and each got the same puzzle to solve as the world's press took note of every number written with digital picture after digital picture (and yes, they were distracting to me for the first couple puzzles until I got used to solving on stage, particularly in the first round when they were actually using flash photography from behind my easel directly into my eyes).

At the end of 15 minutes, your score was equal to the number of correct squares minus the number of incorrect squares in your grid at that time - blanks being worth zero (It seems that, in general, you only got credit for the givens if you finished the whole puzzle but I don't know how consistently this was applied).

If you finished the puzzle before the 15 minutes, then you could declare that you were "finished" and that would lock in your score and a time. In only one round did all competitors solve the puzzle, making the slowest to finish the last. After each puzzle, the field winnowed by 1 and then the playoff continued again. Points never carried over.

So, in this format, doing well did not necessarily matter in any round as much as just not being last (that is until the final puzzle). In this particular penultimate round, the three other competitors tied with a score with 1. Ties were broken by your seed entering that day. My teammate Wei-Hwa was seeded 2nd and Jana, the world champion, was seeded 8th, so the person eliminated was Tetsuya Nishio, the 9th seed from Japan, the puzzle creator who originally introduced Sudoku to Japan and has written many many interesting puzzles and variants of Sudoku over the years. This was a sad loss as Tetsuya was solving incredibly well in the playoff that day and, if not for the difficulty of this puzzle, would likely have won had he made the classic final. You can see the playoff round scores at this site.


It was a slightly unfortunate structure in my mind, but I knew the structure going in. We all did. I have some suggestions for how it should change the next time to reward people who perform strongly more such as doing something like a "sudoku relay" for the playoffs so that you solve a puzzle, go to the next and use your solution to fill in givens, and continue like that. It may remove the drama when the fastest solvers get leads on the competition, but I think it cleans up the system a little bit in determining a winner.


Re: giving hints to solving the puzzle, I intend to do this very thing. I will post a (vague) starting hint tomorrow that will hopefully get some people to start seeing the kind of region connections you need to do in your mind to break into this puzzle using logic.

Thanks for your comments em - I hope my recount of the two days of the WSC that I will be writing soon will be interesting and excite people about the WSC next year. I also hope to start some discussion on the value of Sudoku variants in expanding the puzzle of Sudoku (the WSC had many variants, and may be criticized by purists for this, but I think made the competition much more interesting for having them). Competitive sudoku solving competitions can become a spectator sport (that seems to be Pappocom's beliefs from my conversations with him) and maybe my account of the event can contribute to this trend. Until now, Sudoku has been a primarily personal activity - it can now become a "mental sport".
motris
 
Posts: 71
Joined: 13 March 2006

Postby udosuk » Wed Mar 15, 2006 8:03 am

With 9 final participants, how come they didn't implement 8 rounds in the finals, but only 7 and make it 1-out-of-3 in the final round? I think it would be much fairer and more convincing if there was a 1-on-1 round 8 where the final two could square it off, like in any respectable sport event...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby HATMAN » Wed Mar 15, 2006 3:39 pm

Udosuk

Are you saying that the football league is not respectable?

HATMAN
HATMAN
 
Posts: 203
Joined: 25 February 2006

Postby motris » Wed Mar 15, 2006 3:53 pm

So I promised a starting hint. This number won't necessarily get you much farther in the puzzle, but if you can make sense of why this placement is forced, you can maybe see why another placement which is much more important is also going to be forced.

Hint #1: R2C6 (the square directly above one of the 9's) must be 4. Why is this?
motris
 
Posts: 71
Joined: 13 March 2006

Postby tarek » Wed Mar 15, 2006 4:13 pm

Oh...

So it is a form of sudoku variant, boxes are molded into other shapes but still contain 9 cells...similar to the ones gaining popularity in Japan....


it shouldn't be that different from your normal "vanilla" one, you have here A snake-line elimination replacing your box-line elimination....Fishes should still be valid as they are formed & eliminate in lines & colouring should also be possible...


Now because the shapes are all geometrically identical......would the final solution be different if the clues were the same but the vanilla rules are applied:?: (Just a thought), I think i can tell the result very quickly though:)

A killer version of all these variants sould increase the twist

Tarek
User avatar
tarek
 
Posts: 2622
Joined: 05 January 2006

Postby CathyW » Wed Mar 15, 2006 10:38 pm

Thanks for posting the puzzle Tom - a fascinating variant. Like Em, I've got the one digit that presumably everyone else managed in r3c7.

Having tried the irregular sudoku from the samples on the WSC website http://wpc.puzzles.com/sudoku/WSC_sample.pdf, I'm not sure that some of the usual tactics will be of any help. It can be hard enough spotting some of the 'fish' without the patterns being distorted!

Think I'll certainly need a few more hints when you're ready ...

Cathy

PS Was there a Sum Number Place aka Killer Sudoku? (My favourite variant):)
CathyW
 
Posts: 316
Joined: 20 June 2005

Postby motris » Wed Mar 15, 2006 11:14 pm

CathyW, there were a couple sum (aka killer) sudoku although none in the playoffs. I honestly think its my strongest type as I tend to do even the hard ones in only a handful of minutes (credit my years of doing cross sums/kakuro puzzles). They also had other mathematically-inspired sudoku such as a multiplication sudoku- think killer but with products.

I can't share the actual competition puzzles- one condition on which the WPF works is that individual countries get rights to publish the puzzles in their countries to help subsidize their teams- but they should be published sometime in the future. Yes, I realize I posted the toroidal but I figure the press took enough photos of that puzzle and the final puzzle that its almost public domain by now.

However, the "instruction booklet" for the WSC contains reasonable examples of all the variants that appeared for those who are curious. Feel free to download it here and try them out. The "mechanical" cannot be solved but was a really cool puzzle on transparencies where numbers could rotate and mirror and you had to reassemble a sudoku grid that could be solved. The "cubic" and "word" examples are unfortunately non-unique. All the rest are solid.
motris
 
Posts: 71
Joined: 13 March 2006

Re: Toroidal from World Sudoku Championships

Postby r.e.s. » Thu Mar 16, 2006 5:56 am

EDIT (posting removed):
I'd incorrectly applied the Law of Leftovers by trying to use a single "vertical" line instead of partitioning the toroid into two disjoint sets of whole columns. However, using a boundary consisting of two "vertical" lines to define such a partition, the LoL can be applied ...
Law of Leftovers (LoL)
Imagine a boundary partitioning the puzzle into any two chosen groups of whole rows or columns. Now shift this boundary -- adding some cells to, and removing an equal number of other cells from, the enclosed area -- so as to contain a group of whole jigsaw boxes instead of the rows or columns originally enclosed. Then the two sets of cells -- those added and those removed -- will contain the same set of digits.

Unfortunately (afaics), in the present puzzle this will result in balanced "leftover sets" of size 6, rather than size 3.
Last edited by r.e.s. on Mon Mar 27, 2006 8:03 pm, edited 2 times in total.
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby motris » Thu Mar 16, 2006 2:06 pm

r.e.s. - your analysis is fair. I did, as I got a couple digits placed, begin to use the repeating triplets to fill in the rest much faster. My only rating of "difficulty" comes from how the puzzle played out in competition. Perhaps its trying to solve this puzzle on an easel in front of everyone that takes it from the moderately difficult you state to the difficulty actually in play.

My one question for you is how you apply what I'll call the "toroidal" constraint - namely all triplets repeat - before you have a complete triplet filled in. Provided you are getting your placements a-f without strictly using LOL (I got them without LOL), I'm fine with using LOL to fill in the whole remainder of the grid with the three unique triplets. I think my actual order in the competition for these six placements was a, c, d, e, b, f. However, once I had them, the whole puzzle became simply a matter of placing triplets using LOL as you state.

Until you have those two light blue triplets filled-in, I think you have to "assume" the triplets repeat to make headway, and while toroidals may only ever have repeating triplets - every example I've seen so far does - this was not an assumption any of us in the competition seemed willing to make until the two offset triplets on the grid force it to be true.
Last edited by motris on Thu Mar 16, 2006 10:42 am, edited 6 times in total.
motris
 
Posts: 71
Joined: 13 March 2006

Postby motris » Thu Mar 16, 2006 2:11 pm

Hint #2 - if you don't follow r.e.s.'s LOL steps, this was the logical step that I saw to allow my second placement and then the whole puzzle began to fall in place. After R3C7, you want to try to place a 9 in that same shape at either R4C7 or R7C5. However, one of these placements causes a necessary problem if you use the same logic I implied for the Hint #1 placement. See if you can tell why one of those two nine placements cannot be used.
motris
 
Posts: 71
Joined: 13 March 2006

Re: Toroidal from World Sudoku Championships

Postby r.e.s. » Thu Mar 16, 2006 5:57 pm

EDIT: Posting removed. (Invalid application of the "Law of Leftovers" to the toroidal case.)
Last edited by r.e.s. on Mon Mar 27, 2006 5:34 pm, edited 1 time in total.
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby CathyW » Sun Mar 19, 2006 2:57 pm

It's no good:( I'm still stuck. Please can you explain the logic involved in placing the 4 at r2c6. Maybe then I can work out where the 9 goes in the box that has 3 at r3c7, and make some progress.
CathyW
 
Posts: 316
Joined: 20 June 2005

Next

Return to Sudoku variants

cron