|
| View previous topic :: View next topic |
| Author |
Message |
| gaby
| | Joined: 02 Jul 2005 | | Posts: 120 | | : | |
Items |
|
 Posted: Mon Jul 18, 2005 10:28 pm Post subject: disjoint subsets/number chains, same thing? |
 |
|
I've been reading the comments in the code of my PHP solver. I wrote this for disjoint subsets (which I used to call matched pairs):
| Code: | * Try disjoint subset matching, also called matched pairs, triplets,
* etc, up to num_end - 1. This used to be called matched pairs, where
* it only looked for sets of 2 numbers in 2 cells, but it actually
* works for n numbers in n cells.
*
* Look at a row and see if there are any instances where there are
* only 2 numbers in 2 cells. If these are the only numbers in these
* cells then we can remove the two numbers from all the other cells
* in the row.
* Repeat this for columns and blocks.
* Repeat this for sets of 3, 4, 5, etc, numbers.
*
* A more general definition:
* A cellset is all the free cells in a row, column or block.
* If we find a set {s} of n numbers that are the only numbers
* that appear in n cells {c}, then we can remove the numbers in {s}
* from all the other cells in the cellset that are not in {c}
|
And I then read this about number chains:
| Code: |
* Look at a row in the solution grid to see if there are any cells
* that form number chains - as simple as [18]-[18] or as complex
* as [123]-[234]-[134]-[124]. If so, these cell must be the cells
* that contain those numbers, so eliminate the numbers in the chain
* from all the other cells in the line. Repeat for columns and blocks
*
* http://www.sudokusolver.co.uk/solvemethods.html (Method D)
* Also with some help from Anna
*
* A more general version:
* A cellset is all the free cells in a row, column or block.
* Look at all the numbers that occur in a cellset, {x}. Work out every
* possible permutation of these numbers. We only want permutations that
* are between 2 numbers and X numbers, where X is the size of {x}.
* For each permuatation of numbers {s}, look at which cells they appear
* in in the cellset {c}. If {s} and {c} are the same size, then we can
* remove all the numbers in {s} from all other cells in the cellset that
* are not in {c}.
|
Now reading these two comments, and thinking about how they work, they're effectively the same thing. Each method looks for a set of n numbers that appear in n cells (3 numbers in 3 cells, 4 in 4 cells, etc), then either removes these numbers from other cells or removes the other candidates from those cells.
The more I think about it the more I can see that any condition caught by disjoint subsets will also be caught by number chains. disjoint subsets requires that the cells be matched, whereas number chains works using permutations of all the possible numbers in the rows. Although working with cells is quicker, as there are less permutations, number chains will find anything that disjoint subsets matches, and then more on top.
Am I right in thinking that number chains and disjoint subsets are the same thing? Will they have the same effect? Do I even need to bother with both?
If anyone can solve my mystery, I would appreciate it... 
Gaby
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/ |
|
| Back to top |
|
 |
