Irregular Toroidal

For fans of Killer Sudoku, Samurai Sudoku and other variants

Irregular Toroidal

Postby r.e.s. » Mon Jun 05, 2006 8:15 am

The toroidals I've seen have a very regular tiling pattern, so I made this one for variety ...

Image

I'm curious what techniques people will use to solve this. (It has exactly one solution.)

Edit(1): For improved readability, removed the top & bottom borders of column 5 and the left & right borders of row 2.
Edit(2): The following will paste this puzzle directly into SumoCue:
SumoCueV1
=9J0=0J1=0J2=0J2=1J3=0J3=0J4=0J5=0J0
=0J0=1J1=0J2=0J4=2J4=0J4=0J4=0J5=0J0
=0J1=0J1=0J2=0J2=3J4=0J4=0J5=0J5=0J6
=0J1=0J7=0J7=0J2=4J4=0J4=5J5=0J5=0J6
=0J1=0J1=0J7=0J7=5J7=0J5=0J5=0J5=0J6
=0J1=0J1=0J7=0J7=6J7=0J6=0J6=0J6=4J6
=0J8=0J8=0J8=0J7=7J6=0J6=0J8=0J8=0J8
=0J0=0J0=7J8=0J2=8J2=0J3=0J3=0J3=0J3
=0J0=0J8=0J8=0J2=9J3=2J3=0J3=0J0=0J0
Edit(3): 2007-04-05: Update link address.
Last edited by r.e.s. on Thu Apr 05, 2007 9:11 pm, edited 3 times in total.
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby Smythe Dakota » Wed Jun 07, 2006 1:06 am

I haven't even been able to get started. There don't even seem to be any singles, not even one. Closest thing is, there are only two cells in row 8 where a 1 can go.

No wonder nobody has posted to this topic!

It is interesting that your puzzle has only 15 clues, below the thought-to-be-minimum 17 for a regular puzzle. And at least two of them are redundant, such as the 4 and 5 in the center column.

Bill Smythe
Smythe Dakota
 
Posts: 564
Joined: 11 February 2006

Postby motris » Wed Jun 07, 2006 2:53 am

After about a minute, I'd say I see at least one hidden single which is in R8. There's also a pointing pair that looks to get you R4C2 which then gets you another digit in R6. The challenge with toroidals is really just adapting techniques you know to very odd boxes that extend over the edges. If you get used to that, you can make progress.

I have put this puzzle in my pile to try but may not get to it for awhile as I'm focusing on non-sudoku in advance of the US Puzzle Championship. I'm glad to see it though and hope that people continue to post these toroidal variants as I really like the challenge.
motris
 
Posts: 71
Joined: 13 March 2006

Postby motris » Wed Jun 07, 2006 2:59 am

On printing it out, it seems that the top/bottom of column 5 should be dashed as well for that nonet. Its clear what is intended, but the shape of that box is a little weird.
motris
 
Posts: 71
Joined: 13 March 2006

Postby r.e.s. » Wed Jun 07, 2006 4:50 am

SD, here are some LoL cases that can be used in solving the puzzle ...

Image

A "Law of Leftovers" (LoL) for Toroidals:

Any pair of row or column borders in a toroidal grid partitions it into two disjoint sets of whole units (whereas just one such border is enough in an ordinary non-toroidal grid). In only one of these two sets can a line be drawn between the pair of borders without wrapping around -- call that one the "inside set". Now if the partitioning borders are deformed into tile borders that also form such a units-partition -- adding some cells to the inside set while an equal number are subtracted from it -- then the set of digits in the added cells must equal the set of digits in the subtracted cells. In the examples, the blue cells are added to an inside set, and must balance the equal number of red cells that are subtracted from it.

