Overlapping Techniques

Advanced methods and approaches for solving Sudoku puzzles
RW wrote: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

Just a thought...Of the T&E techniques, the first thing that comes to mind is to locate a cell with only two candidates. Pick both candidates, then use simple techniques, then find candidates in other cells that are eliminated by both choices. These candidates can then be removed from the original pencilmark grid. Is this something that has a sudokuian name? I skimmed through the techniques from the link in your first reply, but haven't come across it yet. I'm wondering if it would be any faster than the other T&E techniques.

Thanks,
sb1920alk

Posts: 18
Joined: 13 June 2007

sb1920alk wrote:Of the T&E techniques, the first thing that comes to mind is to locate a cell with only two candidates. Pick both candidates, then use simple techniques, then find candidates in other cells that are eliminated by both choices. These candidates can then be removed from the original pencilmark grid. Is this something that has a sudokuian name?
Thats the good old (double) forcing chain, almost forgotten. See e.g. here or there. It can also be expressed as a simple contradiction chain or nice loop.
ravel

Posts: 998
Joined: 21 February 2006

ravel wrote:
sb1920alk wrote:Of the T&E techniques, the first thing that comes to mind is to locate a cell with only two candidates. Pick both candidates, then use simple techniques, then find candidates in other cells that are eliminated by both choices. These candidates can then be removed from the original pencilmark grid. Is this something that has a sudokuian name?
Thats the good old (double) forcing chain, almost forgotten. See e.g. here or there.

Sudoku Explainer calls this a cell forcing chain, though this is often referred to only as a forcing chain. I use these a lot, but SE is the only program I know of that have implemented these.

RW
RW
2010 Supporter

Posts: 1000
Joined: 16 March 2006

RW wrote:
ravel wrote:
sb1920alk wrote:Of the T&E techniques, the first thing that comes to mind is to locate a cell with only two candidates. Pick both candidates, then use simple techniques, then find candidates in other cells that are eliminated by both choices. These candidates can then be removed from the original pencilmark grid. Is this something that has a sudokuian name?
Thats the good old (double) forcing chain, almost forgotten. See e.g. here or there.

Sudoku Explainer calls this a cell forcing chain, though this is often referred to only as a forcing chain. I use these a lot, but SE is the only program I know of that have implemented these.

RW

Will it ever be the case that a unit will have two sets of naked triples that each reduce candidates elsewhere in that unit where other simple techniques (like hidden pairs) would not?
sb1920alk

Posts: 18
Joined: 13 June 2007

There will always be a hidden set in the remaining cells.
Myth Jellies

Posts: 593
Joined: 19 September 2005

Myth Jellies wrote:There will always be a hidden set in the remaining cells.

Do you think it's possible to narrow it down further and say that the set will never be a hidden triple?
sb1920alk

Posts: 18
Joined: 13 June 2007

sb1920alk wrote:Do you think it's possible to narrow it down further and say that the set will never be a hidden triple?

Here's an example.
Code: Select all
`.......24.1.3......7........6....3......29...8........4..1..6..2......75..9...... 3     9     8     | 567   1567   1567  | 57    2     4#56    1     2     | 3    *45789 *4578  |*5789 #568  #68 56    7     4     | 2     589    58    | 589   13568 1368-------------------+--------------------+------------------ 9     6     15    | 4     1578   1578  | 3     58    2 7     4     3     | 58    2      9     | 58    16    16 8     2     15    | 56    1356   1356  | 4     9     7-------------------+--------------------+------------------ 4     358   7     | 1     358    2     | 6     38    9 2     38    6     | 9     348    348   | 1     7     5 1     358   9     | 5678  35678  35678 | 2     4     38 (#)naked triple = {r2c189} = {568} (*)hidden triple = {r2c567} = {479}`

Any pairing -- with one from each column -- from the following table is possible. Indeed pairings with quints, sextets etc. occur too, but we don't need to look for anything larger than a quad in a 9x9 sudoku.
Code: Select all
`naked single      hidden singlenaked pair        hidden pairnaked triple      hidden triplenaked quad        hidden quad`
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

ronk wrote:Any pairing -- with one from each column -- from the following table is possible. Indeed pairings with quints, sextets etc. occur too, but we don't need to look for anything larger than a quad in a 9x9 sudoku.
Code: Select all
`naked single      hidden singlenaked pair        hidden pairnaked triple      hidden triplenaked quad        hidden quad`

That's cool. I guess I'm asking if we can have two naked triples and a hidden triple in the same unit, or if we have two naked triples that there will never be a hidden triple in that same unit. At that point either technique would remove the same candidates. Also, why is it that quads are sufficient?
sb1920alk

