The New Sudoku Players' Forum

[Brendan]

As a newbie, I have read the usual online techniques. But I came up with one that I wonder whether it is new. It is a row comparison technique, that it a bit similar to forced chains in outcome. It is a technique that I use before Nishio but after most other simpler techniques. I don't know what tabling is, (the online sources didn't mention them) so it could be a form of tabling with very specific goals. I call it Convergence, and will explain by means of an example

Purpose: To reduce the number of possible options in cells across a row.

Example:

ROW 1 => | 2 18 3 | 16 9 68 | 4 7 5 |
ROW 2 => | 7 189 19 | 1689 5 4 | 3 129 12689 |

These rows are separated, not in the same square, although there is no reason that the technique cant be used for rows in the same square.

I begin by writing all the options for the unknowns in the first line on a blank page and assigning a monica to it

1 6 8 - A
8 1 6 - B

I then write out all the options for the second line

19628
19826
81629
81692
81926
89126
89612
89621
91628
91826

Now the first two unknown digits of the top row align with the first and third digits of the bottom row. I put arrows above to remind myself of where they are. Then I check through the options, making sure that if I use a particular number in the first line, I don’t also use that number at that same location in the second line. If the top line option doesn’t conflict with the bottom line option, I write the letter next to it as below. Then I check to see if any of the options converged, by crossing out the incompatible lines (that have no letters next to them) and checking the remaining options in each column.

Code: Select all

 ↓ ↓
 19628  B
 19826  B
 81629  (Crossed out)
 81692  (Crossed out)
 81926 A
 89126 A
 89612  (Crossed out)
 89621  (Crossed out)
 91628  B
 91826 AB



In this example, the first three digits of the bottom line still remain unknown, with the same number of options as before. The fourth digit, however, all compatible options converge to the number 2, as all the other options are incompatible with the top line. The last digit has reduced its options from five down to two, the numbers 6 and 8.

I find that I generally only have to do this once to break open the puzzle. The real trick is working out which lines to compare, as results don't always converge. I look for short rows for my top row, effective forcing chains in my second row, and, most importantly, a mix of mutual unknowns in the intersecting columns. These limit the range of possibilities that are to be written out and compared, and maximise the possibility that some can be eliminated. The ability to reduce the options in more than one cell at a time is also quite useful.

Brendan

[Lummox JR]

I'm not sure I follow this technique, but maybe it's the example. Your example is of an invalid grid. This can't possibly ever happen:

ROW 1 => | 1 18 3 | 16 9 68 | 4 7 5 |

If you've pinned down 1 at (1,1), that leaves 8 at (2,1) and 6 at (4,1). Both of those eliminate all of the candidates in (6,1), so you have a condradiction.

[angusj]

I'm not sure I follow this technique, but maybe it's the example.

Yes, I found it required a bit of patience to follow. However, it is perfectly logical apart from the presumed typo where the first cell in the top row is 2 (not 1).

[Brendan]

Oops, sorry about the typo. The first line should have been

|2 18 3 | etc

1 next to 2, you know.....

I have now corrected it

Brendan

I'm not sure I follow this technique, but maybe it's the example. Your example is of an invalid grid. This can't possibly ever happen:

ROW 1 => | 1 18 3 | 16 9 68 | 4 7 5 |

If you've pinned down 1 at (1,1), that leaves 8 at (2,1) and 6 at (4,1). Both of those eliminate all of the candidates in (6,1), so you have a condradiction.

[cho]