(I first saw the LoL for plain jigsaw sudokus in the tutorials at http://www.bumblebeagle.org/dusumoh/index.html)
--

motris, I've removed the pair of cell-borders you mentioned (and a similar pair on the sides) -- it is equivalent to the original. I hope you'll return with more feedback when time allows. Good luck in the USPC!

Edit: In the LoL, clarified the definition of the "inside set" of cells. The LoL is a very simple idea in spite of the wordiness of my description.
[2007-04-05: Updated link address.]
Last edited by r.e.s. on Thu Apr 05, 2007 9:16 pm, edited 2 times in total.
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby motris » Wed Jun 07, 2006 10:05 pm

As often happens, I bring a puzzle home and see it sitting on the stack and then when I hit a set of puzzles I don't want to do (this was a run of spokes puzzles in one of the Tuller/Rios Mensa Math and Logic Puzzle books - great books, I just hate spokes puzzles), I ended up doing the toroidal even though I knew it would take longer than I intended to be puzzling. I've written up my solution more so r.e.s. can get a sense of how I tackled it as he said he was curious and I definitely suggest trying out the LoL things he suggested or other ideas altogether as I'm curious myself to see how else it can be solved.

Step 1:
See the hidden single 9 in R8 at C4. After filling this in you will see that R8C12 is a locked pair of 12, but the 1 in R2C2 gives you the placement of both of these digits as well.

Step 2:
It becomes very important to observe that some of the pieces are thin and don't occupy many columns. If, in two nonets, there are only two shared columns in which a number can go, then it cannot occur in any other nonet in these columns. A lot of variants of this are also true - its sort of a "paired pointing pair with two shapes" - but I used it a couple times in this solution and tend to use it a lot when solving toroidals for some reason. In this step, use this kind of rule to eliminate 1 from R9C3 because C3 and C4 are forced to have their 1's in the other two shapes that cover column 3. This creates a hidden single in R9 of 1 in C4.

Step 3: Notice the 7 in R8C3 creates a pointing pair in C4 in the nonet that stretches across the top and bottom. This then forces 7 in R4C2. This then forces a 7 in R6C1 as a hidden single for row 6. You'll then find that a 7 must go in both R5 at C678 and C8 at R1235 given a constraint of both the row and column so R5C8 is 7.

Step 4: The first interesting step in my mind which leads to a nice cascade. First, let's identify that R7C789 is a locked triplet of 129 as you need this now if you hadn't already marked it down. Consider the possible placements of the number 4 starting in C6 and C7. There are only two nonets that can contain 4 in these columns, so the 4's in these pieces must be in these columns (and not in other columns like C8). This then leave just one place in C8 for a 4 at R9. Once you have 4 at R9C8, you can use the pointing pair in R7C123 to forces 4 in R5C34 to force 4 at exactly R3C7. Then 4 at R8C6. 4 at R2C3 as a hidden single in R2 given all the other shapes now have their 4's. This then puts a 4 at R5C4 and with only 1 place in R1 for a 4, you get the last 4's at R1C2 and R7C1.

Step 5: My favo(u)rite placement - which turns out can also be your first placement but I saw it here. R1C7 is a naked single of 6 with just the givens in the puzzle. Let me explain. The box/row/columns at this point in the puzzle suggest this square is any of 678. However, you have a locked pair of 78 in the two cells R1C6 and R9C7 in the nonet immediately touching R1C7. It is an underused elimination in jigsaws, but any square that both partners of a locked pair in a nonet "sees" cannot be either of the numbers in the locked pair. It's very much the classic rule you use for just rows or columns in standard sudoku but here is a little different because of the jigsaw shape (and, best of all, it uses the toroidal property as well as one of the squares is actually on the other side of the grid). Anyway, eliminating 78 from R1C7 leaves the naked single 6. This placement then gives another naked single 3 in R8C7.

Step 6: Now I just get into some "Nishio-like" things but then I saw this one rather fast so I don't hate it entirely here. R8C89 are the locked pair 56. Notice that putting a 6 in R8C8 easily forces the placement of a 6 in R5C6. In this state of the puzzle, you would have 3 nonets that can only have a 6 in the rows R34 (the specific squares are R34C1, R3C3+R34C3, R34C9). This is impossible. So R8C8 is 5, R8C9 is 6. This gives you a couple more digits. R7C6 = 6, R2C1 = 6 (by pointing pair), R9C3 = 6 (by pointing pair), and R5C2 = 6 (hidden single for row 5).

Step 7: I got the rest by a much uglier Nishio but first let me set the stage. 5 has to be in R7C23 so then 5 has to be in R9C19 so then 5 has to be in R1C34. You can also say that 7 has to be in R13C4 and 6 has to be in R34C4 in that same piece so you have a couple forcing connections between pairs here. The 3 in R3C5 also serves to force the placement of the remaining 3 and 2 in that nonet so it seems a valuable place to try a Nishio even if it is not at all simple. You also will need to see that a 3 cannot be in R7C3 because of the two other nonets in column 3 needing that 3.

Ok, now the ugly Nishio. Let's say that there is a 5 in R1C3. Then there would be a 5 in R7C2 which forces a 3 in R7C4. However, there is another forced 3 in C4 at either R1C4 or R4C4 in the other nonet so now you have to put two 3's in C4 which is not possible. So 5 is not in R1C3. 5 is in R1C4.

This starts a final cascade that finishes the puzzle with 7 in R3C4 gives 6 in R4C4 gives 3 in R1C3 fives 2 in R3C3 gives 6 in R3C8 gives 5 in R2C6 (this follows if you've put the pointing pairs I've mentioned above in the grid as the only place left in R3 as it cannot be R3C9). Then 8 in R2C4 and 2 in R6C4 (pointing pair) and 3 in R7C4 and 3 in R9C2 and 8 in R7C2 (pointing pair) and 5 in R7C3 and 5 in R9C1 and 8 in R3C1 and 2 in R1C8 and 2 in R7C7 and 5 in R3C9 and 9 in R3C2 and 5 in R6C2 and 1 in R3C6 and 3 in R2C9 and 7 in R2C7 and 9 in R2C8 and 7 in R1C6 and 8 in R9C7 and 8 in R1C9 and 7 in R9C9 and 1 in R7C8 and 9 in R7C9 and 1 in R5C7 and 9 in R6C7 and 9 in R4C6 and 9 in R5C3 and 1 in R4C9 and 2 in R5C9 and 2 in R4C1 and 3 in R5C1 and 3 in R4C8 and 3 in R6C6 and 1 in R6C3 and 8 in R4C4 and 8 in R5C6 and 8 in R6C8 and done.

Thomas Snyder
Last edited by motris on Thu Jun 08, 2006 4:42 pm, edited 2 times in total.
motris
 
Posts: 71
Joined: 13 March 2006

Postby motris » Wed Jun 07, 2006 10:26 pm

Forgot to mention my thanks - great puzzle r.e.s. I really enjoyed it and think that just as nonsymmetric jigsaws make you use the shapes you are given in clever new ways, I found myself doing more to tease out placements than with some other toroidals. I also found myself engaging in a weird but fun game of naming the nonets, like "New Hampshire" or "t-shirt with one arm raised" or "cane pulling you off-stage" even if it was not useful in the solving. Anyway, thanks again for posting this puzzle.
motris
 
Posts: 71
Joined: 13 March 2006

Postby r.e.s. » Thu Jun 08, 2006 8:52 pm

motris,

The effort of making this puzzle "by hand" (and learning how highly-constrained these irregular toroidals tend to be!), is rewarded by knowing others enjoy it, and I appreciate very much the detailed description of your solution-path. Below is an alternative path that incorporates some of the moves you mentioned, but uses LoL three times, and one simple digit-to-digit forcing chain (also known as an AIC), instead of Nishio-like moves ...

The three LoL partitions are the ones labelled A,B,C in the picture posted earlier ...

LoL(A) uses c34 as the "inside set"
LoL(B) uses c5678 as the "inside set"
LoL(C) uses r1234567 as the "inside set"

and the path begins with the especially nice move you mentioned:

Code: Select all
   r1c7=6:  naked single (using the naked pair 78-78 in r1c6-r9c7)
   r4c2=7:  LoL(A) (also gives r2c4=58, and 6 locked in r79c2=568)
   r6c1=7:  naked single
   r5c8=7:  7 must be in both r5c678 and r1235c8
   r8c4=9:  row-hidden single
   r8c1=1, r8c2=2:  naked pair 12-12 resolved by r2c2=1
   r9c4=1:  row-hidden single
   r9c8=4:  LoL(B) => must be a 4 in r7c78 or r9c8, but r7c789 contains a naked triple 129
   r3c7=4:  naked single (r9c8=4, and 4 is locked in r5c34; r7c4<>4 due to 4 locked in r7c123)
   r8c6=4:  naked single
   r2c3=4:  row-hidden single
   r1c2=4:  naked single
   r7c1=4:  naked single
   r5c4=4:  naked single
   r8c7=3:  naked single
   r8c9=6:  a digit-to-digit chain of 6's with alternating strong links:
6[r8c9]==6[r8c8]--6[r2c8]==6[r2c1]--6[r9c1]==6[r9c3]--6[r7c3]==6[r7c6]--6[r345c9]==6[r8c9]
=> r8c9=6
(by Lol(B) a 6 is locked in {r345c9, r8c9, r2c4}, but 6 has already been eliminated from r2c4, providing the strong link 6[r345c9]==6[r8c9])
   r7c7=6:  naked single
   r5c2=6:  naked single
   r9c3=6:  naked single (also r9c2<>5 due to 5 locked in r7c23)
   r2c1=6:  naked single
   r9c2=3:  cannot be 8 because 8 is locked in r7c23 (r7c4<>8 due to the 58-58 in r2c4-r7c3)
   r7c4=3:  row-hidden single
   r1c3=3:  col-hidden single
   r2c9=3:  box-hidden single
   r1c8=2, r1c4=5:  naked singles from the 78-78 naked pair in r1c69 due to LoL(C)

   A sequence of successively revealed naked singles solves the remaining cells.

I too found myself seeing images in this puzzle ... maybe because of the strong middle column, I was seeing a totem pole with a one-hand-up person at the top, situated over the posterior of a duck, below which is a snake's head; the 8 below that is another snake's eyes, and an elephant's trunk is nudging it from the left ...:)
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby udosuk » Sat Jun 10, 2006 11:30 am

I think these puzzles are better presented when you colour the regions up...

Image

solution

... And an advantage is you could name the regions with their colours - in these case the following 9:
  • P=pink
  • M=mandarin
  • Y=yellow
  • L=lime
  • B=blue
  • V=violet
  • T=turquoise
  • W=white
  • G=grey
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby Jean-Christophe » Mon Jun 26, 2006 11:09 pm

r.e.s. wrote:SD, here are some LoL cases that can be used in solving the puzzle ...


Hmmm, I must admit I'm lost here. I understand the case D. OK, I'm not familiar with the toroidal flavour but I don't see what kind of inference can be made from the cases A, B and C which cells are spread all around the puzzle. In particular each "half" in these cases include cells which may possibly hold the same number (for instance in case A, R2C4 may duplicate a value in one of R789C3. Also, R4C2 may duplicate a value in one of R568C5). Any chance to have an explanation ?

TIA
Jean-Christophe
 
Posts: 149
Joined: 22 January 2006

Postby r.e.s. » Tue Jun 27, 2006 2:57 am

Jean-Christophe,

It may be surprising at first that LoL relates the contents of cells that can seem "spread all around the puzzle" as you say. But it's really a very simple principle:

Starting with a set of whole units, add some cells and subtract an equal number of other cells, such that the result still consists entirely of whole units. (Recall that a "unit" is any row, column, or box.) That can happen only if the set(*) of digits added (including duplicate values, if any) is equal to the set of digits subtracted -- wherever they occur in the puzzle! -- otherwise the result could not consist of whole units.

(*) In order to use the language of sets, I'm using the word "digit" here in such a way that digits in different cells are different digits, even if they have the same value -- the elements of a set are by definition distinct. Alternatively, the LoL conclusion can be stated in the language of multisets: the multiset of values added must equal the multiset of values subtracted. The essential point is that the two sets of cells -- those added and those subtracted -- must have the same content, including any repeated values.

ASIDE: To have applications of LoL that are easiest to visualise, it's a convenience to make the starting set of units a collection of adjacent rows (or columns), and to think of this set of units as being "converted" to a resulting equal-sized set of jigsaw units by adding & subtracting some cells -- the contents of which must then "balance". (This is just my particular adaptation of LoL.)

So, as you say, in case A "R2C4 may duplicate a value in one of R789C3"; however, not only "may" it duplicate a value, it *must* duplicate a value if that's necessary for equality of the two digit-sets. (In the present puzzle there are initially duplicated candidates in the four cells you mention, but, as you'll see below, they solve to four distinct values.)

