The New Sudoku Players' Forum

[dobrichev]

Is there a classification of solving techniques based on the number of elements involved?

Element is a house or a digit, i.e. one of the 9 rows, 9 columns, 9 boxes, or 9 digits.

[ronk]

Is there a classification of solving techniques based on the number of elements involved?

Element is a house or a digit, i.e. one of the 9 rows, 9 columns, 9 boxes, or 9 digits.

I don't think there is such a classification ... and with many of the techniques having a variable number of elements, how would that work?

Some of us use the number of rows, columns, boxes and cells as an arbiter for the relative difficulty of moves. Adding the number of digit layers to this seems like a good idea.

[dobrichev]

Hi Ronk,

Thank you for the answer.

IMO a cell is always examined in the context of some intersection of houses. Just a speculation.

For the techniques of variable number of elements, there should be some lower limit. Say, for UR there are 2 rows, 2 columns, 2 boxes, and 3+ digits.

I asked, because I am trying to code a template-based solver. Take all possible 9-cell templates for each digit, then reduce them to one per digit. I found there are some puzzles rated by SE up to 6.9 which are easily solvable by intersecting the templates. It is far not human technique, but it could help in puzzle analysis.

Below are details of the method used, along with an example.

Hidden Text: Show

Take a puzzle. Example from Patterns Game.

Code: Select all

... ..1 ..2
..3 .4. .5.
.6. 7. .8..

..6 ... .7.
.4. .2. ..3
1.. ..4 9..

..8 ..9 5..
.7. 8.. .6.
6.. .5. ... ER=6.6/6.6/6.6 - joel64, patterns game 146


Step A. Prepare 9 81-bit masks, one per digit. Example for digit 7.

Code: Select all

.*. *** .*2
.*3 *** .*.
*** 7** ***

*** *** *7*
.*. *2. ***
1*. *.4 ***

*** *.9 5*.
*7* *** ***
*** *5. .*. Digit 7 step A1: set all visible cells


.*. *** .**
.** *** .*.
*** 7** ***

*** *** *7*
.*. **. ***
**. *.* ***

*** *.* **.
*7* *** ***
*** **. .*. Digit 7 step A2: set all givens <> 7


.*. *** .**
.** *** .*.
*** .** ***

*** *** *.*
.*. **. ***
**. *.* ***

*** *.* **.
*.* *** ***
*** **. .*. Digit 7 mask: only 6 from the 46656 possible templates are disjoint to this mask


Step B. Apply the 9 masks over all 46656 templates. Store all disjoint to the mask templates as candidates for the respective digit.

Code: Select all

Template distribution 36 28 54 28 14  4  6 14 42    product=301112598528 sum=226


Step C. Perform some basic eliminations (none of them is required for this example puzzle).

Step D. Remove all templates that have no at least one disjoint template for each of the other digits.
Repeat until solution found or no more eliminations exist.

Code: Select all

Template distribution  1  1  1  1  1  1  1  1  1    product=1            sum=9 (example puzzle solved)


Steps E-Y. Still unknown.

Step Z. Last resort: Reorder digits (relabel) in accending order by number of templates, perform 9 nested loops, find all disjoint templates.

No-solution condition: A digit with 0 template candidates.
Single-solution condition: 9 disjoint templates remain, one for each digit.
Multiple-solution condition: More than one possibility to form 9 disjoint templates, one for each digit.

The basic methods include:
- Solve a cell if only templates for one of the digits hit it. Remove the templates for the same digit that not hit the solved cell.
- Solve a digit if there is a cell covered by only one template. Remove rest of the templates for this digit. Remove the templates for other digits that hit the solved digit.
- Other methods, suggested (not yet) by experts.

Step B rate is ~500 puzzles/sec.
Generating large amount of solutions for multiple-solution puzzle is expected to be fairly fast.

I am looking for analogs of existing methods, which could be easily coded using digit templates. Hope the methods with low number of digits and high number of houses would fit better, but who knows...

