Sudoku Players' Forum (clone)

Well, as I understand it, in Sherlocking you basically enumerate every possibility and see which ones fit. If you did it over the whole puzzle instead of just 2 rows, it'd basically amount to a brute force search (right)? With more traditional techniques, you make specific deductive eliminations, like "the 3 and 9 can both only be in these two cells in the row, which are both in the same box, so we can eliminate the 3 and 9 from elsewhere in the box".

Sherlocking is just expanding on deduction by looking at the enumerated possibilities of a whole line and making direct logical deductions for which possibilities can be eliminated by comparison to the possibilities for another line. With some other techniques you loose the connection to deduction and simply match the pattern and make the reductions.

As a classification of techniques, I would definitely put sherlock in the class of "Outside the box". Some techniques can be applied directly without the need of pencil marks. Some require simple marks that can be made within the cells of the puzzle. And then there are the advanced techniques that require extra paper or tokens which are outside the box of the original puzzle.

As DanO has stated, after the two lines have been enumerated and compared, a critical element of Sherlock is to make deductions from the surviving lines. The deductions fall into two types, shown by example below

1. "The only surviving value for RxCy is A. Therefore A can be eliminated elsewhere in that row, column and box."

2. "The surviving candidates for RxCy do not include B. Therefore B can be eliminated as a candidate for RxCy, and must be elsewhere in that row, column and box."

A success for deduction 2 often leads to a search for naked pairs, triples etc., as a result.

Sherlock Block expands this set to include the following deduction

3. "Because all surviving lines have C in either line 1 or line 2 in block D, then C can be eliminated from line 3 in block D."

Brendan

The same could be said about naked pairs.

This is just not true. There is no "trial" component where you fill in a cell, let alone up to eighteen cells, with potential values and then see what happens when you eliminate candidates due to naked pairs.

I can come up with all kinds of limited trial and error methods similar to Sherlocking.

For example, fill in a box with all possible digit solutions to that box. Then come up with all the solutions for boxes that share a row or column with the original box. Eliminate conflicts and examine survivors for common traits. That way I can get 33% of the puzzle involved in the guesses instead of just 22%

Or pick two cells. Fill in all possibilties for both the row and the column that contains cell 1. Do the same for cell 2. Eliminate the trials that conflict. Examine the surviving digit patterns for common traits. I get 42% of the cells involved in my limited trial and error method that way, and the two intersecting cells could be most useful in identifying conflicts.

The fact that you have an analysis step at the end does not eliminate the fact that you filled in the cells with many trial values to get to that final step. Analyzing for common survival traits is merely the next step whenever you have a limited trial and error method that allows multiple survivors. That is just the way I see it.

Myth Jellies wrote:

The same could be said about naked pairs.

This is just not true. There is no "trial" component where you fill in a cell, let alone up to eighteen cells, with potential values and then see what happens when you eliminate candidates due to naked pairs.

Actually there is a trial component, but, because there is so few options, it is often overlooked. Take the following naked pair

Code: Select all

12  12  31  ...


This is the trial component - the options for the first two cells are 1 and 2 or 2 and 1. The deductive component is - therefore the candidates 1 and 2 can only occur in the first two cells, and therefore the 1 can be eliminated as a candidate in cell 3.

The fact that you have an analysis step at the end does not eliminate the fact that you filled in the cells with many trial values to get to that final step. Analyzing for common survival traits is merely the next step whenever you have a limited trial and error method that allows multiple survivors.

Exactly as is done with naked pairs. Sherlock just extends this to more cells than two, just as other methods do. As I said earlier, Sherlock still attempts to find the reason for the solution, and therefore does not violate the spirit of Sudoku.

Brendan

I disagree. Yes, all tactics can be cleverly phrased like this to sound like trial and error, but pairs (for example) can be thought about in other ways. Essentially, if you think about the 1 and 2 together, then you're just thinking "the 1-and-2 can't go here, here, or here, so they must go here", or whatever, just like you do with singles.

Naked pair is definitely no trial and no error. It has a pattern to follow and the end result is instant and spontaneous. Use something else to support your argument, but not naked pair please.

I feel that I am running against a fundamentalism that wouldn't dare question the orthodoxy of the basic concepts of Sudoku. Given the history of Sudoku as a puzzle to challenge and expand thinking processes, I find this delisciously ironic. Fortunately, it is not that drastic.

The points in my post above were in response to Myth Jellies suggestion that you couldn't think of naked pairs in terms of trial and error. I was not, and will not, argue that you must think of it only in those terms. But I can definitely argue that you can think of it in those terms.