Posts: 18
Joined: 13 June 2007

Two naked triples in the same house when taken together form a naked sextet. If there were nine unsolved cells in the house, then the remaining three cells would contain a hidden triple. You might be able to break that hidden triple down into smaller hidden sets as well, such as a hidden pair-hidden single combination, or three hidden singles.

Note that after all deductions are made in a house, a hidden set qualifies as a naked set, and vice versa.
Myth Jellies

Posts: 593
Joined: 19 September 2005

sb1920alk wrote:I guess I'm asking if we can have two naked triples and a hidden triple in the same unit, or if we have two naked triples that there will never be a hidden triple in that same unit.

While I've never seen three triples in one unit, I don't know the answer to that question. If three triples in one unit does exist, I suspect they occur rarely. Even one naked triplet in a unit with no "big numbers" (fills, givens plus placements) is relatively rare.

[edit: I found only this one in a scan of over 50,000 puzzles.]
Code: Select all
`#8165 from Ruud's recently published 10,000..3..2.94...94.....1....26.......547..9...6..387.......31....7.....76...79.5..4..After some Simple Sudoku steps: 58    57    3     | 168   1568  2     | 17    9     4 2568  2567  2568  | 9     4     1358  | 137   1358  1358 9     1     4     | 378   358   3578  | 2     6     358-------------------+-------------------+------------------ 1     26    26    | 38    389   389   | 5     4     7 45    45    9     | 127   12    17    | 6     1238  1238 3     8     7     | 1246  1256  145   | 19    12    129-------------------+-------------------+------------------ 2456  3     1     | 24    29    49    | 8     7     256 2458  245   258   | 12348 7     6     | 139   1235  12359 7     9     268   | 5     1238  138   | 4     123   1236 naked  triple = {r4c456} = {389} naked  triple = {r5c456} = {127} hidden triple = {r6c456} = {456}`

Also, why is it that quads are sufficient?

With no fills, a naked quint would be paired with a hidden quad.
With no fills, a hidden quint would be paired with a naked quad.
With one fill, a naked quint would be paired with a hidden triple.
With one fill, a hidden quint would be paired with a naked triple.
Etc, etc, etc.
ronk
2012 Supporter

Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

ronk wrote:[edit: I found only this one in a scan of over 50,000 puzzles.]
Code: Select all
`#8165 from Ruud's recently published 10,000..3..2.94...94.....1....26.......547..9...6..387.......31....7.....76...79.5..4..After some Simple Sudoku steps:`

I had to recheck -- the naked triple is found because the ss order applies naked triple before hidden pair
otherwise a hidden pair would/could apply at this point
I keep forgetting that many questions like this rely heavily on the (assumed) constraint/technique order
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

ronk wrote:
Also, why is it that quads are sufficient?

With no fills, a naked quint would be paired with a hidden quad.
With no fills, a hidden quint would be paired with a naked quad.
With one fill, a naked quint would be paired with a hidden triple.
With one fill, a hidden quint would be paired with a naked triple.
Etc, etc, etc.

That makes perfect sense.

Thanks,
sb1920alk

Posts: 18
Joined: 13 June 2007

Myth Jellies wrote:Two naked triples in the same house when taken together form a naked sextet. If there were nine unsolved cells in the house, then the remaining three cells would contain a hidden triple. You might be able to break that hidden triple down into smaller hidden sets as well, such as a hidden pair-hidden single combination, or three hidden singles.

Note that after all deductions are made in a house, a hidden set qualifies as a naked set, and vice versa.

Ok, I think I've got it. As it relates to this question, I'm primarily concerned with avoiding the need to program the ability to search for two naked triples in the same unit. I have it set so combinations of cells that contain big numbers are not consided a naked triple. So all I need to do is process hidden triples prior to naked triples, and I will at most have one naked triple in that unit that can further reduce candidates.

Thanks,
sb1920alk

Posts: 18
Joined: 13 June 2007

gsf wrote:I keep forgetting that many questions like this rely heavily on the (assumed) constraint/technique order

Now that you mention it: Is there a particular order that most programs use either to optimize speed, or to solve as a human would?
sb1920alk

Posts: 18
Joined: 13 June 2007

sb1920alk wrote:
gsf wrote:I keep forgetting that many questions like this rely heavily on the (assumed) constraint/technique order

Now that you mention it: Is there a particular order that most programs use either to optimize speed, or to solve as a human would?

there's some basic agreement among implementations
but its also a matter of taste, manual solving habits, and the subset of techniques implemented by each solver
I gave up a long time ago and made the constraint order programmable from the command line
gsf
2014 Supporter

Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Previous