Here's a more-detailed explanation of the second step in my solution-path posted above, where I wrote
"r4c2=7: LoL(A) (also gives r2c4=58, and 6 locked in r79c2=568)":

LoL(A) involves converting the starting set of units (c34) into two jigsaw boxes by subtracting four cells ...

RED
r2c4 = 5789
r7c3 = 12345689
r8c3 = 7
r9c3 = 134568

and adding four cells ...

BLUE
r4c2 = 23789
r5c5 = 5
r6c5 = 6
r8c5 = 8

The true digits in RED must exactly match the true digits in BLUE, and vice versa.

ASIDE: Before proceeding, note the potential significance of the repeated RED 7's -- one is a known true digit, while the other is a candidate which may or may not be true (its cell may or may not solve to 7). *If* the other set (BLUE) were to have contained *two* known true 7's (which it doesn't in our case), then there would had to have been two true 7's in RED also, i.e. we could have deduced that r2c4=7. Similar remarks apply to the repeated BLUE 8's.

Now to proceed with the LoL(A) deductions ...

1st: Since r8c3=7 is a known true RED 7, there must be at least one true BLUE 7, which can only be r4c2=7.
2nd: The BLUE set now consists of just the known true digits 5,6,7,8, so this must also be the exact composition of RED. This eliminates in RED every 1,2,3,4,9 candidate, as well as the duplicate 7, so RED is now ...

RED
r2c4 = 58
r7c3 = 568
r8c3 = 7
r9c3 = 568

3rd: For r79c3 we've deduced more than just the candidates 568-568 -- we also know that one of those 6's must be true, thus eliminating all other candidate 6's in that jigsaw box.
--

PS: The general versions of LoL described above can be applied to ordinary (non-toroidal) jigsaw sudoku as well, but in that case there is also a (presumably less-powerful) <simpler version>.

EDIT: Added comment on multisets.
Last edited by r.e.s. on Wed Jun 28, 2006 12:51 pm, edited 1 time in total.
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby Jean-Christophe » Tue Jun 27, 2006 9:19 am

Thanks for you explanation:)