As an example, I think that 7x6=42. It is instant, spontaneous and thought of as a single block. It doesn't mean that I can't think of it as 7x6=7+7+7+7+7+7 or its alternative, 7x6=6+6+6+6+6+6+6, or even 7x6=100-58.

I wonder, why does the term "trial and error" evoke such a negative response when it is actually quite subjectively defined?

Brendan

Brendan,

Ahhh! I see where I think you are going wrong in your argument. If you understand naked pairs, then you can see the 1-2 candidates in the first two cells of your example and realize that you can eliminate all the 1's and 2's from all of the other cells that share a house with those two. If you do not get the concept of naked pairs or you just miss it, then you might have to resort to a trial where you place the 1 in the third cell and find that it results in a conflict where you can't place a number in one of the first two cells. The thing is, when you do that, or something like it using the first two cells, you aren't doing naked pairs, you are doing trial and error. You haven't thought of naked pairs in terms of trial and error, you have replaced (or perhaps proved) the naked pairs method with a trial and error method. T&E is ultimately powerful, and it can easily replace all of the other methods we have. That is probably the basis for much of the negativity surrounding it.

It seems to me that Myth's "Pattern Overlay Method" and Brendan's "Sherlocking" are very much on similar footing. Here's why I think so ...

In POM, the equivalent of "simple coloring" is used to find a complete set of possible patterns (e.g. 1a,1b,...,2a,2b,...,etc.) for where a given digit can be located.

In Sherlocking, the most basic rules of sudoku are used to find a complete set of possible patterns for what an entire row (or column) can be.

In both methods, deductions are then based on "overlaying" the patterns -- for different digits in the case of POM, for different rows or columns in the case of Sherlocking.

In POM's initial step, each digit candidate in a cell is converted to a list of possible solution patterns for that digit candidate that utilize that cell. You can perform this over the entire puzzle, and you have a whole bunch of labels in your cells; but, except in the rare case where no solution pattern for a candidate digit can occupy a given cell, you are no closer to finding a solution to the puzzle than when you started. In addition, POM never makes any assumptions that any of its candidate digits or patterns or groups of any sort are either true or false. It is stringently anti-T&E. Colors lets you assign a color to an assumption, and another color to its opposite, and follow them around until they conflict. POM doesn't even let you do that.

Contrast this with Sherlock. If you allow Sherlock to operate over the whole puzzle instead of limiting it to two rows, you solve the puzzle via guesses. Don't let the row-vs-row presentation fool you, either. In essence, Sherlock isolates 18 cells, takes one cell and tries every candidate in that cell and eliminates that candidate if it conflicts with the other 17. It repeats this process for all 18 cells. Truly look at your row vs row Sherlock comparisons and you will see that this is what is happening.

I am not trying to demean Sherlock in any way. I find it a useful tool in isolating potential eliminations localized to a pair of columns or rows. One could potentially study these things and perhaps work out a real logical pattern to search for in a convenient row vs row fashion.

As an aside, here is the POM merge grid for the original Sherlock problem.

Code: Select all

{2}{1abcd 8ab}{3     }{1efgh 6a    }{9}{6bc 8cde}{4}{7        }{5                } 
{7}{1e 8c 9a }{1af 9b}{1b 6b 8ad 9c}{5}{4       }{3}{1cg 2a 9d}{1dh 2b 6ac 8be 9e}


It turns out you can use logical POM pattern elimination methods as well as other advanced methods to get rid of 1cdgh, 2b, and 9de; but even when you know this in advance, it is pretty difficult to figure it out.

Myth Jellies wrote:I am not trying to demean Sherlock in any way.

I understand. And I love your POM method. I never knew that it existed until this discussion. That is the type of creative thinking that I enjoy.

Now for Sherlock. Although it is poignant, I hope that you take it in the humor that it is meant.

My Sherlock method of solving Sudoku puzzles requires a slight overhaul in the way that you think about the problem. Normally you are finding all of the digits that possibly fill a cell and then trying to eliminate all choices except for the correct one. When you switch to Sherlock mode you find all of the valid patterns for numbers within a line couplet and try to eliminate all patterns except for the correct one. It turns out that this change in approach can be a powerful tool for solving many, otherwise intractible, puzzles without resorting to forced chains.

The first step is to solve the puzzle as far as you can go using whatever normal methods you have mastered. Personally I solve for everything up to and including XY-wings, although I can miss an X-wing or two if I am really honest. The fewer possibilities you have for a given digit, the easier the next step becomes. Discovery of all XY-wings, swordfish, and other denizens of the deep, may fall out naturally during the next step of the process anyway, but then again, as the next step limits itself to two rows, it may not.

