The New Sudoku Players' Forum

[sb1920alk]

Hello,

Nice forum.

I was introduced to Sudoku around 7 months ago and now enjoy it on a regular basis. I also enjoy Excel recreationally, so I have entered several techniques into Excel using circular references (including hidden and naked pairs). I am gradually learning more techniques and entering them as I learn them. This also helps me to master each technique.

I am struggling with finding examples that require a particular technique to be solved. This would be very useful in mastering one technique at a time. I also have not been able to find a key for all of the abbreviations used in this forum. It looks like they were in an old post that no longer exists. Help on these two points would be appreciated.

Additionally, I saw a post that someone had created an Excel file that also used only circular references, but the link to the file no longer works. Is there any way to still take a look at that file?

If anyone needs anything simple done in Excel, just let me know. For example, I can easily make converters to transfer Sudokus between two different code systems or webpages that offer import/export. You'll just have to copy from the source, paste into the converter, copy from the converter, then paste into the destination.

Regards,

edit: Of course...I forgot to include my original question.... Of the more advanced techniques, are them some that can always be used over another? Are there two or more similar techniques that can be easily mastered at the same time?

Thanks,

[RW]

Hello sb1920alk, welcome to the forums!

There's lots of threads with examples of particular techniques, including:
The Zoo
The Benchmark Sudoku List
The Effortless Extremes

A good list of the terminology and abbreviations can be found in Sudopedia. The best list of different techniques can be found here.

Be aware that the forum has moved to a new server two days ago and as a result no old links to threads work anymore. To use old links: rightclick the link and choose "copy shortcut" -> paste into your address bar -> replace the word "forums" with "boards" -> press enter.

Among advanced techniques, there's many that cover the same ground and can be used over each other. Templates and nishio covers all fishes and other 1-digit techniques, forcing chains can be used over any other (non-uniqueness based) technique. People still tend to prefer the pattern based techniques over chains and templates.

RW

[sb1920alk]

Thanks for the info and the links. That's just great. Leave it to me to find this forum right when it changed servers :O)

I haven't seen templates before. It looks like this isn't something that would be usable without a computer. At that point, why not collect a library of all possible solutions (trimmed down for reflections, row exchanges, arbitrary candidate symbols etc.) ...a quick search...it looks like there are 5,472,730,538 different solutions, and only 46,656 different templates...perhaps a slightly faster computer first.

Regards,

[RW]

Yes, templates is not really a technique for humans... though I actually did use it earlier today and noticed some (useless) eliminations in this puzzle richardm posted in the help forum:

Code: Select all

 *-----------*
 |...|.61|.3.|
 |693|274|...|
 |1..|.3.|26.|
 |---+---+---|
 |...|..2|..1|
 |.5.|1.9|.7.|
 |4..|6..|...|
 |---+---+---|
 |962|.1.|..3|
 |...|42.|95.|
 |574|.9.|...|
 *-----------*

Looking at the sevens I saw that there's only two different templates:
if r7c7=7 => r8c6=7 => r4c4=7 => r6c3=7 => r1c1=7 => r3c9=7
if r8c9=7 => r1c7=7 => r3c3=7 => r4c1=7 => r6c6=7 => r7c4=7

=> r1c3<>7, r1c9<>7, r4c3<>7, r7c6<>7

In this case the same eliminations could be made by a swordfish, but when solving without pencilmarks I'm used to thinking in chains instead of patterns.

At that point, why not collect a library of all possible solutions (trimmed down for reflections, row exchanges, arbitrary candidate symbols etc.) ...a quick search...it looks like there are 5,472,730,538 different solutions

I'm afraid you'd have to work with all 6670903752021072936960 possible solutions. Otherwise you'd have to canonicalize the puzzle, which can't be done without solving it first...

RW

[sb1920alk]

I'm afraid you'd have to work with all 6670903752021072936960 possible solutions. Otherwise you'd have to canonicalize the puzzle, which can't be done without solving it first...

RW

