|
| View previous topic :: View next topic |
| Author |
Message |
| MadOverlord
| | Joined: 01 Jun 2005 | | Posts: 80 | | : | | Location: Wilmington, NC, USA |
Items |
|
 Posted: Sun Oct 16, 2005 5:50 pm Post subject: Uniqueness - a possible simplification? |
 |
|
I have been playing around with the uniqueness test, adding it to the latest version of the Susser. I think -- but am not sure -- that I have found a simplification that may extend the test, and I wanted to run it by the group before I continue implementation. I am, btw, indebted to the forums for posting sample puzzles, it made my life a lot easier! All of the examples below were scraped from the forums.
Uniqueness patterns are often described by this nomenclature, which I'll use. I'm not going to get into the "type b" versions, just the original ones:
The basic type of uniqueness is of this form:
The 123 must be a 3, because otherwise, we collapse to a 2-solution puzzle. I explain it like this in the Susser:
| Code: |
+----------------+----------------+----------------+
| 25 8 24 | 45 6 3 | 9 7 1 |
| 357 37 1 | 58 2 9 | 6 4 358 |
| 6 39 349 | 458 7 1 | 238 28 2358 |
+----------------+----------------+----------------+
| 4 25 2356 | 7 9 8 | 1 26 23 |
| 27 1 26 | 3 4 5 | 278 268 9 |
| 379 379 8 | 6 1 2 | 37 5 4 |
+----------------+----------------+----------------+
| 8 25 25 | 1 3 7 | 4 9 6 |
| 39 4 39 | 2 8 6 | 5 1 7 |
| 1 6 7 | 9 5 4 | 28 3 28 |
+----------------+----------------+----------------+
|
* Squares R7C2, R7C3, R4C2 and R4C3 form a Unique Rectangle on <25>. Because they share two rows, two columns, and two blocks, if they all had possibilities <25> then the puzzle would have two solutions; you could simply exchange the <2>'s with the <5>'s in those four squares to get the other solution, and their common rows, columns and blocks would still contain one of each value. Since a valid Sudoku can have only one solution, R4C3 cannot contain <25>, since if it has either value, the other squares will immediately be forced into a two-solution configuration.
Ok, so far so good (though suggestions on improving the explanation are always appreciated!). The next version looks like this:
One of the 123 squares must be 3, or we collapse to a 2-solution puzzle. I explain it like this in the Susser:
| Code: |
+----------------------+----------------------+----------------------+
| 9 3 6 | 14 128 148 | 24 7 5 |
| 8 7 5 | 49 29 3 | 246 246 1 |
| 1 4 2 | 7 5 6 | 3 8 9 |
+----------------------+----------------------+----------------------+
| 236 26 7 | 134569 1369 149 | 8 1359 24 |
| 5 1 4 | 8 39 2 | 7 39 6 |
| 236 8 9 | 13456 7 14 | 15 135 24 |
+----------------------+----------------------+----------------------+
| 4 25 18 | 16 168 7 | 9 25 3 |
| 236 256 138 | 139 4 189 | 125 125 7 |
| 7 9 13 | 2 13 5 | 46 46 8 |
+----------------------+----------------------+----------------------+
|
* Squares R9C7, R9C8, R2C7 and R2C8 form a Unique Rectangle on <46>. Because they share two rows, two columns, and two blocks, if they all had possibilities <46> then the puzzle would have two solutions; you could simply exchange the <4>'s with the <6>'s in those four squares to get the other solution, and their common rows, columns and blocks would still contain one of each value. Since a valid Sudoku can have only one solution, either R2C7 or R2C8 must be a <2>; if neither has that value, then the other squares obviously form a two-solution configuration. This means that <2> can be removed from all the other squares in block 3 and row 2, since we now know it must be in R2C7 or R2C8.
Again, this should be clear. But now we get to the third type of Uniqueness, which I just started working on:
| Code: |
12|12AB...
12|12AB...
|
(where AB... is a string of 2 or more identical possibilities, such as 34,345, etc)
| Code: |
+----------------------+----------------------+----------------------+
| 478 1 9 | 78 3 5 | 26 26 47 |
| 3457 345 6 | 9 24 27 | 1 34 8 |
| 3478 2 378 | 1 46 68 | 379 349 5 |
+----------------------+----------------------+----------------------+
| 3589 35689 4 | 38 56 1 | 3589 7 2 |
| 27 358 1 | 4 9 27 | 358 358 6 |
| 235789 35689 2378 | 378 256 68 | 4 1 39 |
+----------------------+----------------------+----------------------+
| 1 7 23 | 5 8 4 | 2369 2369 39 |
| 2489 489 5 | 6 7 3 | 28 248 1 |
| 6 348 38 | 2 1 9 | 3578 3458 47 |
+----------------------+----------------------+----------------------+
|
Now, I've read the explanations on the forums about finding N-1 squares, etc., but it occurs to me that there is a simplification. Consider the above example, which I'll rotate to make it clearer:
Depending on which one of the 26's is 2 and which is 6, there are only 2 possible configurations for the puzzle:
| Code: |
2|369 or 6|239
6|239 2|369
|
However, we know that two possible solutions are invalid:
| Code: |
2|6 and 6|2
6|2 2|6
|
which lets us reduce a bit:
| Code: |
2|39 or 6|239
6|239 2|39
and also:
2|639 or 6|39
6|39 2|639
|
Question 1: AFAICT, this lets us say that either c or d must be 39.
But here is Question 2: Does it also let us say that the other square of the cd pair is 26? In other words, do we always get this set of possible solutions?
| Code: |
2|39 or 6|26
6|26 2|39
and also:
2|26 or 6|39
6|39 2|26
|
The reason I ask this is as follows:
If the answer to question 1 is yes, then I should be able use the fact that one of the two squares is 39 to find locked sets in the 2 groups that intersect squares c and d (the block and row or column). I may not know which of squares c and d is 39, but the fact that one of them is permits me to look for sets that contain 39 in their possibilities.
Note that in the examples in the other threads, it seems to be assumed that only simple locked sets will do, ie, if you have a unique rectangle that looks like this:
you need to find 2 other squares that are 345. What I'm thinking is that if you have a unique rectangle that looks like this:
you can go hunting for locked sets such as <34>,<35>,<45> = <345>!
Note also that if the answer to Question 2 is yes, you can not only use the same logic to look for locked sets containing <12>, but because we are able to state that "if c=12, then d=34, or vice-versa", then you can also safely hunt for hidden sets containing <12> and <34>.
If the answer to Question 2 is no, then: can we still safely hunt for hidden sets containing <34>? If so, then that is another avenue to reduction.
I am wondering if the above observations, if true, might embrace and extend some of the existiing uniqueness patterns, or at least make them easier to work with.
Comments? |
|
| Back to top |
|
 |