Step two is to take all the possible cells for a line couplet and, by applying the Sudoku rules, find all of the possible unique patterns for that line couplet. Any line pattern that does not contain a valid pattern can be removed as a possibility. I like to create a separate column of patterns for each line, X out any lines where that pattern is not possible, and represent each pattern with a unique letter. You can do this process for each line. Each line couplet that is uses that pattern will contain that pattern's letter. After you practice this method a few times, you can get a feeling for which lines will provide results in the next step quickly and just do those to save time. At this point, we can deduce whether the numbers remain valid - the number can be removed as a possible from any cell that is not contained in a valid pattern. If removing the possibles from the unused cells does not break things open then procede on to step three.

Step 3 uses derived algebraic-logic relationships between patterns of different lines and relies on the fact that only valid solution patterns will propigate smoothly when you merge these patterns together. Assuming you can find all of the logic equations you need, invalid patterns will ultimately be crossed out after the merging process. However, this is theoretical, as I have not yet taken it to its logical endpoint.

Myth, I hope that you have enjoyed this explanation. I will give a more serious address to your concerns at the weekend. But before I do, could you give me a generalised definition of "trial and error"? I think that the argument of whether Sherlock is trial and error will only be solved if we can agree on a tighter definition, i.e. one that I cannot apply to simpler methods. Until your last post, I thought that you were arguing that determining all permutations of a subset of cells constituted trial and error.

Brendan

Sorry if I'm not in the right topic. I'm looking after "unsolvable" puzzles to check my version of chains (I call it "forbidding chains" but it may be well known under other names...). I tried this one provided in this topic by Sue deCoq :

Code: Select all

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

It appeared solvable by FCs (forbidding chains) of length under 6, which in my scale is somewhat simple and humanly bearable. Have you other examples of more "unsolvable" puzzles?

Myth Jellies wrote:In POM's initial step, each digit candidate in a cell is converted to a list of possible solution patterns for that digit candidate that utilize that cell.

You haven't explained how you perform this initial step in which the non-overlapping patterns for a given candidate digit (e.g., 1a, 1b, ...) are determined. If not by some way equivalent to filtering on the digit in the candidate grid, and, as I said, applying "coloring logic" to determine the possible non-overlapping patterns, how is it to be done? (That is the only part of "simple coloring" I was referring to -- not to any further use of it as a solving method.)

r.e.s.

You are certainly right about filtering on the individual digits. After you do that, there are several possible ways of filling out all the possible patterns. For the easier cases, like the two row example I have shown above, it is pretty easy to do by inspection. Each candidate 1 in the top row has 4 available candidate slots in the second row, so plop 1abcd in one and 1efgh in the other, and fill them in the second row as you go. The other numbers were even easier. Another way to go is to use the most basic patterns and/or symmetry to build up a list of reference patterns. For example, it is not too hard to go from

Code: Select all

             
X X X | X X X
X X a | b X X
X X b | a X X

to generating a reference pattern like

X X    X    | X    X    X
X abcd efgh | jlnp ikmo X
X ijkl mnop | bdfh aceg X
------------+------------
X efmn abij | cgko dhlp X
X ghop cdkl | aeim bfjn X
X X    X    | X    X    X

then, if you don't have all those cells open, you can X them out and kill
the patterns they contain.  For example, if in our 4x4 case we don't have
cells r3c5, r4c2, and r4c5, then we can eliminate acdefghlmnp, leaving
only bijko

X X    X    | X    X    X
X .b.. .... | j... ik.o X
X ijk. ..o. | b... (X)  X
------------+------------
X (X)  .bij | ..ko (X)  X
X ..o. ..k. | ..i. b.j. X
X X    X    | X    X    X

and, voila, this is one of those rare cases where you end up eliminating
the candidate in r3c3 because no valid solution pattern can use it.


I am not sure what you mean by using colors to label your solution patterns, but if it works for you, go for it. I've also done things like get the patterns for a portion of the puzzle and then building off of those patterns for the complete puzzle. You can also figure things out based on the number of branchings and convergences from each cell in a box/col/row, to other candidate box/col/row cells. There are lots of ways you can perform the initial POM step.

Brendan,

To my way of thinking, as soon as you have either assumed a particular candidate value in a cell to be true or assumed a particular candidate value to be false, you have started a trial. If you assume a whole row of values to be true, you have started a whole row's worth of trials. When you take every possible row combination then you have started every possible trial on every cell in that row. Do that for two rows and then clash them together and see what eliminates just finishes the 18-cell limited, but very thorough, trial and error process.

No decent definition of trial and error that "cannot be applied to simpler methods" exists, because trial and error can replace all of those simpler methods. Even hidden singles candidate eliminations and solutions can be found using trial and error.