Patterns involving various numbers and organisation units

gnatzkopp

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?

Tempbow

IJ · 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 Very Happy

)

gnatzkopp · Posted: Mon May 02, 2005 12:55 pm Post subject:

Can hardly wait to see it. Very Happy

rubylips · 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.

Tempbow · 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 · Posted: Wed May 04, 2005 9:42 am Post subject:

Animator · 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 · 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.

gnatzkopp · Posted: Thu May 05, 2005 12:16 pm Post subject: