|
View previous topic :: View next topic |
Author |
Message |
| gnatzkopp
| Joined: 01 May 2005 | Posts: 3 | : | Location: Rostock, Germany | Items |
|
Posted: Sun May 01, 2005 9:26 am Post subject: Patterns involving various numbers and organisation units |
|
|
I have noticed various discussions about whether or not puzzles are solvable using pure forward logic or may require T&E - whatever the exact definitions are.
I'm a strong believer that all SuDoku puzzles with exactly one solution can be solved without T&E, it is just a question of the right techniques and patterns to apply.
So far, all patterns I know of - starting with the simple elimination rules up to X-Wing and Swordfish, also including the coloring technique - have one limitation in common: they either deal with a fixed number and consider various organisation units (didn't know a better term, but I mean rows, columns, boxes) OR they deal with a fixed unit and consider various numbers. Sometimes dependencies are a bit more complex.
Is there any pattern described yet that includes more than one number in more than one unit?
It might be helpful in a particular puzzle I am looking at. This was published in the Telegraph as no.56, dated Apr, 23 and looks like this
5**|12*|**7
*3*|***|24*
*1*|*76|**3
---+---+---
***|**5|**2
**7|***|9**
1**|2**|***
---+---+---
6**|91*|*3*
*45|***|*1*
9**|*54|**6
Standard deductions bring us to
5 89 4 1 2 3 6 89 7
7 3 6 5 89 89 2 4 1
28 1 289 4 7 6 5 89 3
48 689 3 678 4689 5 1 67 2
248 2568 7 68 3 1 9 56 48
1 5689 89 2 4689 789 3 567 48
6 278 28 9 1 78 4 3 5
3 4 5 678 68 2 78 1 9
9 78 1 3 5 4 78 2 6
With T&E we can see that putting 8 into r1c2 had the following implications
i) r3c3 must be 9 because it is the only place left for 9 in the upper left hand box
ii) r7c3 must be 8 because it is the only place left for 8 in the bottom left hand box
These two don't leave any possible for r6c3 and the original assumption is wrong.
While I think this is not too difficult to spot I really struggle with a generic description of that pattern.
Is there any help out there? |
|
Back to top |
|
|
| Tempbow
| Joined: 18 Apr 2005 | Posts: 22 | : | | Items |
|
Posted: Sun May 01, 2005 9:53 pm Post subject: Re: Patterns involving various numbers and organisation unit |
|
|
gnatzkopp wrote: |
<snip>
Code: | **|12*|**7
*3*|***|24*
*1*|*76|**3
---+---+---
***|**5|**2
**7|***|9**
1**|2**|***
---+---+---
6**|91*|*3*
*45|***|*1*
9**|*54|**6 |
Standard deductions bring us to
Code: | 5 89 4 1 2 3 6 89 7
7 3 6 5 89 89 2 4 1
28 1 289 4 7 6 5 89 3
48 689 3 678 4689 5 1 67 2
248 2568 7 68 3 1 9 56 48
1 5689 89 2 4689 789 3 567 48
6 278 28 9 1 78 4 3 5
3 4 5 678 68 2 78 1 9
9 78 1 3 5 4 78 2 6 |
Is there any help out there? |
This is not a solution to answer your question.
But I would like to show various representations of the solution state of the puzzle.
Firstly, show the state matrix for each of the nine possibles:
1 - 5
Code: | +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
|...|*..|...| |...|.*.|...| |...|..*|...| |..*|...|...| |*..|...|...|
|...|...|..*| |...|...|*..| |.*.|...|...| |...|...|.*.| |...|*..|...|
|.*.|...|...| |2.2|...|...| |...|...|..*| |...|*..|...| |...|...|*..|
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
|...|...|*..| |...|...|..*| |..*|...|...| |4..|.4.|...| |...|..*|...|
|...|..*|...| |22.|...|...| |...|.*.|...| |4..|...|..4| |.5.|...|.5.|
|*..|...|...| |...|*..|...| |...|...|*..| |...|.4.|..4| |.5.|...|.5.|
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
|...|.*.|...| |.22|...|...| |...|...|.*.| |...|...|*..| |...|...|..*|
|...|...|.*.| |...|..*|...| |*..|...|...| |.*.|...|...| |..*|...|...|
|..*|...|...| |...|...|.*.| |...|*..|...| |...|..*|...| |...|.*.|...|
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |
6 - 9
Code: | +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
|...|...|*..| |...|...|..*| |.8.|...|.8.| |.9.|...|.9.|
|..*|...|...| |*..|...|...| |...|.88|...| |...|.99|...|
|...|..*|...| |...|.*.|...| |8.8|...|.8.| |..9|...|.9.|
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
|.6.|66.|.6.| |...|7..|.7.| |88.|88.|...| |.9.|.9.|...|
|.6.|6..|.6.| |..*|...|...| |88.|8..|..8| |...|...|*..|
|.6.|.6.|.6.| |...|..7|.7.| |.88|.88|..8| |.99|.99|...|
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
|*..|...|...| |.7.|..7|...| |.88|..8|...| |...|*..|...|
|...|66.|...| |...|7..|7..| |...|88.|8..| |...|...|..*|
|...|...|..*| |.7.|...|7..| |.8.|...|8..| |*..|...|...|
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ |
These detectable swordfish have already been applied:
rows: found row 3 columns 13 row 5 columns 12 row 7 columns 23 for poss 2
rows: found row 4 columns 15 row 5 columns 19 row 6 columns 59 for poss 4
columns: found column 1 rows 35 column 2 rows 57 column 3 rows 37 for poss 2
columns: found column 1 row 45 column 5 row 46 column 9 row 56 for poss 4
Also, this represents the column numbers for each possible by row:
Code: | ROWS poss 1 - 9
1 2 3 4 5 6 7 8 9 <= possible
4 5 6 3 1 7 9 28 28
9 7 2 8 4 3 1 56 56
2 13 9 4 7 6 5 138 38
7 9 3 15 6 2458 48 1245 25
6 12 5 19 28 248 3 1249 7
1 4 7 59 28 258 68 23569 2356
5 23 8 7 9 1 26 236 4
8 6 1 2 3 45 47 457 9
3 8 4 6 5 9 27 27 1 |
This represents the row numbers for each possible by column:
Code: | COLUMNS poss 1 - 9
1 2 3 4 5 6 7 8 9 <= possible
6 35 8 45 1 7 2 345 9
3 57 2 8 56 456 79 145679 146
9 37 4 1 8 2 5 367 36
1 6 9 3 2 458 48 458 7
7 1 5 46 9 468 3 2468 246
5 8 1 9 4 3 67 267 26
4 2 6 7 3 1 89 89 5
8 9 7 2 56 456 46 13 13
2 4 3 56 7 9 1 56 8 |
Pattern recognition may be more readily applied to other representations than the standard "pencilled possibles" array - hence this response.
Terry |
|
Back to top |
|
|
| IJ
| Joined: 15 Apr 2005 | Posts: 16 | : | | Items |
|
Posted: Mon May 02, 2005 12:50 am Post subject: |
|
|
I have a rule. It's an absolute killer, and I've used it to solve a couple of "unsolvable" DT diabolicals now, including the one above.
However, I'm going to sleep on it and post it in the morning (too many embarrassing late night posts in the past ) |
|
Back to top |
|
|
| gnatzkopp
| Joined: 01 May 2005 | Posts: 3 | : | Location: Rostock, Germany | Items |
|
Posted: Mon May 02, 2005 12:55 pm Post subject: |
|
|
Can hardly wait to see it. |
|
Back to top |
|
|
| rubylips
| Joined: 07 Apr 2005 | Posts: 62 | : | Location: London | Items |
|
Posted: Tue May 03, 2005 11:52 pm Post subject: |
|
|
The following thoughts crossed my mind after I'd considered the puzzle posted by gnatzkopp. Normally I don't comment until I've written code but that will have to wait for a couple of days.
First, introduce the following notation, based upon the Kronecker delta:
dij(n) = 1 if the cell (i,j) contains the value n, 0 otherwise
The standard Sudoku puzzle gives us 81 delta variables for each value and 27 constraints (9 for each row, column or box). Of course, we know further that each delta variable must equal 0 or 1 but these constraints aren't so easily written in matrix form.
Now consider the posted puzzle. We have:
d12(9)+d33(9)=1
d33(9)+d63(9)=1
which combine to give:
d12(9)=d63(9)
(In Swordfish-speak, we'd say that we had a 2-leg string in the 9s).
Critically, the fact that the cells (1,2) and (6,3) share the same two candidate values - 8 and 9 - gives us:
d12(8)+d12(9)=1
d63(8)+d63(9)=1
which combine with the earlier results to give:
d12(8)=d63(8)
We now perform a traditional analysis of the 8s in Columns 2 and 3 and Box 7 but with the benefit of an additional constrained supplied from the 9s. A key point is that previously this would have been a Nishio analysis, which is generally considered T&E, however - the delta notation allows the problem to be expressed without recourse reductio ad absurdum, which (I believe - though I'm not yet 100% certain) legitimizes the procedure.
The four equations are:
d72(8)+d73(8)+d92(8)=1 [Box 7]
d12(8)+d42(8)+d52(8)+d62(8)+d72(8)+d92(8)=1 [Column 2]
d33(8)+d63(8)+d73(8)=1 [Column 3]
d12(8)=d63(8) [9s]
d72(8)+d92(8) cancels from the first two equations to give:
d12(8)+d42(8)+d52(8)+d62(8)=d73(8)
d73(8) in the above cancels within the third equation to give:
d12(8)+d33(8)+d42(8)+d52(8)+d62(8)+d63(8)=1
Substitute in the fourth equation in order to obtain:
2*d12(8)+d33(8)+d42(8)+d52(8)+d62(8)=1
Now it's clear that d12(8) must be zero, otherwise the factor of two would make it impossible for the LHS to sum to one. We are in a position to report something like the standard Nishio message 'The move (1,2):=8 would make it impossible to place the remaining 8s.' - however, we haven't made a prior assumption about the value of a given delta variable and, because there has been no assumption, the analysis will have been much faster.
I think there might be two useful ideas in this analysis:
i. It's possible to shift a constraint in one value (the 9s) to another (the 8s) if cells share candidate values.
ii. Delta notation makes it straightforward to spot illegal values without recourse to reductio ad absurdum. It's possible that this will legitimize (and vastly accelerate) Nishio analysis.
Code will follow later this week. |
|
Back to top |
|
|
| Tempbow
| Joined: 18 Apr 2005 | Posts: 22 | : | | Items |
|
Posted: Wed May 04, 2005 7:29 am Post subject: |
|
|
Let me see if I have understood the basics first, before going into the equations and the strategy.
rubylips wrote: | d12(9)=d63(9)
(In Swordfish-speak, we'd say that we had a 2-leg string in the 9s). |
That's saying "if there is a 9 in 1,2 then there must be a 9 in 6,3. Conversely, if there is not a 9 in 1,2 then there is not a 9 in 6,3."
Quote: | Critically, the fact that the cells (1,2) and (6,3) share the same two candidate values - 8 and 9 - gives us:
d12(8)+d12(9)=1
d63(8)+d63(9)=1
which combine with the earlier results to give:
d12(8)=d63(8) |
That's saying "because the only possible candidates in 1,2 and 6,3 are 8 & 9, then the same applies for 8. If one contains an 8, both contain an 8, and if one does not contain an 8, neither contains an 8."
Quote: |
<snip>
I think there might be two useful ideas in this analysis:
i. It's possible to shift a constraint in one value (the 9s) to another (the 8s) if cells share candidate values. |
Have I correctly restated the basic initial premise?
Next I would like to question the selection of the columns 2 and 3 and box 7. How are they selected?
Terry |
|
Back to top |
|
|
| rubylips
| Joined: 07 Apr 2005 | Posts: 62 | : | Location: London | Items |
|
Posted: Wed May 04, 2005 9:42 am Post subject: |
|
|
Quote: | That's saying "if there is a 9 in 1,2 then there must be a 9 in 6,3. Conversely, if there is not a 9 in 1,2 then there is not a 9 in 6,3." |
Exactly
Quote: | That's saying "because the only possible candidates in 1,2 and 6,3 are 8 & 9, then the same applies for 8. If one contains an 8, both contain an 8, and if one does not contain an 8, neither contains an 8." |
Exactly
Quote: | Next I would like to question the selection of the columns 2 and 3 and box 7. How are they selected? |
In general, it would be necessary to consider all 27 constraints. However, in order to illustrate the general principle, I've simply selected the smallest necessary subset of constraints. |
|
Back to top |
|
|
| Animator
| Joined: 26 Apr 2005 | Posts: 18 | : | | Items |
|
Posted: Wed May 04, 2005 9:51 am Post subject: |
|
|
This post is an explanation of rubylips analysis... it took me some time to figure it out, so I post it just to safe others from going to the trouble of figuring it out thereselfs.
First we start with the first two equations (Box 7 and Column 2): obviously the result of Box 7 should be the same as Column 2 (as in, both should have the number 8, meaning a value of 1):
So we write:
d72(8)+d73(8)+d92(8)= d12(8)+d42(8)+d52(8)+d62(8)+d72(8)+d92(8)
Now you see that both d72(8) and d92(8) occur on both side of the equation, which basiclly means we can remove them.
Or to say it in rubylips's words:
rubylips wrote: |
d72(8)+d92(8) cancels from the first two equations to give:
d12(8)+d42(8)+d52(8)+d62(8)=d73(8)
|
Now we found another way to write d73(8), so in order to use it we write it down in the thrid equation (the equation of Column 3), resulting in:
d33(8)+d63(8)+ ( d12(8)+d42(8)+d52(8)+d62(8) )=1
From the fourth equation we know that d12(8)=d63(8). This means that in all previous equations we can replace d63(8) with d12(8) (or vice-versa), so let's do it to the last one:
d33(8)+d12(8)+ ( d12(8)+d42(8)+d52(8)+d62(8) )=1
Now we see that it has d12(8) twice, which means that it is impossible that d12(8) is 1... (as in, if it would be 1 then the result of the last equation would be 2, which is invalid)
This new knowledge gives us the result of the previous equations:
rubylips wrote: |
d12(8)+d12(9)=1
d63(8)+d63(9)=1
|
==> we just said that r1c2 can't be 8, so r1c2 must be 9...
(update, typo)
Last edited by Animator on Thu May 05, 2005 11:03 am; edited 2 times in total |
|
Back to top |
|
|
| rubylips
| Joined: 07 Apr 2005 | Posts: 62 | : | Location: London | Items |
|
Posted: Wed May 04, 2005 11:01 pm Post subject: |
|
|
Thanks for the follow-up posts to clarify - my original should have been more expansive. |
|
Back to top |
|
|
| gnatzkopp
| Joined: 01 May 2005 | Posts: 3 | : | Location: Rostock, Germany | Items |
|
Posted: Thu May 05, 2005 12:16 pm Post subject: |
|
|
rubylips wrote: |
I think there might be two useful ideas in this analysis:
i. It's possible to shift a constraint in one value (the 9s) to another (the 8s) if cells share candidate values.
ii. Delta notation makes it straightforward to spot illegal values without recourse to reductio ad absurdum. It's possible that this will legitimize (and vastly accelerate) Nishio analysis.
Code will follow later this week. |
Conclusion i. is very nice, it allows for example to amend the coloring technique. Unfortunately in the particular puzzle it doesn't get us much further.
I'm a bit doubtful regarding ii. when it comes to programming. Your reasoning is clear and straightforward, but it still has the 'human factor' when you combine the equations to eliminate terms. When we look at the equations we see what they tell us, but making an algorithm out of this is a different thing.
I'm looking forward to see your ideas about coding. |
|
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
|