| jaap
| | Joined: 13 Jun 2005 | | Posts: 24 | | : | | Location: NL |
Items |
|
| Posted: Tue Jul 19, 2005 6:37 am Post subject: Re: disjoint subsets/number chains, same thing? |
|
|
| gaby wrote: | | Am I right in thinking that number chains and disjoint subsets are the same thing? |
They look exactly the same to me.
I have also found certain rules to be the same thing in my solver. This is because it treats things such as 'the possible placements of digit 7 in column 4' the same way as 'the possible values of cell (3,5)'.
This means that matched pairs is treated the same as X-wings. For example, an X-wings in my solver gives the output:
| Code: | Must have number 9 at (1,5) (and number 9 at (9,8))
or number 9 at (9,5) (and number 9 at (1,8))
reducing options for digit 9 in column 5
Must have number 9 at (1,8) (and number 9 at (9,5))
or number 9 at (9,8) (and number 9 at (1,5))
reducing options for digit 9 in column 8 |
and a matched pair gives the output:
| Code: | Must have number 2 at (1,2) (and number 3 at (1,9))
or number 2 at (1,9) (and number 3 at (1,2))
reducing options for digit 2 in row 1
Must have number 3 at (1,2) (and number 2 at (1,9))
or number 3 at (1,9) (and number 2 at (1,2))
reducing options for digit 3 in row 1 |
In the same way (if I had implemented them) a matched triplet would be equivalent to swordfish, a matched quadruplet equivalent to Jellyfish, etc.
_________________
Jaap
--
Jaap's Puzzle Page:
http://www.geocities.com/jaapsch/puzzles |
|
| Back to top |
|
|
| tilps
| | Joined: 19 Jun 2005 | | Posts: 44 | | : | |
Items |
|
| Posted: Tue Jul 19, 2005 10:55 am Post subject: Re: disjoint subsets/number chains, same thing? |
|
|
| jaap wrote: |
In the same way (if I had implemented them) a matched triplet would be equivalent to swordfish, a matched quadruplet equivalent to Jellyfish, etc. |
To be pedantic, matched triplets and swordfish are different - swordfish is the equivlent of 3 cells containing possibilities of 1,2 2,3 3,1 - triple chained pairs. |
|
| Back to top |
|
|
| gaby
| | Joined: 02 Jul 2005 | | Posts: 120 | | : | |
Items |
|
| Posted: Tue Jul 19, 2005 11:15 am Post subject: |
|
|
So, disjoint subsets/matched pairs/number chains can all be summarised like this:
| Code: |
A cellset {s} is all the free cells in a row, column or block.
If we look through our cellset {s} and we find a set of cells {c} that:
1. Contain the candidate numbers {n} between them
2. They only contain the candidates {n} and no other numbers
3. There are X numbers in {n}, and X cells in {c} (the same size)
Then we can remove all the numbers in {n} from the cells in the cellset that are not in {c} (this is {s} - {c}).
|
And the inverse, or 'hidden' versions of these can be summarised as:
| Code: |
A cellset {s} is all the free cells in a row, column or block.
If we look through our cellset {s} and we find a set of numbers {n} where:
1. The numbers in {n} *only* appear in the cells {c} and in no other cells
2. There are X numbers in {n}, and X cells in {c} (the same size)
Then we can remove all the numbers *not* in {n} from the cells in {c}.
|
A matched pair is a number chain where X=2.
tilps, I agree that matched triplets and swordfish are different. Matched triplets is a number chain where X=3? Swordfish is finding X pairs on X rows in X columns.
Gaby
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/ |
|
| Back to top |
|
|
| Nick70
| | Joined: 08 Jun 2005 | | Posts: 160 | | : | |
Items |
|
| Posted: Tue Jul 19, 2005 11:48 am Post subject: |
|
|
| gaby wrote: | | tilps, I agree that matched triplets and swordfish are different. Matched triplets is a number chain where X=3? Swordfish is finding X pairs on X rows in X columns. |
Not really. See here. |
|
| Back to top |
|
|
| gaby
| | Joined: 02 Jul 2005 | | Posts: 120 | | : | |
Items |
|
| Posted: Tue Jul 19, 2005 4:34 pm Post subject: |
|
|
From that example, my swordfish algorithm would find that quite happily. What I think I was saying that disjoint subsets/matched pairs/matched triplets will also be found by my generic number chains algorithm, as outlined in the comments above.
Swordfish is a different technique that is looking for a different pattern, so doesn't cover possibilites found by number chains. Swordfish where N=2 is X-wings. N=3 is Swordfish, N=4 is Jellyfish, N=5 is Squirmbag, etc. etc.
In terms of implementation, the more specific versions (matcher pairs, x-wing) are quicker to run, because they're not looking through every permutation of numbers in cells, they're just trying the various cells that are there. Usually there are fewer permutations of cells then there are possible permutations of numbers in those cells.
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/ |
|
| Back to top |
|
|
| ulfn
| | Joined: 25 Jul 2005 | | Posts: 3 | | : | |
Items |
|
| Posted: Mon Jul 25, 2005 8:10 pm Post subject: |
|
|
In fact the hidden version is exactly the same as the normal version on the set {s} - {c}:
Assume that you find that two cells in a row can only contain 1 or 2. The chain rule now states that we can remove all 1s and 2s from the other cells.
But we also have that the numbers 3-9 can only occur in the remaining 7 cells, so the inverse rule allows us to remove all numbers that aren't 3-9 from these cells (i.e. 1 and 2).
/ Ulf |
|
| Back to top |
|
|
| kranser
| | Joined: 18 Aug 2005 | | Posts: 35 | | : | |
Items |
|
| Posted: Mon Oct 03, 2005 10:26 pm Post subject: |
|
|
| ulfn wrote: | In fact the hidden version is exactly the same as the normal version on the set {s} - {c}:
Assume that you find that two cells in a row can only contain 1 or 2. The chain rule now states that we can remove all 1s and 2s from the other cells.
But we also have that the numbers 3-9 can only occur in the remaining 7 cells, so the inverse rule allows us to remove all numbers that aren't 3-9 from these cells (i.e. 1 and 2).
/ Ulf |
Very true!
In my solver I'm only implementing Disjoint Subsets, and it finds Disjoint Chains as well (due to the reasoning stated by Ulf).
However, the only problem I have with this is that I base my difficulty calculation based on the number of Disjoint Subset candicates (i.e. Tripple is more difficult than Twin), and I'm getting some Disjoint Subsets found with 4 or 5 disjoint candicates - causing my solver to treat the puzzle as difficult! However, if Disjoint Chains were looked for first before Disjoint Subsets, this may eliminate most of these occurences! Not tried it though. |
|
| Back to top |
|
|
| Pat
 | | Joined: 06 Sep 2006 | | Posts: 128 | | : | |
Items |
|
| Posted: Thu Nov 30, 2006 4:30 pm Post subject: re: X-wing ~~ duo |
|
|
[ off-topic ]
| jaap (2005.Jul.19) wrote: | my solver treats things such as 'the possible placements of digit 7 in column 4' the same way as 'the possible values of cell (3,5)'.
This means that matched pairs is treated the same as X-wings.
For example, an X-wings in my solver gives the output:
| Code: | Must have number 9 at (1,5) (and number 9 at (9,8))
or number 9 at (9,5) (and number 9 at (1,8))
reducing options for digit 9 in column 5
Must have number 9 at (1,8) (and number 9 at (9,5))
or number 9 at (9,8) (and number 9 at (1,5))
reducing options for digit 9 in column 8 |
and a matched pair gives the output:
| Code: | Must have number 2 at (1,2) (and number 3 at (1,9))
or number 2 at (1,9) (and number 3 at (1,2))
reducing options for digit 2 in row 1
Must have number 3 at (1,2) (and number 2 at (1,9))
or number 3 at (1,9) (and number 2 at (1,2))
reducing options for digit 3 in row 1 |
In the same way (if I had implemented them) a matched triplet would be equivalent to Swordfish, a matched quadruplet equivalent to Jellyfish, etc. |
this idea has been mentioned in various places,
does anyone know if this is the ealiest-ever ??
|
|
| 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