If we're re-labeling, can't we always choose Row One to be 1,2,3,4,5,6,7,8,9? Assuming that is true, if there were no clues in Row One, (Worst Case) I suppose we would have to consider 9! (362,880) different labelings to do this it prior to solving, but 362,880 x 5,472,730,538 = 1,985,944,457,629,440, which is still considerably less than 6,670,903,752,021,072,936,960. With each clue or big number in Row One, I would guess it would get closer to 5,472,730,538.

That makes me wonder if while using templates it might be more efficient to consider the values that require the fewest number of templates, and instead of comparing against a library of templates, have the computer calculate only the required templates on the fly based on the positions of the subject value.

You've pointed me to a ton of information that's new to me. I really appreciate it.

Regards,

[RW]

If we're re-labeling, can't we always choose Row One to be 1,2,3,4,5,6,7,8,9? Assuming that is true, if there were no clues in Row One, (Worst Case) I suppose we would have to consider 9! (362,880) different labelings to do this it prior to solving, but 362,880 x 5,472,730,538 = 1,985,944,457,629,440, which is still considerably less than 6,670,903,752,021,072,936,960. With each clue or big number in Row One, I would guess it would get closer to 5,472,730,538.

I'm afraid this doesn't work. Even if you relabel the digits, there's still 6^8*2 = 3,359,232 possible permutations by swapping rows, columns and chutes and rotating the grid. So if you have succesfully solved the first row and can relabel the grid to give 123... in row 1, you only need to compare with about 1.8*10^16 grids.

That makes me wonder if while using templates it might be more efficient to consider the values that require the fewest number of templates, and instead of comparing against a library of templates, have the computer calculate only the required templates on the fly based on the positions of the subject value.

I don't know exactly how the programmers around have implemented templates, but I doubt that anyone has a program that compares with all 46,656 templates. I guess most programs look for the possible templates in the current situation, which usually is less than 20 for any digit.

RW

[sb1920alk]

I'm afraid this doesn't work. Even if you relabel the digits, there's still 6^8*2 = 3,359,232 possible permutations by swapping rows, columns and chutes and rotating the grid. So if you have succesfully solved the first row and can relabel the grid to give 123... in row 1, you only need to compare with about 1.8*10^16 grids.

RW

That's true. The 5,472,730,538 figure is that small because it includes swapping rows, columns and chutes, rotations as you said, and relabling, and I only considered the relabling. Computer speed would need quite a boost!

Is there a recommend or logical order that makes the most sense to learn new techniques? I'm up to hidden and naked pairs by hand and in Excel, and naked triples, x-wing, and singles chains by hand and working on putting those in Excel.

Regards,

[ravel]

Otherwise you'd have to canonicalize the puzzle, which can't be done without solving it first...

To be more precise, there are other normalizations that do not use the solution (also multi solution puzzles can be normalized).

[gsf]

Otherwise you'd have to canonicalize the puzzle, which can't be done without solving it first...

To be more precise, there are other normalizations that do not use the solution (also multi solution puzzles can be normalized).

yes, but in this case the poster suggested normalizing a puzzle in order to do a lookup
in a normalized catalog of (solution) grids

the popular normalizations we have are row order minlex
one based on the solution grid, the other based on the puzzle (what I called subgrid to differentiate)

add a clue to a puzzle and it could completely change its subgrid row order minlex representation
in particular, a valid puzzle (a puzzle with one solution) row-order minlex has no (known) direct relationship to
its solution grid row order minlex

[daj95376]

That makes me wonder if while using templates it might be more efficient to consider the values that require the fewest number of templates, and instead of comparing against a library of templates, have the computer calculate only the required templates on the fly based on the positions of the subject value.

I don't know exactly how the programmers around have implemented templates, but I doubt that anyone has a program that compares with all 46,656 templates. I guess most programs look for the possible templates in the current situation, which usually is less than 20 for any digit.

I don't know how others implement POM/Rookeries/Templates, but I ended up using a backtracking technique to generate a Templates table that's loaded at compilation. For me, searching a table of 46,656 entries nine times seems faster than generating Templates at runtime nine times -- but I could easily be wrong.

Does anyone have an efficient method of generating Templates at runtime?

[sb1920alk]