| Lummox JR
| | Joined: 07 Sep 2005 | | Posts: 202 | | : | |
Items |
|
| Posted: Sun Oct 16, 2005 10:21 pm Post subject: Re: Uniqueness - a possible simplification? |
|
|
| MadOverlord wrote: | Again, this should be clear. But now we get to the third type of Uniqueness, which I just started working on:
| Code: |
12|12AB...
12|12AB...
|
(where AB... is a string of 2 or more identical possibilities, such as 34,345, etc)
| Code: |
+----------------------+----------------------+----------------------+
| 478 1 9 | 78 3 5 | 26 26 47 |
| 3457 345 6 | 9 24 27 | 1 34 8 |
| 3478 2 378 | 1 46 68 | 379 349 5 |
+----------------------+----------------------+----------------------+
| 3589 35689 4 | 38 56 1 | 3589 7 2 |
| 27 358 1 | 4 9 27 | 358 358 6 |
| 235789 35689 2378 | 378 256 68 | 4 1 39 |
+----------------------+----------------------+----------------------+
| 1 7 23 | 5 8 4 | 2369 2369 39 |
| 2489 489 5 | 6 7 3 | 28 248 1 |
| 6 348 38 | 2 1 9 | 3578 3458 47 |
+----------------------+----------------------+----------------------+
|
Now, I've read the explanations on the forums about finding N-1 squares, etc., but it occurs to me that there is a simplification. Consider the above example, which I'll rotate to make it clearer:
Depending on which one of the 26's is 2 and which is 6, there are only 2 possible configurations for the puzzle:
| Code: |
2|369 or 6|239
6|239 2|369
|
However, we know that two possible solutions are invalid:
| Code: |
2|6 and 6|2
6|2 2|6
|
which lets us reduce a bit:
| Code: |
2|39 or 6|239
6|239 2|39
and also:
2|639 or 6|39
6|39 2|639
|
Question 1: AFAICT, this lets us say that either c or d must be 39. |
That's one way to look at it. Essentially it tells us that at least one of the cells must be either 3 or 9.
| Quote: | But here is Question 2: Does it also let us say that the other square of the cd pair is 26? In other words, do we always get this set of possible solutions?
| Code: |
2|39 or 6|26
6|26 2|39
and also:
2|26 or 6|39
6|39 2|26
|
|
This is true if and only if a subset exists. You should however, it occurs to me now, be able to test both the 26 and the 39 for subsets.
| Quote: | Note that in the examples in the other threads, it seems to be assumed that only simple locked sets will do, ie, if you have a unique rectangle that looks like this:
you need to find 2 other squares that are 345. |
34, 35, and 45 will also do. Any subset of 345 works.
| Quote: | What I'm thinking is that if you have a unique rectangle that looks like this:
you can go hunting for locked sets such as <34>,<35>,<45> = <345>! |
You make an excellent point here, which I had not previously considered but does make a difference, and should be considered part of the standard test. Since one of the cells is 34, you should be able to look for any naked subset which includes 34.
Actually it occurs to me there's a hidden form of this as well, which has never been explored. (Would it be uniqueness 3', or 3h? I'll have to think of a name.) Since 34 must appear in one of those two cells, any hidden subset of N-1 cells that includes candidates 3 and 4 can be used for eliminations.
I'm definitely going to have to augment my solver now. My search for the N-1 cells was quite limited previously, but these changes should make it much more versatile.
| Quote: | | If the answer to Question 2 is no, then: can we still safely hunt for hidden sets containing <34>? If so, then that is another avenue to reduction. |
Looks like you got to that thought before me. And yes.
| Quote: | | I am wondering if the above observations, if true, might embrace and extend some of the existiing uniqueness patterns, or at least make them easier to work with. |
Well, this'll be a lot harder to throw into my subset algorithm, but yes, this will definitely extend the pattern. In fact you've just illuminated the fact that uniqueness 3 actually comes in 4 different flavors (excluding the B format): Naked and hidden subsets of extra digits, and naked and hidden subsets of the original 2 candidates. To find this in my subset algorithm I believe I'll have to lie to it and tell it that cell c is 12 and cell d is 34, and any eliminations it finds will automatically be in other cells anyway. This will require only slight modifications.
You also should look into pattern 4, which comes up more often. PaulIQ164 found that if one of the candidates in a or b is constrained to the c and d cells in their common box/column/row, the other candidate can be eliminated from the c or d cells. The logic behind this sounds a little weird at first until you work it out. If ab=26 and c or d had to be a 2, for example, then if the other cell was a 6, you'd have the forbidden pattern. So whichever of the c or d cells is a 2, the other one cannot be a 6. Hence neither one of them can be a 6. |
|
| Back to top |
|
|
| MadOverlord
| | Joined: 01 Jun 2005 | | Posts: 80 | | : | | Location: Wilmington, NC, USA |
Items |
|
| Posted: Mon Oct 17, 2005 2:40 am Post subject: Re: Uniqueness - a possible simplification? |
|
|
| Lummox JR wrote: | | Quote: | But here is Question 2: Does it also let us say that the other square of the cd pair is 26? In other words, do we always get this set of possible solutions?
| Code: |
2|39 or 6|26
6|26 2|39
and also:
2|26 or 6|39
6|39 2|26
|
|
This is true if and only if a subset exists. You should however, it occurs to me now, be able to test both the 26 and the 39 for subsets.
|
Could you be more specific as to what you mean by a subset in this instance. Or more particularly, under what circumstances can we guarantee that one of the squares reduces to 39 [I think all the time] and under what circumstances does the other reduce to 26? |
|
| Back to top |
|
|
| MadOverlord
| | Joined: 01 Jun 2005 | | Posts: 80 | | : | | Location: Wilmington, NC, USA |
Items |
|
| Posted: Mon Oct 17, 2005 1:05 pm Post subject: |
|
|
Oh, and some other clarifications would be helpful to this poor programmer:
1) assuming a
12|12AB...
12}12AB...
pattern, does the naked set have to be the AB..., or can it be a superset.
ie: 12|12345 - does the naked set have to be 345 (possibly created by finding two other squares 34 and 45, not just 345 345) or can it be 3456?
2) Assuming supersets are OK, can the superset contain 1 or 2, the original possibilities. I'm thinking that it can't.
3) What about hidden sets? Can they be supersets? Can they contain the original possibilities? Can they be used to EXCLUDE the original possibilities in other squares?
Inquiring minds want to know. |
|
| Back to top |
|
|
| Lummox JR
| | Joined: 07 Sep 2005 | | Posts: 202 | | : | |
Items |
|
| Posted: Mon Oct 17, 2005 7:27 pm Post subject: |
|
|
| MadOverlord wrote: | | Could you be more specific as to what you mean by a subset in this instance. Or more particularly, under what circumstances can we guarantee that one of the squares reduces to 39 [I think all the time] and under what circumstances does the other reduce to 26? |
By "subsets" I mean any naked or hidden subset. I believe you can reduce one to 39 and one to 26 only if you can find a subset of size N involving one and only one of the c or d cells. As I mentioned the best way for my own solver to go about this will be to pretend one is 26 and the other is 39, and look for subsets.
I should add, however, that it is critical to find any other subsets that exist for c and d's common box and column/row before doing this test. Otherwise a naked pair elsewhere could end up totally eliminating the 26 from both cells. Therefore to properly implement uniqueness test 3 in Sudoku Susser, I believe you'd have to require all standard subset rules and uniqueness to be checked. That is, not X-Wing and swordfish, but all naked/hidden sets certainly. I'm not sure what the Susser means by "comprehensive" sets, but presumably it's just subsets taken out past pairs and triples.
| Quote: | Oh, and some other clarifications would be helpful to this poor programmer:
1) assuming a
12|12AB...
12}12AB...
pattern, does the naked set have to be the AB..., or can it be a superset.
ie: 12|12345 - does the naked set have to be 345 (possibly created by finding two other squares 34 and 45, not just 345 345) or can it be 3456? |
From what you said in your original post I agree a superset will work. My original definition of uniqueness 3 was far too limited. (It does have the advantage of being easier to test, though.)
| Quote: | | 2) Assuming supersets are OK, can the superset contain 1 or 2, the original possibilities. I'm thinking that it can't. |
Indeed it cannot. However, I now believe that 12 can be used for subset tests in the same way that 34 can; you just have to make absolutely sure that any other subsets have already been found in the common box and column/row.
| Quote: | | 3) What about hidden sets? Can they be supersets? Can they contain the original possibilities? Can they be used to EXCLUDE the original possibilities in other squares? |
Hidden sets may use either the extra possibilities or the originals, but not both. That is, if ab=12 and cd=1234, and another cell e=125 is in c and d's column, but no other cells in that column contain 12, you've just found a hidden pair. You can eliminate 5 from e, but you can't eliminate anything from c or d. The logic of all the uniqueness tests is that between c and d you can have only 1 or 2, or neither, but not both. If the only other viable position for 1 and 2 is a single cell, the other must be in c or d.
Likewise we know from the uniqueness tests that in the same case, 3 or 4 must occur in at least c or d; one could be 3 and the other 4, but we don't know that yet. If cell e=358 and f=145 and ef fall within cd's box, well we know 3 or 4 must occur somewhere in cd, so c and d act as a single cell in this subset test. You now have a hidden subset 345 where cd=1234, e=358, and f=145, eliminating 8 from e and 1 from f. From cd no eliminations can be made yet, but we know only one of those cells can be 34, so the other must be 12.
Since both of those cases are searching for N-1 cells with a certain set of values, you can just tell the subset solver that one is 12 and the other is 34, and have it search for sets appropriately; either it will find the set then or not. If none of those special N-1 subsets can be found, you can't rule out the possibility that neither c nor d is 1 or 2. I know this seems a little like putting the cart before the horse, but it's more like putting the chicken before the egg. If the N-1 cells exist, they constrain either cd to 12 and 34 in some order; those cells will be easiest to find by assuming that is already the case, and cannot be found if it is false. |
|
| Back to top |
|
|
| Lummox JR
| | Joined: 07 Sep 2005 | | Posts: 202 | | : | |
Items |
|
| Posted: Mon Oct 17, 2005 8:05 pm Post subject: |
|
|
You know, immediately I'm beginning to doubt my logic for two tests. Hidden subsets work for the 12, because at most only c or d can be 12. But for the 34, I don't think it can work because both cells could conceivably be 34. The only way you can find a hidden subset with the 34, then, is to also test if some subset exists with 12.
But on the other hand I don't think naked subsets with the 12 are to be trusted either. Since cd may not end up with 12 at all, this elimination is not possible. Naked subsets do work for 34, though, because at least one of the cd cells must be 3 or 4.
So to amend my answer to your question: No, hidden sets cannot be found in all cases. So test 3's four forms break down like so:
3.1) A naked N-subset exists with the extra candidates and N-1 other cells.
3.2) A hidden N-subset exists with the extra candidates and N-1 other cells, if and only if case 3.4 is also true.
3.3) A naked N-subset exists with the original candidates and N-1 other cells, if and only if case 3.1 is also true.
3.4) A hidden N-subset exists with the original candidates and N-1 other cells.
The 3.2 and 3.3 cases will be hard to test--more so because my subset solver ignores any sets that have no eliminations. I think to test that one I'll have to get another routine that will simply look for existing, already eliminated subsets, and specifically for particular digits.
[edit]
I further amend my reply. Uniqueness 3 is not limited to cases where the candidates in c and d are alike. You can still find naked subsets if c and d have disparate candidates, like 123 and 124. c and d together still behave as a single cell which must contain 3 or 4. If 35 and 45 coexist in their common house, you still have a naked subset 34,35,45 and you've proved one of the c or d cells must be 12. Similarly the hidden subset tests for 12 are not invalidated by this case either.
Gads, this is gonna be harder to implement than I thought. Sure you don't want to give uniqueness 3 a pass for now and move on to 4?  |
|
| Back to top |
|
|
| Lummox JR
| | Joined: 07 Sep 2005 | | Posts: 202 | | : | |
Items |
|
| Posted: Tue Oct 18, 2005 4:37 am Post subject: |
|
|
I've found an example of the partial naked subset form of uniqueness 3 with unlike candidates in cells c and d. Here's the original puzzle:
| Code: | . . 9|. . .|. . .
. . 5|. 6 .|. 4 7
. . 7|. 4 9|. 1 .
-----------------
. . .|6 . .|2 . 5
. . 1|. 3 .|. . 4
6 . .|. . .|. . .
-----------------
. . .|. . 2|. 7 3
9 . .|. 7 .|6 . .
. . .|1 . .|. . 8 |
You can take that puzzle to this point after applying uniqueness 1:
| Code: | +-------------+-------------+-------------+
| 124 146 9 | 27 8 17 | 3 5 26 |
| 128 18 5 | 23 6 13 | 9 4 7 |
| 23 36 7 | 5 4 9 | 8 1 26 |
+-------------+-------------+-------------+
| 78 9 34 | 6 1 47 | 2 38 5 |
| 5 2 1 | 9 3 8 | 7 6 4 |
| 6 78 34 | 47 2 5 | 1 38 9 |
+-------------+-------------+-------------+
| 14 14 6 | 8 9 2 | 5 7 3 |
| 9 5 8 | 34 7 34 | 6 2 1 |
| 37 37 2 | 1 5 6 | 4 9 8 |
+-------------+-------------+-------------+ |
Here the ab cells are (1,7)=14 and (2,7)=14. c is (1,1)=124 and d=(2,1)=146. The original candidates are 14, the extras 26. If you look in box 1 you'll see (1,3)=23 and (2,3)=36. By the logic of the uniqueness test, (1,1)=2 or (2,1)=6, or perhaps both. 26 forms a naked subset with 23 and 36, so the third cell of the subset must be either (1,1) or (2,1). 2 can be eliminated from (1,2), forming a garden-variety naked pair with 18 in (1,2) and (2,2) and therefore eliminating 1 from (1,1) and (2,1).
Another way to do this is to find the partial naked pair in row 1. With (9,1)=26, and either (1,1)=2 or (2,1)=6, you have the partial pair and you can eliminate 2 from (4,1).
Interestingly uniqueness 4 also leads to the same result, though this won't always necessarily be the case. Here we know that 4 must be in (1,1) or (2,1), so whichever cell is 4, the other cannot be 1. After eliminating 1 from those cells, there is now a hidden pair 18 in (1,2) and (2,2), and you can eliminate 2 from (1,2) that way. |
|
| Back to top |
|
|
| Lummox JR
| | Joined: 07 Sep 2005 | | Posts: 202 | | : | |
Items |
|
| Posted: Sat Oct 22, 2005 5:08 pm Post subject: |
|
|
In going over uniqueness 3 some more recently I learned I made some wrong assumptions in this thread. One of them is an important one.
Using as an example ab=12, c=123, d=124: If you run the house through a subset solver, you shouldn't pretend c=34 and d=12. Instead pretend c=34 and d=1234. This will correctly identify naked and hidden subsets; do not eliminate any candidates from d. (A subset solver will not recommend eliminations in c.)
The second thing I did wrong was to think that once you'd proved at least c or d was 12 by finding another subset, you could search for naked subsets including 12 or hidden subsets including 34. I'm convinced now that's not the case. If you found the original subsets, there'd be nothing left to eliminate. |
|
| Back to top |
|
|
| MadOverlord
| | Joined: 01 Jun 2005 | | Posts: 80 | | : | | Location: Wilmington, NC, USA |
Items |
|
| Posted: Sat Oct 22, 2005 9:47 pm Post subject: |
|
|
| Lummox JR wrote: | | In going over uniqueness 3 some more recently I learned I made some wrong assumptions in this thread. One of them is an important one. |
Lummox, can you please give explicit examples of what you mean?
Which square is a, b, etc? It's confusing -- different posts have different conventions.
Do you mean:
a|c
b|d
or
a|b
c|d
I was under the impression that you should always treat the two squares with extra possibilities as a single square; I think of it as the "quantum" square.
So, in
12|1234
12|1234
the quantum square value is 34.
It might be better to keep all the discussion in a single thread for a while, such as the standardizing thread over on sudoku players, until we've got it nailed down. |
|
| Back to top |
|
|
| Lummox JR
| | Joined: 07 Sep 2005 | | Posts: 202 | | : | |
Items |
|
| Posted: Sun Oct 23, 2005 3:05 am Post subject: |
|
|
| MadOverlord wrote: | Lummox, can you please give explicit examples of what you mean?
Which square is a, b, etc? It's confusing -- different posts have different conventions.
Do you mean:
a|c
b|d
or
a|b
c|d |
I mean both, actually. The former is the A form and the latter the B form. The a and b cells are always the one with the original naked pair, and c and d have the potential for extra candidates depending on the test. In my posts I've stuck to this terminology.
| Quote: | | I was under the impression that you should always treat the two squares with extra possibilities as a single square; I think of it as the "quantum" square. |
Yes, that's valid in all tests but form 1. (In that case, treating the two cells differently is a good thing.) And as we've observed, some tests still work when c and d have different candidates.
| Quote: | So, in
12|1234
12|1234
the quantum square value is 34. |
Likewise if c=123 and d=124, it's still 34.
| Quote: | | It might be better to keep all the discussion in a single thread for a while, such as the standardizing thread over on sudoku players, until we've got it nailed down. |
Works for me. |
|
| Back to top |
|
|
| MadOverlord
| | Joined: 01 Jun 2005 | | Posts: 80 | | : | | Location: Wilmington, NC, USA |
Items |
|
| Posted: Sun Oct 23, 2005 1:52 pm Post subject: |
|
|
| Lummox JR wrote: | | Quote: | | It might be better to keep all the discussion in a single thread for a while, such as the standardizing thread over on sudoku players, until we've got it nailed down. |
Works for me. |
May I suggest the standardizing thread over in Sudoku Players? A larger audience, and it will let me edit the first message to reflect what is agreed upon. I'll take a stab at that Sunday |
|
| Back to top |
|
|
| gaby
| | Joined: 02 Jul 2005 | | Posts: 120 | | : | |
Items |
|
| Posted: Mon Oct 31, 2005 10:12 am Post subject: |
|
|
Does anybody have any puzzles that can be progressed/solved using the uniqueness test? I'm looking for some puzzles to test my implementation against.
Gaby
_________________
Free daily sudoku - Online puzzle database
http://vanhegan.net/sudoku/ |
|
| Back to top |
|
|
| MadOverlord
| | Joined: 01 Jun 2005 | | Posts: 80 | | : | | Location: Wilmington, NC, USA |
Items |
|
|
| Back to top |
|
|
| Bob Hanson
| | Joined: 05 Oct 2005 | | Posts: 187 | | : | | Location: St. Olaf College |
Items |
|
| Posted: Fri Nov 04, 2005 12:21 am Post subject: |
|
|
I'm just attaching here what I said on a different thread:
I do not believe that
| Code: |
12|12AB...
12|12AB...
|
can arise in any actual solution to any actual real unique Sudoku.
Reason: Simple hypothesis and proof, which is NOT FALLABLE since it relies on perfectly straight logic, would force all the AB to be eliminated, leading to a nonunique puzzle solution. Or, if you prefer, simple bifurcation leads to the same conclusion:
bottom left is either 1 or 2.
If it is 1, then the bottom right is 2 (because there are only 2 2s in this row).
If it is 2, then the bottom right is 1 (because there are only 2 1s in this row).
In neither case can A or B arise.
Therefore A and B can be eliminated.
Therefore the puzzle is not unique.
Therefore, since the premise is that the puzzle IS unique, this situation in a partial solution to a valid unique Sudoku cannot arise.
Right?
_________________
Bob Hanson
Professor of Chemistry
St. Olaf College
Northfield, MN
http://www.stolaf.edu/people/hansonr |
|
| Back to top |
|
|
| Lummox JR
| | Joined: 07 Sep 2005 | | Posts: 202 | | : | |
Items |
|
| Posted: Fri Nov 04, 2005 4:35 am Post subject: |
|
|
| Bob Hanson wrote: | bottom left is either 1 or 2.
If it is 1, then the bottom right is 2 (because there are only 2 2s in this row).
If it is 2, then the bottom right is 1 (because there are only 2 1s in this row).
In neither case can A or B arise.
Therefore A and B can be eliminated.
Therefore the puzzle is not unique.
Therefore, since the premise is that the puzzle IS unique, this situation in a partial solution to a valid unique Sudoku cannot arise.
Right? |
Nope. You're overlooking the fact that other cells exist that aren't part of the pattern, and are merely not being shown in our examples. It is not the case that those are the only cells in each row with 12 as candidates. Those would be simple hidden pairs. Rather, we're just not interested in showing those other cells in each row which have 12 as candidates because they have no bearing on the test.
Likewise, it is not the case that the 12AB cells are the only cells in that column with 12. If they're the only ones with either 1 or 2 (it can't be both), though, you have the uniqueness 4 test. |
|
| 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