This could be quite useful. I will have to watch for opportunities to try it. At my stage of development (trying to master Wayne's hard puzzles), I haven't really been looking at what ifs since branching and forcing chains are not needed, and I want to get good at the basics before venturing on. But this is simple enough and as angusj said, perfectly logical.

The example given looks like something that might be encountered frequently. I would probably not have the patience to make a table, but your example looks simple enough to spot and evaluate mentally. If row 1 is 1 6 8, then row 2 has a 189 triple, a 2 and a 6. If it is 8 1 6, then row 2 has a 19 pair, a 2, and a 68 pair. So the 2 is nailed and the last set of candidates can be set to 68.

Thanks, Brendan.

cho

[Nick67]

Hi Brendan,

Looks like a nice technique! Alas, I couldn't tell
you if it is new or not. You might try posting
in the programmers' forum, too, for more feedback.

One question for you:

I look for short rows for my top row, effective forcing chains in my
second row, and, most importantly, a mix of mutual unknowns in the
intersecting columns.

Could you please explain "effective forcing chains"? (I'm familiar with forcing chains,
but I just can't quite picture what you mean here.)
Thanks.

[Brendan]

Hi Brendan,

Looks like a nice technique! Alas, I couldn't tell
you if it is new or not. You might try posting
in the programmers' forum, too, for more feedback.

One question for you:

I look for short rows for my top row, effective forcing chains in my
second row, and, most importantly, a mix of mutual unknowns in the
intersecting columns.

Could you please explain "effective forcing chains"? (I'm familiar with forcing chains,
but I just can't quite picture what you mean here.)
Thanks.

What I termed "effective forcing chains" are one dimensional chains such as

| 12 123 1234 | 15 16 ...

whereby if you set one number, you can markedly reduce the number of options in the row. I don't know if it has another term already, but it has to be within the row (or column of course)

Brendan

[DanO]

If this doesn't have a name already, Enumeration might be a good choice since what you are doing is enumerating the permitted permutations.

I tried it out on the "Toughest Known Puzzle" by enumerating the first two rows and was surprised that the permitted values [12] dropped out of R1C1 and R1C3. Unfortunately, it didn't help solve the puzzle but it does indicate that there is a pattern in those two rows that isn't being found by the simple rules.

[Lummox JR]

Now that I finally understand this technique I definitely do see the value in it. The original post threw me off a bit because those arrows didn't align with the digits in the post; putting that in a code block would make it a little clearer.

I see also one other interesting aspect of this test: If one of the A or B choices doesn't get marked for any of the 2nd row, it cannot be valid. You can use this to perform a kind of double elimination.

Given that this test relies on two columns or two rows and on the digits that line up between them, I think it makes sense to call this test Alignment. I'd reserve the term enumeration for cases where you're only testing the possibilities of a single column/row (or box!).

It's very interesting that you found two eliminations in row 1 for the toughest known puzzle. I see you found MadOverlord's post on that, and he too had noticed the possibility of a pattern to be found involving row 1.

[Nick67]

Now that I finally understand this technique I definitely do see the value in it. The original post threw me off a bit because those arrows didn't align with the digits in the post; putting that in a code block would make it a little clearer.

Yeah, in my browser the 2 arrows look like they are above columns 1 and 2,
instead of columns 1 and 3 as intended.

Maybe we can persuade Brendan to edit the original post, placing that
part in a code block like this:

Code: Select all

↓ ↓
19628 B
19826 B
81629 (Crossed out)
81692 (Crossed out)
81926 A
89126 A
89612 (Crossed out)
89621 (Crossed out)
91628 B
91826 AB


... especially since his whole idea seems like a good one!

[Brendan]

I have edited the post to get the arrows right, as suggested. Thanks.

On the topic of arrows, I have been experimenting with multiple arrows when comparing with lines within a 3x3 block. These rows have the extra constraints that may help. Eg. If the following were in the same block

Code: Select all

| 12 13 23 | 14 5  6  | 7  8 9 |
| 14 15 16 | 17 18 19 | 48 2 3 |


then a 1 in the first three columns of the first row would eliminate all possibilities with 1 in the first three columns in the second row.

As the purpose of the arrows is simply to remind me where to look, I use cross arrows to indicate two digits could eliminate a possibility and curly sideways brackets for three digits.

Brendan

[PaulIQ164]

Caould we see the entire puzzle that the example in the first post came from? I'm just worried that this method might be equivalent to some other method that we can't see fully because the rest of the puzzle is hidden.

[gsf]

this is similar to a forward checking backtrack search:
(1) pick an unsolved cell
(2) attempt each candidate value for the cell by assigning the cell value
and propagating constraints

each attempt will result in one of:

(a) contradiction -- cell cannot have that value
(b) constrained puzzle -- puzzle solved by logic constraints
(c) indeterminate -- no contradiction no solution .. yet

(3) once all the attempts are done for a given cell examine the pinned values for each indeterminate attempt -- if any cell has the same pinned value for all indeterminate attempts then that must be the solution value for that cell; otherwise the candidate values for a given cell can be accumulated over the indeterminate attempts, possibly reducing the candidate set for that cell

if the puzzle is 1-constrained (at least 1 magic cell that cracks the puzzle) then the forward checking will eventaully find one of those magic cells (by looping on (1) until attempt result (b)) and solve the puzzle without backtracking

the new technique limits the constraint propagation to two rows/cols
but its still trial and error, no?

[Lummox JR]

the new technique limits the constraint propagation to two rows/cols
but its still trial and error, no?

No indeed. Trial and error has a specific placement to prove true or false; this does not. This method compares possible sets to determine which interfere with each other, and which can never be chosen. Based on that it can look for 1) digits which never appear in a certain position, or even better 2) digits which always appear in a certain position.

[gsf]

No indeed. Trial and error has a specific placement to prove true or false; this does not. This method compares possible sets to determine which interfere with each other, and which can never be chosen. Based on that it can look for 1) digits which never appear in a certain position, or even better 2) digits which always appear in a certain position.

are you saying trial and error is limited to "does this move solve the puzzle"?