Cheers,
MD

[JasonLion]

Have you read this topic, over at the programmers forum?

[dobrichev]

Hi JasonLion,

Thank you for the reference. I read this topic years ago, and reread it now carefully.

The most valuable is Ruud's initial post, which doesn't cover the number of template candidates for a non-given digit, and opens some questions, which are still unanswered.

I have written logic in the program for detecting naked singles, hidden singles, naked subsets, hidden subsets, X-wings and coloring, but the template technique removes the same candidates (and more!) without knowing why it did that.

His approach is based on POM (which I listed as a basic techniques), and brute force intersection. Merging the patterns, suggested later, is dangerous for a puzzle with huge number of solutions.

There must be more intermediate operations making something reasonable, similar to Step D in my previous post.

It is known this algorithm is slow in comparison to other solvers, but in comparison to the discussed rating software the performance is good. Recently the focus is moved to the hardest puzzles, and maybe this 6-year old approach can suggest some shortcuts in rating algorithms?

I am sure nobody there believe that the modern solving methods are "logical", so this isn't the problem.

Sorry that there is no written classification of the methods by the elements. It could be a natural base for further comparison of the (future) template methods to the other techniques.

[JasonLion]

To the best of my knowledge, no one has ever found any meaningful correspondence between templates and the great majority of the human solving techniques. The Pattern Overlay Method is obviously closely related. And it is either believed or proven, I forget which, that if there is a single digit template elimination/placement then there is going to be some kind of fish (likely obscure) with the same elimination/placement.

Your step D seems to me to be a kind of optimization of multi-digit template merging, which will no doubt result in speed ups, but doesn't appear to present any new or different results compared to straightforward merging.

[eleven]

Some of us use the number of rows, columns, boxes and cells as an arbiter for the relative difficulty of moves. Adding the number of digit layers to this seems like a good idea.

IMO a cell is always examined in the context of some intersection of houses. Just a speculation.

The number of cells is interesting, because you can reuse, what you found before. E.g. when you found a pair in a row, you can fade out 7 cells there for a move using the 2 digits. This makes it easier.

Also the number of digits involved is not always a good classification. A 9 cell xy-chain can have all digits, but is not an extremely hard move. But of course moves of over the same number of cells/units normally are easier, when less digits are involved.

So a good classification probably should consider the number of units, cells, candidates, and digits. But i guess, that this cannot be done in reasonable time.

Anyway, each additional classification, which can be calculated fast is a goodie.

[dobrichev]

It is not necessary such classification to follow the difficulty level, although it could help in some degree.

Pair in a row.
There are 2 digits, 1 row, and 2 columns involved.

Pair in a row and box.
There are 2 digits, one row, and one box involved. Depending on needs, we could count also the 2 columns involved.
We might want increasing the involved elements when the purposes are the possible eliminations, or decreasing the involved elements when the purpose is to minimize the calculations in finding the phenomena.

Following this line,
Naked pair in a row.
All columns in 1 row must be processed. 9 times (rows) to scan the entire grid. No eliminations(?), or 2 digits eliminations in 6 cells (= intersection of 1 box and 2 rows) when involved columns intersect same box.

Hidden pair in a row.
All digits in one row must be processed. 9 times. Eliminates 7 digits in 2 cells (= intersection of 2 columns to 1 row).

Yes, it is confusing even for the simple techniques.

[Smythe Dakota]

How about classifying techniques according to the degree of fishiness?

Bill Smythe

[PIsaacson]

You might want to review Allan Barker's set/link set logic http://www.sudokuone.com/ and see how he categorizes various sudoku techniques based on the number of truths/links and rank. Since his logic pretty much covers all known techniques including chains and complex structures, you can use these values for comparing the relative complexity of diverse techniques.

Cheers,
Paul

[dobrichev]

Thank you.
Do you mean http://sudokuone.com/sweb/general.htm? Studying everything in this valuable site would take years...