New Multi-Spoke Pattern

Advanced methods and approaches for solving Sudoku puzzles

Postby ronk » Fri Jan 26, 2007 11:11 pm

Steve K wrote:Of course, there is also the puzzle I created above. (Does that disqualify it from the real world?)

Of course, but I was hoping someone would start with real-world examples, not real-world puzzles.:(
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby ravel » Fri Jan 26, 2007 11:24 pm

Steve K wrote:In this puzzle, after performing a locked candidate elimination on the 6's in row 1, one can immediately apply a triple spoke pattern starting from cell r9c8 and using strong cells r1c7, r1c9.
ronk wrote: Of course, but I was hoping someone would start with real-world examples, not real-world puzzles.:(
I agree with Ron. I did not read the posts carefully, but i think, examples would help much to understand quicker. So please be so kind to at least post a candidate grid with the cells marked, which are involved in the pattern you use.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Myth Jellies » Sat Jan 27, 2007 6:39 am

Steve R wrote:MJ, I hope you won’t mind a couple of suggestions.

Does defining the rim as a house represent the clearest approach?...


No, you are right, (and Steve K has basically said the following as well) the real underlying rule is as follows...

In an N-Spoke Pattern, all N spokes must weakly link to the same A^(N-1)LS group.

An A^mLS group is defined as a group of M cells that are in the same house and contain M+m different digit values. Note that an A^1LS is just an ALS (almost locked set). An A^2LS is an AALS, etc.


A One-Spoke pattern would involve a weak link into an A^0LS which is a weak link into an already locked set. Since you know the digit in the locked set must be true, the other end of the weak link is false. Not too interesting, but there for mathematical completeness.

Both explanations are valid; however, this one is simpler and more complete. When figuring out a new pattern, it is not bad to have multiple ways of looking at it though. This new way of looking at it allows you to count the following as a triple-spoke...
Code: Select all
Triple-Spoke 
 +----------------+-------------------+----------------+
 | .    1789 .    | .       2789 3789 | 789  .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 +----------------+-------------------+----------------+
 | .    1A*  .    | 1a2b3c* .    .    | .    .    .    |
 | .    .    .    | .       2B*  .    | .    .    .    |
 | .    .    .    | .       .    3C*  | .    .    .    |
 +----------------+-------------------+----------------+
 | .    .    .    | .       .    .    | .    .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 +----------------+-------------------+----------------+

...as well as...
Code: Select all
Triple-Spoke
 +----------------+--------------------+----------------+
 | .    .    .    | .       12389 2389 | .    .    .    |
 | .    .    .    | 2B*     12389 .    | .    .    .    |
 | .    .    .    | 3C*     .     .    | .    .    .    |
 +----------------+--------------------+----------------+
 | .    .    .    | 1a2b3c* .     .    | .    .    .    |
 | .    .    .    | .       1A*   .    | .    .    .    |
 | .    .    .    | .       .     .    | .    .    .    |
 +----------------+--------------------+----------------+
 | .    .    .    | .       .     .    | .    .    .    |
 | .    .    .    | .       .     .    | .    .    .    |
 | .    .    .    | .       .     .    | .    .    .    |
 +----------------+--------------------+----------------+


Eliminating the concept of strong spokes in the pattern is an added benefit as well.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Myth Jellies » Sat Jan 27, 2007 7:41 am

ronk wrote:The Multi-Spoking pattern

Very interesting, but I note that most of the diagrams are for continuous loops.

I've never seen statistics on this, but there are unquestionably many more deductions made with discontinuous loops rather than continuous ones. For the ALS xz-rule, for example, there are many more singly-weakly-linked sets than doubly-linked ones (sometimes called ALS xz mutual exclusion rule).

That observation coupled with the lack of actual examples, causes me to be skeptical of the usefulness of this technique.


The problem with multi-threaded networks is that you have so many options that it is almost impossible to know where to start or decide on which paths to investigate. This is especially true if you are solving without the aid of a computer. The Spoke Pattern has a nice potential start point with its hub. The good thing is that the hub is an easy to spot marker. The bad thing is that the hub is essentially a weak link start point and so you may have to make a closed or continuous loop/net in order to make a non-assumptive deduction.

I think there is a lot of bang for the buck here. The pattern potentially eliminates a lot of candidates. A double spoke can be used to help find ALS deductions that might otherwise be missed. A triple spoke or almost (finned) triple spoke & beyond might find deductions that we currently have no other human doable non-assumptive method for finding. Even if a discontinuous network is more prevalent, that's no reason to abandon continuous networks; especially if you don't have a decent method for isolating/finding those discontinuous networks.

I'm hoping that the Spoke Pattern gives us a foothold in the realm of network deductions from which we can generate more methods. There is another pattern with similar features called a fish which is also essentially a closed network loop. We seem to have found a lot of uses for it:) I think many of the fish modification concepts may be applicable to this pattern.

Of course time will tell if any of this pans out.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby Steve K » Sun Jan 28, 2007 2:04 am

Myth Jellies wrote:The problem with multi-threaded networks is that you have so many options that it is almost impossible to know where to start or decide on which paths to investigate. This is especially true if you are solving without the aid of a computer. The Spoke Pattern has a nice potential start point with its hub. The good thing is that the hub is an easy to spot marker. The bad thing is that the hub is essentially a weak link start point and so you may have to make a closed or continuous loop/net in order to make a non-assumptive deduction.


In my experience, such a hub - a cell with multiple strong links emanating from it - is exactly the best place to start looking for forbidding chains (AIC). Often, there are non-closed loops that use such a cell. Moreover, in a puzzle that is "stuck" early, it is more likely that a hub such as this will be fruitful rather than a strong cell. Also, the types of chains that emanate from such a cell are not limited to ever needing to use strength in cells, and in fact often use only strength in location.

The manner that I use typically to locate forbidding chains in a very tough puzzle that is stuck "early" - less than 35 cells, (+-) solved, is precisely to focus on hub-like cells, which are really just the endpoints of multiple strong links.

Also, of some interest may be the use of double hubs. Double hubs can be found often. Some interesting patterns, like most Sue de Coq's, have an alternate representation as a multi-hub multi-spoke pattern.

Code: Select all
 +----------------+
 |12345   .    .  | 
 |12345  12    .  |
 |12345   .    .  |
 +----------------+
 | *      .    .  |
 | 34     .    .  |
 |~126    .    .  |
 +----------------+
 |~126    .    .  |
 |~126    .    .  |
 | *      .    .  |
 +----------------+




* is a wildcard, ~ means not.
Above we have a typical Sue de Coq, which needs strength in 5 cells to complete.
Alternatively, there is a double hub: An Almost Hidden Pair 16 or 26 at r49c1 which acts as a double hub, with spokes, strong 1's and 2's extending into box 1. Viewed this way, we have strong 6's,1's,2's in column 1 crossed with the ALS 12 at r2c2, yeilding some of the same eliminations as the Sue de Coq (the same eliminations in box1, but perhaps more at r49c1, but perhaps less at r678c1) - but all at less native depth (4 versus 5).

I would write this alternative chain as follows:
{Hidden pair 16 @ r49c1} == (r123c1=1} -- (r2c2=1) == (r2c2=2) -- {r123c1=2} == {Hidden pair 26 @r49c1}


A rather timely coincidence: Today's tough puzzle at http://www.sudoku.com.au/1V28-1-2007-sudoku.aspx is easily unlocked using a strong hub in two seperate, but not closed, chains. Clark's proof of this puzzle in the comments on that page demonstrate precisely how this is done.

BTW, I have no control over the puzzles used on that site, although I do host a sudoku blog through that site. Chain finding strategies are discussed in that blog. Since the blog is still in its infancy, the advice is incomplete (although I suspect it will always be "incomplete")
Steve K
 
Posts: 98
Joined: 18 January 2007

Postby ravel » Sun Jan 28, 2007 6:23 pm

Steve K,

once again: would you be so kind to post the grid with the cells marked, that are involved?

Here is your sample:
Code: Select all
 *--------------------------------------------------------------------*
 | 8      7      12459  | 146    1346   169    | 2345   26     2356   |
 | 134    124    6      | 1478   5      17     | 23478  278    9      |
 | 345    45     459    | 2      34678  679    | 1      678    3568   |
 |----------------------+----------------------+----------------------|
 | 16     3     @18     | 5     @169    2      |#89     4      7      |
 | 14567  1456   1457   | 3     #14679  8      | 29     1269   126    |
 | 2      9     #1478   |@1467  @1467  @167    | 38     5      1368   |
 |----------------------+----------------------+----------------------|
 | 1567   12568  3      | 16789  1678   4      | 25789  12789  1258   |
 | 9      1458   1457   | 178    2      3      | 6      178    158    |
 | 167    1268   127    | 16789  1678   5      | 2789   3      4      |
 *--------------------------------------------------------------------*
With some practice for finding contradiction chains those are not very hard to spot:
r6c3=47 => r4c3=8 => r4c7=9 => r4c5<>9 => r5c5=9 => r6c456=47
=> r6c3<>47
You did not mention this one (of course it also follows from the eliminations):
r5c5=47 => r4c5=9 => r3c7=8 => r4c3<>8 => r6c3=8 => r6c456=47
=> r5c5<>47

You can alternatively notate them as AIC, nice loop or whatever (e.g. either r6c3=8 or r5c5=9 => r6c456=47).
So what is the benfit of hubs and sparks here ?
Steve K wrote:BTW, the parameters that I have suggested for locating forbidding chains should flag cell e5 as a likely focal point for some fruitful chains.
Can you explain that please ? Why is it better than e.g. r1c3 ?

And here is the grid from your other sample:
Code: Select all
*--------------------------------------------------------------------------------------*
 | 467      8        23467    | 47       9        5        | 124      1234     1234     |
 | 9        134      5        | 48       13       123      | 2468     2346     7        |
 | 47       1347     2347     | 478      6        123      | 24589    2345     23459    |
 |----------------------------+----------------------------+----------------------------|
 | 8        2        4679     | 1        3457     349      | 4567     4567     456      |
 | 3        457      47       | 6        4578     48       | 12       9        12       |
 | 4567     4579     1        | 2        457      49       | 3        4567     8        |
 |----------------------------+----------------------------+----------------------------|
 | 1        4579     4789     | 3        2        468      | 45679    4567     4569     |
 | 2        6        349      | 59       14       7        | 1459     8        13459    |
 | 457      34579    34789    | 59       148      1468     | 1245679  1234567  1234569  |
 *--------------------------------------------------------------------------------------*
Can you now show us the triple spoke pattern and how to use it, please ?
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Steve K » Sun Jan 28, 2007 8:25 pm

ravel wrote:With some practice for finding contradiction chains those are not very hard to spot:
r6c3=47 => r4c3=8 => r4c7=9 => r4c5<>9 => r5c5=9 => r6c456=47
=> r6c3<>47 ....... So what is the benfit of hubs and sparks here ? ......
Why is it better than e.g. r1c3 ?

The cell r5c5 is a likely place to not only find a chain passing through, but also that the chain passing through that location will serve significantly towards unlocking the puzzle. That is because three bivalue links strong by location emanate from that cell. It is thus a plausible hub. Not an exact science by any means. It is higher valued than many others. The fact that r6c3 is also a highly valued cell, and that it has a similar 3 spoke configuration coming out of it, and the fact that the candidates 47 are part of both of these potential hubs with r5c5 flag both of those cells. Again, I don't know that one can ever formulate an exact science to which places are always going to be the best places to look. In any event, I have used this method to find chains frequently, and have met with great success. Of couse, since the number of puzzles I have solved is small relative to total possible puzzles, it is likely that I have a great deal more to learn in formulating a good theory for finding chains.

Please forbear my ignorance at posting here. I have a great deal of difficulty posting a readable puzzle grid. I could use some tips on how to do that more efficiently. To get this partial grid, I copied and pasted what ravel provided. I truncated columns 1 through 6 for clarity.

Code: Select all
    c7       c8       c9

 | 124      1234     1234     |
 | 2468     2346     7        |
 | 24589    2345     23459    |
 +----------------------------|
 | 4567     4567     456      |
 | 12       9        12       |
 | 3        4567     8        |
 +----------------------------|
 | 45679    4567     4569     |
 | 1459     8        13459    |
 | 1245679  1234567  1234569  |
 


Here, r9c8 is the hub, as for each of candidates 1,2,3 we have a strong spoke to r123c8. This triple spoke interacts with the strong cells:
r1c7=124 and r1c9=1234.

Clearly, r9c8 must be at least one of 1,2,3 - for if not then r1c7 = r1c9 = 4.

The nice loop made by the triple hub, and
the Almost Almost Locked set 1234 at r1c79 allows one to forbid:

4567 from r9c8.
2 from r23c7, r3c9.
3 from r3c9.
4 from everywhere it exists in row 1 and box 3 outside of r1c79.
Steve K
 
Posts: 98
Joined: 18 January 2007

Postby Steve K » Sun Jan 28, 2007 8:33 pm

ravel wrote:Steve K,

once again: would you be so kind to post the grid with the cells marked, that are involved?

But, like an idiot, I did not. Sorry:

Code: Select all
   c7       c8       c9

 | 124#     1234*    1234#    |
 | 2468     2346*    7        |
 | 24589    2345*    23459    |
 +----------------------------|
 | 4567     4567     456      |
 | 12       9        12       |
 | 3        4567     8        |
 +----------------------------|
 | 45679    4567     4569     |
 | 1459     8        13459    |
 | 1245679  1234567@ 1234569  |


@ is the hub, using candidates 123.
#'s are the Almost Almost Locked Set.
*'s are the spokes, using candidates 123.

Eventually, I will learn to post better.
Steve K
 
Posts: 98
Joined: 18 January 2007

Postby ravel » Sun Jan 28, 2007 11:30 pm

Thanks for the answer,
Steve K wrote:The cell r5c5 is a likely place to not only find a chain passing through, but also that the chain passing through that location will serve significantly towards unlocking the puzzle. That is because three bivalue links strong by location emanate from that cell.
Sorry, i dont know, what you mean. I only can see the bilocation link for 9. Maybe you mean grouped links, like for 4 and 7 ? But r1c3 has more (and a chain to eliminate 4).
I have a great deal of difficulty posting a readable puzzle grid. I could use some tips on how to do that more efficiently.
I do it with Simple Sudoku, just copy and paste.
Clearly, r9c8 must be at least one of 1,2,3 - for if not then r1c7 = r1c9 = 4
I cant see that. Why not r9c8=4569, r1c8=1, r1c9=4, r1c7=2 and r1c3=3?
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Myth Jellies » Mon Jan 29, 2007 7:20 am

ravel wrote:Thanks for the answer,
Steve K wrote:Clearly, r9c8 must be at least one of 1,2,3 - for if not then r1c7 = r1c9 = 4
I cant see that. Why not r9c8=4569, r1c8=1, r1c9=4, r1c7=2 and r1c3=3?


Why? Because the pattern says so:) . Seriously, if r9c8 = 4567 then you have a naked quad eliminating those numbers from r123c8, leaving you with r123c8 = 1&2&3. Therefore, r1c79 are both left with only a 4.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ravel » Mon Jan 29, 2007 9:46 am

Thanks, i did not know, that r467c8 belong to the pattern. So finally i can see an almost almost locked set.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Steve K » Mon Jan 29, 2007 10:36 am

ravel wrote:Thanks for the answer,
Steve K wrote:Clearly, r9c8 must be at least one of 1,2,3 - for if not then r1c7 = r1c9 = 4
I cant see that. Why not r9c8=4569, r1c8=1, r1c9=4, r1c7=2 and r1c3=3?


Although Myth answered using naked sets to explain it, I see it by strength in location (almost hidden sets).
If r9c8<>{1,2,3}, then {1,2,3} exists at {r123,c8} (a hidden triple in the column) => r1c79<>{1,2,3} => (r1c7 = r1c9 = 4).


There are always multiple ways to solve a puzzle. There are always multiple ways to prove the same elimination. There are always hidden sets when there are naked sets. There are always Almost Hidden Sets when there are Almost Naked sets. If there exists a fish of size n with candidate r with respect to rows, there must also exist a fish of size m with candidate r with respect to columns. And so on....


Preferences, as to how one sees the eliminations, are fairly arbitrary. It is not really possible to evaluate those arbitrary choices without making, well, some arbitrary choices.

Because the possibility matrix makes strength in cells, and thus Naked Sets, and Almost Naked sets, more visual, they tend to be more highly valued (=easier to spot) for many people. Since I study a sudoku first without using the possibility matrix, for me the exact opposite is true. So, even with the possibilities entered, I will see strength in location faster, or as fast, as strength in cells.

For example, for me a hidden pair is easier to find than a naked pair, because I look before the possibilities are entered. (Or, alternatively, look past the possibility matrix.) No matter which one is preferred by the solver, what is not arbitrary is:
The amount of native puzzle information to prove the existence of a naked pair is exactly the same as the amount of native puzzle information required to prove the existence of a hidden pair. Equivalently, the number of eliminations one must make to prove one is exactly the same as the number of eliminations one must make to prove the other.

Therefor, it is truly impossible to answer "why not this" instead of "that". It will be a very, very rare puzzle that allows but a single method of attack.

Finally, I may be a little bit slow on the uptake with the terminology used here. To me, grouped links such as one strong candidate in one large container and a grouping in a single other large container are a type of bivalue strength, and often get a flag on a printed out possibility matrix.
Steve K
 
Posts: 98
Joined: 18 January 2007

Re: New Multi-Spoke Pattern

Postby ronk » Tue Jan 30, 2007 12:33 am

Myth Jellies wrote:
Code: Select all
Triple Spoke
 +----------------+-------------------+----------------+
 | .    124  .    | 1A*     .    134  | .    .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 +----------------+-------------------+----------------+
 | .    2B*  .    | 1a2b3c* .    .    | .    .    .    |
 | .    .    .    | .       .    3C*  | .    .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 +----------------+-------------------+----------------+
 | .    .    .    | .       .    .    | .    .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 +----------------+-------------------+----------------+
 Legend:  1a & 1A are conjugate colors for digit 1
          2b & 2B are conjugate colors
          3c & 3C are conjugate colors
          * represents any number of extra digits
 r4c4 is the hub cell
 r1c246 are the rim cells

I added code to my multi-digit coloring algorithm to detect the above pattern (and all its permutations) and then searched Ruud's file of 50,000 puzzles (sorry, no link).

It found no instances of the pattern. But without a single real-world example with which to test, it's impossible to know if my code is bug-free, or at least almost bug-free.

The code allowed neither for grouped candidates nor for the "2B" cell to be in the same box as the hub.

[edit: I now think my implementation of the above exemplar was too narrow. For example, it didn't cover either of the following:]
Code: Select all
Triple Spoke ("variant" 2)
 +----------------+-------------------+----------------+
 | .    124  .    | 1A*     .    .    | 134  .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 +----------------+-------------------+----------------+
 | .    2B*  .    | 1a2b3c* .    .    | 3C*  .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 +----------------+-------------------+----------------+
 | .    .    .    | .       .    .    | .    .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 +----------------+-------------------+----------------+

Triple Spoke ("variant" 3)
 +----------------+-------------------+----------------+
 | .    .    .    | 1A*     124  134  | .    .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 +----------------+-------------------+----------------+
 | .    .    .    | 1a2b3c* .    .    | .    .    .    |
 | .    .    .    | .       .    3C*  | .    .    .    |
 | .    .    .    | .       2B*  .    | .    .    .    |
 +----------------+-------------------+----------------+
 | .    .    .    | .       .    .    | .    .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 +----------------+-------------------+----------------+
Last edited by ronk on Tue Jan 30, 2007 9:40 am, edited 1 time in total.
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby Myth Jellies » Tue Jan 30, 2007 5:48 am

I just updated the initial post to include some of these collaborative findings.

Ronk's initial finding may seem a little disappointing, but when solving using the Molecular Method/multidigit multicoloring I have quite often come across situations where I have had a triangle of three weakly linked colors in my "molecule". I didn't know what I could do with it then. Now I know they form a potential hub, so I will keep my eyes open.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby ronk » Tue Jan 30, 2007 6:14 am

Myth Jellies wrote:Ronk's initial finding may seem a little disappointing, but when solving using the Molecular Method/multidigit multicoloring I have quite often come across situations where I have had a triangle of three weakly linked colors in my "molecule". I didn't know what I could do with it then. Now I know they form a potential hub, so I will keep my eyes open.

Would those likely have been examples of the following pattern?
Code: Select all
Triple-Spoke (no strong spokes)
 +----------------+-------------------+----------------+
 | .    189  .    | .       289  389  | .    .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 +----------------+-------------------+----------------+
 | .    1A*  .    | 1a2b3c* .    .    | .    .    .    |
 | .    .    .    | .       2B*  .    | .    .    .    |
 | .    .    .    | .       .    3C*  | .    .    .    |
 +----------------+-------------------+----------------+
 | .    .    .    | .       .    .    | .    .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 | .    .    .    | .       .    .    | .    .    .    |
 +----------------+-------------------+----------------+
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

PreviousNext

Return to Advanced solving techniques