I already understand the basic logic of LOL (I think !)

The inferences which can be made :
1: if a digit must be included in some "half" (some color) then it must also be included in the other "half" (other color).
1a : This holds true for a cell with a definite known value (given or solved).
1b : And also for some digit which must be included as deduced by other means (for instance row-columns/boxes interactions).
2: if a digit is excluded from all the cells in some "half" (some color), then it is also excluded form all the cells in the other "half" (other color), none of the cell in the other half may include this digit.

My concern was mainly about digits which may possibly be repeated within the SAME "half" of the set (same color).

Let's consider a simpler case first (non-toroidal) :
Image
Since the 3 cells in red are within the same row, no digit may be duplicated in these.
We can then deduce that no digit may be duplicated either in the cells in blue, even if R5C1 could theorically hold the same digit as R6C8.

Thus we may infer :
3: If no digit may be repeated in some "half" (some color), then no digit may be duplicated either in the other "half" (other color).

Am I correct at assuming this ?

Then your cases which are much more complex.
For instance, in your case A, within the blue set, R4C2 may possibly hold the same digit as R8C5. Since they are in different rows, columns and boxes.
Also, within the red set, one of the cell in R789C3 may possibly hold the same digit as R2C4.

For instance, what would prevent this case, where all X holds the same value ?
Image
See what I mean ?

