|
| View previous topic :: View next topic |
| Author |
Message |
| Bob Hanson
| | Joined: 05 Oct 2005 | | Posts: 187 | | : | | Location: St. Olaf College |
Items |
|
 Posted: Wed Nov 16, 2005 4:27 pm Post subject: locked candidates, naked/hidden subsets,x-wings,grids same |
 |
|
In thinking about expanding Sudoku Assistant http://www.stolaf.edu/people/hansonr/sudoku
to solve NxN Sudoku, it dawned on me that all of the following:
cross-hatch scanning,
locked candidates,
naked/hidden subsets,
x-wings, swordfish, and
grids
are all just permutations of the same thing.
Previously, (see http://www.stolaf.edu/people/hansonr/sudoku/explain.htm#grids) I've shown that all but locked candidates
are the same. Now I'd like to add locked candidates as well.
Locked Candidates:
The generally expressed idea for locked candidates is that once a number can be assigned to a given row(column) of a specific block (even if its exact location is still unknown), no other block may have that same number in the same row(column), and no other row(column) of that block may contain that candidate. It's a symmetric arrangement.
If [....] represents a three-cell "subset" of a row, then a row looks like this:
and a 3x3 block looks like this:
and a 3-wide set of 3x3 blocks looks like this:
| Code: |
[ a ] [ b ] [ c ]
[ d ] [ e ] [ f ]
[ g ] [ h ] [ i ]
|
and our "locked candidate" idea looks like this, where "--X--" means the candidate X is "somewhere in this set of cells":
| Code: |
either
[ no X ] [ b ] [ c ]
[ no X ] [ e ] [ f ]
[--X---] [ h ] [ i ]
or
[ a ] [ b ] [ c ]
[ d ] [ e ] [ f ]
[--X---] [ no X ] [ no X ]
implies
[ no X ] [ b ] [ c ]
[ no X ] [ e ] [ f ]
[--X---] [ no X ] [ no X ]
|
I find it interesting that you can think of this either as a "hidden single" (focusing on X) or as a mini "block-based" X-wing (focusing on sets b, c, e, and f). What we have here is a simple 3x3 variant of a 9x9 concept.
OK, so if you go to 16x16 Sudoku, each 4-wide set of 4x4 blocks looks like this:
| Code: |
[ a ] [ b ] [ c ] [ d ]
[ e ] [ f ] [ g ] [ h ]
[ i ] [ j ] [ k ] [ l ]
[ m ] [ n ] [ o ] [ p ]
|
(Four of these stacked on top of each other constitute the entire puzzle.)
What's interesting, I think, is that the "locked candidate" idea now expands to also include something that DEFINITELY looks like an X-Wing:
| Code: |
[ no X ] [ no X ] [ c ] [ d ]
[ no X ] [ no X ] [ g ] [ h ]
[--X---] [--X---] [ k ] [ l ]
[--X---] [--X---] [ o ] [ p ]
implies:
[ no X ] [ no X ] [ c ] [ d ]
[ no X ] [ no X ] [ g ] [ h ]
[--X---] [--X---] [ no X ] [ no X ]
[--X---] [--X---] [ no X ] [ no X ]
|
We also have the "hidden single/now Swordfish" thing as well, it's just that we also have this new thing. Or, is it new? Not really. A 25x25 Sudoku would have the same business, but now an X-Wing/Swordfish combination would arise.
The point is simply that IN GENERAL all these strategies for solving an NxN Sudoku puzzle are the same. A single function (such as the one used by Sudoku Assistant to find all naked and hidden tuples, all X-wings, all swordfish, all related grid-based "patterns") would suffice to all handle all NxN possibilities of locked candidates as well. The only difference is that we would send a "condensed" version of the Sudoku (binary OR of candidates in subsets [...]) to the function. In a 9x9 Sudoku, this would be 3x3 "mini-Sudoku"; in the case of 16x16 Sudoku, this would be a mini 4x4 Sudoku.
Beyond this, any coloring or tabling or such strategies are just subsets of logical chain analysis, a general feature of any NxN Sudoku.
I just thought that was interesting.
I know that you don't need any of this "human" stuff to solve Sudoku puzzles -- all you need is trial and error with "depth" (branching). I think what the human methods do is give an aspect of depth to the solving that simple logical chain analysis can't provide without branching. That's why they are so effective in aiding in the solution of so many Sudoku puzzles.
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr |
|
| Back to top |
|
 |
| arsoncupid
| | Joined: 22 Nov 2005 | | Posts: 10 | | : | |
Items |
|
| Posted: Wed Nov 23, 2005 5:48 pm Post subject: |
|
|
| I think it's interesting you said that. In working my daily puzzles by hand, I've yet to find a use for X-wing. I think it comes from the method I use to fill in candidates. I look for pairs or triplets in a row or column and also in a single 3x3 grid when I first start work on a puzzle. Later, when I fill in the remaining candidates, I respect the consequences of those early marks. |
|
| Back to top |
|
|
| rkral
| | Joined: 21 Oct 2005 | | Posts: 233 | | : | |
Items |
|
| Posted: Wed Nov 23, 2005 6:13 pm Post subject: |
|
|
| arsoncupid wrote: | | In working my daily puzzles by hand, I've yet to find a use for X-wing. |
Here's one for practice ... | Code: |
*-----------*
|.8.|..4|15.|
|..4|7..|3.8|
|...|8..|4..|
|---+---+---|
|41.|285|9..|
|6.5|1..|284|
|...|.46|51.|
|---+---+---|
|342|6..|895|
|...|5..|741|
|751|498|6..|
*-----------* |
... with candidates ... | Code: |
*--------------------------------------------------------------------*
| 29 8 3679 | 39 236 4 | 1 5 2679 |
| 15 269 4 | 7 1256 129 | 3 26 8 |
| 15 23679 3679 | 8 12356 1239 | 4 267 2679 |
|----------------------+----------------------+----------------------|
| 4 1 37 | 2 8 5 | 9 367 367 |
| 6 39 5 | 1 37 379 | 2 8 4 |
| 289 2379 3789 | 39 4 6 | 5 1 37 |
|----------------------+----------------------+----------------------|
| 3 4 2 | 6 17 17 | 8 9 5 |
| 89 69 689 | 5 23 23 | 7 4 1 |
| 7 5 1 | 4 9 8 | 6 23 23 |
*--------------------------------------------------------------------* |
|
|
| Back to top |
|
|
| Bob Hanson
| | Joined: 05 Oct 2005 | | Posts: 187 | | : | | Location: St. Olaf College |
Items |
|
| Posted: Wed Nov 23, 2005 7:17 pm Post subject: |
|
|
| Quote: | | I think it's interesting you said that. In working my daily puzzles by hand, I've yet to find a use for X-wing. I think it comes from the method I use to fill in candidates. I look for pairs or triplets in a row or column and also in a single 3x3 grid when I first start work on a puzzle. Later, when I fill in the remaining candidates, I respect the consequences of those early marks. |
It's possible your method amounts to an X-wing check. But usually these show up "late in the game".
I think all the Sudoku puzzles in our paper rate "5 stars" as being just "looking for locked candidates", which in my opinion is "easier" than X-wings and such. Having written the web site Sudoku Assistant, I realize now that anyone saying they can "solve any Sudoku by hand" (without guessing) is probably just naive. Or lucky. (I'm sure I've solved plenty of Sudoku puzzles by hand by making a "key" logical mistake.)
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr |
|
| Back to top |
|
|
| arsoncupid
| | Joined: 22 Nov 2005 | | Posts: 10 | | : | |
Items |
|
| Posted: Wed Nov 23, 2005 8:29 pm Post subject: |
|
|
| Bob Hanson wrote: |
It's possible your method amounts to an X-wing check. But usually these show up "late in the game". |
After looking at rkral's puzzle, I see my method doesn't equal an X-wing. I've just been blessed with the scope of puzzles in my newpaper. 
@ rkral: Yeay! Thank you for that: awesome.
I cannot solve this without X-wing or forcing chains, or some other higher method. With forcing chains, it's easy to exclude from the bottom-left 3x3 box. With X-wing, it's the 9s (and arguably easier!) |
|
| Back to top |
|
|
| Bob Hanson
| | Joined: 05 Oct 2005 | | Posts: 187 | | : | | Location: St. Olaf College |
Items |
|
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
