Overlapping Techniques

Advanced methods and approaches for solving Sudoku puzzles

Postby sb1920alk » Tue Jun 19, 2007 12:27 am

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

Postby ravel » Tue Jun 19, 2007 9:34 am

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

Postby RW » Tue Jun 19, 2007 9:43 am

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

Postby sb1920alk » Wed Jun 27, 2007 2:30 am

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

Postby Myth Jellies » Wed Jun 27, 2007 3:28 am

There will always be a hidden set in the remaining cells.
Myth Jellies
 
Posts: 593
Joined: 19 September 2005

Postby sb1920alk » Thu Jun 28, 2007 2:30 am

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

Postby ronk » Thu Jun 28, 2007 12:26 pm

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 single
naked pair        hidden pair
naked triple      hidden triple
naked quad        hidden quad
ronk
2012 Supporter
 
Posts: 4764
Joined: 02 November 2005
Location: Southeastern USA

Postby sb1920alk » Thu Jun 28, 2007 1:37 pm

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 single
naked pair        hidden pair
naked triple      hidden triple
naked 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

Postby Myth Jellies » Thu Jun 28, 2007 2:53 pm

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

Postby ronk » Thu Jun 28, 2007 3:10 pm

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

Postby gsf » Thu Jun 28, 2007 7:06 pm

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

Postby sb1920alk » Thu Jun 28, 2007 11:02 pm

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

Postby sb1920alk » Thu Jun 28, 2007 11:36 pm

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

Postby sb1920alk » Fri Jun 29, 2007 12:12 am

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

Postby gsf » Fri Jun 29, 2007 2:02 am

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

Return to Advanced solving techniques