Now, I checked all your cases against the solution and indeed none of the cells within the same color contains a duplicate number.
That's where I'm lost.
Can we make any inference about duplicated numbers for such cases ?
Jean-Christophe
 
Posts: 149
Joined: 22 January 2006

Postby r.e.s. » Tue Jun 27, 2006 5:43 pm

Jean-Christophe wrote:My concern was mainly about digits which may possibly be repeated within the SAME "half" of the set (same color).

Please see the second "aside" in my previous posting, which discusses just this possibility. In fact it happens very often, and is perfectly logical when it does.

Here's just one example in the present puzzle, taking the starting set of units to be the two rows r56, and converting it to two jigsaw boxes (yellow outline) by adding the blue cells and subtracting the red cells ...

Image

By LoL, red and blue must contain the same set of digits, here having the multiset of values {1,3,5,6,7,7,8} (with 7 repeated). It's entirely possible that some solving-path could use LoL deductions based on this particular pair of balanced sets.

Jean-Christophe wrote:3: If no digit may be repeated in some "half" (some color), then no digit may be duplicated either in the other "half" (other color).

Am I correct at assuming this ?

It's not an assumption, but a logical consequence of the two "halves" containing the exact same set of digits (they're constructed in a way guaranteed to do so); your points 1, 1a, 1b, and 2, are likewise consequences of this "balancing principle".

Jean-Christophe wrote:what would prevent this case, where all X holds the same value ? [...]

In general, the answer to "what would prevent this?" is that the particulars of whatever puzzle is at hand logically prevent a certain configuration, or not (!) -- the LoL is bound to be consistent with whatever constraints are present in the puzzle.

EDIT: Added reference to multisets.
Last edited by r.e.s. on Thu Apr 05, 2007 9:20 pm, edited 2 times in total.
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby r.e.s. » Wed Jun 28, 2006 3:58 pm

udosuk,

Sorry for having neglected to thank you for the coloring suggestion -- I like also the particular colors you used. I'll just need to be careful not to confuse anyone by coloring the puzzle and then also using colors for certain explanatory purposes (e.g. my red/blue "balanced sets").
r.e.s.
 
Posts: 337
Joined: 31 August 2005

Postby Jean-Christophe » Wed Jun 28, 2006 4:45 pm

Thanks for you explanations about repeated numbers. Indeed I didn't noticed it at first.
Jean-Christophe
 
Posts: 149
Joined: 22 January 2006

Next

Return to Sudoku variants