For me, searching a table of 46,656 entries nine times seems faster than generating Templates at runtime nine times -- but I could easily be wrong.

Do you know if there's a place to download all 46,656 templates, or do most people just produce them themselves?

[daj95376]

For me, searching a table of 46,656 entries nine times seems faster than generating Templates at runtime nine times -- but I could easily be wrong.

Do you know if there's a place to download all 46,656 templates, or do most people just produce them themselves?

I never found a table of Templates. I only found a modest amount of information on generating them. After producing them for myself, I realize that my choice of data structures plays a big part in creating these tables.

Thanks to a suggestion by Ruud in the Programmers Forum, I use a 27-bit bitmap to store a band of information. It takes me three, 32-bit long int's in C to store a single table entry.

I'm more than willing to share my C declarations and data table. I can put a ZIP file on *zshare*. Does anyone want this information in this format?

[Myth Jellies]

Here is a way to convert from candidate-space to POM-pattern or rookery-space.

http://forum.enjoysudoku.com/viewtopic.php?t=4398

[daj95376]

Excellent presentation Myth Jellies. The first time I read it, I only understood about 1% because of my lack of experience. Now, I understand 51% of it.

One quick point. After Naked and Hidden Singles, almost all techniques are based on eliminatons in cells. That's the same approach you take with the following technique.

POM Technique 1 - Pattern Exclusion Principle
If a pattern occupies cells containing all of the patterns for any other digit, then that pattern must be invalid. Obviously, if that pattern were true, then there would be no valid placements for that other digit on the grid. You can often find these reductions by inspection.

However, I contend that assignments exist using POM/Rookeries/Templates. (ronk frowns on my using them!)

Corollary: POM Technique 1C - Pattern Assignment Principle
If all of the patterns for a digit contain the same cell, then that cell can be assigned that digit and removed from the patterns of other digits. (This would be the case for all Naked and Hidden Singles already revealed, but it can also be true for cells that currently contain other digits.)

Here is an example from a recent post.

Code: Select all

 *-----------------------*
 | . 6 . | . 4 . | 2 . . |
 | . . . | . . 7 | . . . |
 | 9 . 8 | 5 . . | . 1 . |
 |-------+-------+-------|
 | . . 7 | 1 . . | . . . |
 | . . 5 | . . . | 8 . . |
 | . . . | . . 6 | 3 . . |
 |-------+-------+-------|
 | . 8 . | . . 5 | 9 . 3 |
 | . . . | 9 . . | . . . |
 | . . 1 | . 3 . | . 7 . |
 *-----------------------*


After Singles, a Locked Candidate 1, and an X-Wing, the puzzle can be solved with a Sashimi X-Wing in <4>.

However, there are eliminations in <2> as well. In fact, they all result from [r9c9]=2 -- which is present in all POM patterns for this digit. (A classic case of three strong links on a cell and, if the digit is assumed false in that cell, then the forced cells create an invalid pattern later for that digit. In this case, [b7] becomes void of <2>.)

Code: Select all

 *--------------------------------------------------------------*
 |  7     6     3     |  8     4     1     |  2     5     9     |
 |  1     5     24    |  26    9     7     |  46    3     8     |
 |  9     24    8     |  5     26    3     |  7     1     46    |
 |--------------------+--------------------+--------------------|
 |  246   3     7     |  1     8     249   |  5     2469  246   |
 |  246   24    5     |  3     7     249   |  8     2469  1     |
 |  8     1     9     |  24    5     6     |  3     24    7     |
 |--------------------+--------------------+--------------------|
 |  24    8     246   |  7     1     5     |  9     246   3     |
 |  3     7     246   |  9     26    24    |  1     8     5     |
 |  5     9     1     |  246   3     8     |  46    7     24    |
 *--------------------------------------------------------------*

 r69     -  2     Skyscraper
 r28     -  2     Sashimi X-Wing

 r69     -  4     Sashimi X-Wing


[ronk]

However, I contend that assignments exist using POM/Rookeries/Templates. (ronk frowns on my using them!)

When we were looking for franken and mutant fish explanations for Nishio eliminations, I'm sure it looked that way ... but I'm not anti-placements, in general.