The New Sudoku Players' Forum

[Smythe Dakota]

.... Which techniques do you use when surface sums are not available or don't allow you to go very far? .... Did you try e.g. the April 14 puzzle? If so, did you find it difficult?

That was a week ago, so I don't remember anymore. On looking at my completed April 14 puzzle, I don't see any cross-outs or any particular evidence that I had any trouble with it.

So I'm going to try a real-time experiment. I just printed out another copy of that puzzle, and as I solve each digit (or small group of digits), I'll list what I did below.

• The lower right corner, r9c9, must be at least 5 because of the 14, and at most 5 because of the 6. So it's 5. That imediately solves the four cells in that corner.
• Where a 2-digit 16 intersects a 2-digit 17, that cell must be 9. That immediately solves the upper left corner.
• Any 3-digit 22 must include a 9. So one of r7c6, r8c6, r9c6 must be 9. It can't be r8c6 because we already have a 9 in that row. It can't be r9c6 because that would put 5 in r9c5, which is impossible because the 4-digit 30 in c5 must consist of 6-7-8-9. So r7c6 is 9.
• r1c4 is at most 5 because of the 8, and r1c5 is at most 4 because of the 10. These maximum values must be the actual values, in order to reach the sum of 9.
• The remaining two cells in that 3-digit 8 must be 1 and 2. Since we already have 2 in r2, we know which is which.
• r2c5 must be one of 1-2-3-4, and 3 is the only one left.
• Likewise, the rest of the 10 in c5 falls into place immediately.
• r9c3 must be either 1 or 3, but 3 would give us a duplicate 4 in r8, so r9c3 must be 1. That also gives us r8c3 and r9c2.
• The 34 in c1 must consist of 9-8-7-6-4. The only one that can still be 4 is r5c1.
• The 33 in c9 must be either 9-8-7-6-3 or 9-8-7-5-4. So r3c9 must be either 3 or 4. That makes r3c8 either 1 or 2. But it can't be 1 because the three missing digits in the 37 in c8 must add up to 8 (45 minus 37), one of which must be 1. So r3c8 and r3c9 must be 2 and 3 respectively.
• r2c7 must be 4 or 5 (we already have 1,2,3 in that row). So r1c7 must be 1 or 2. 1 is impossible since it would force an illegal two-digit number into r1c8. So r1c7 is 2, and that also solves r1c8 and r2c7.
• The two remaining digits in the 19 in r3 must be 7 and 9. But 9 can't go into r3c6, because that would force r2c6 to be 4 or less, which is impossible since we already have all the 4-or-less digits in r2. So r3c3 is 9 and r3c6 is 7.
• r2c6 and r4c6 now fill in easily as 6 and 1 respectively.
• The only place left in r2 for a 9 is r2c9.

I'll leave it at that for now. As you can see, my solving techniques are strictly ad hoc. That's why Kakuro is still interesting for me.

Bill Smythe

[denis_berthier]

.... Which techniques do you use when surface sums are not available or don't allow you to go very far? .... Did you try e.g. the April 14 puzzle? If so, did you find it difficult?

That was a week ago, so I don't remember anymore. On looking at my completed April 14 puzzle, I don't see any cross-outs or any particular evidence that I had any trouble with it.

That's why I chose it. Although it is rated D by Mepham (the highest level there), it is an easy one (W2 in my rating system).

BTW, do you have any idea how the Mepham puzzles are rated G, M, T, D ?

• The lower right corner, r9c9, must be at least 5 because of the 14, and at most 5 because of the 6. So it's 5. That imediately solves the four cells in that corner.
• Where a 2-digit 16 intersects a 2-digit 17, that cell must be 9. That immediately solves the upper left corner.
• Any 3-digit 22 must include a 9. So one of r7c6, r8c6, r9c6 must be 9. It can't be r8c6 because we already have a 9 in that row. It can't be r9c6 because that would put 5 in r9c5, which is impossible because the 4-digit 30 in c5 must consist of 6-7-8-9. So r7c6 is 9.
• r1c4 is at most 5 because of the 8, and r1c5 is at most 4 because of the 10. These maximum values must be the actual values, in order to reach the sum of 9.
• The remaining two cells in that 3-digit 8 must be 1 and 2. Since we already have 2 in r2, we know which is which.
• r2c5 must be one of 1-2-3-4, and 3 is the only one left.
• Likewise, the rest of the 10 in c5 falls into place immediately.

[...]
I'll leave it at that for now.

OK, I don't need more. Thanks for your answer.

As you can see, my solving techniques are strictly ad hoc.

That's where our opinions diverge. For me, there's nothing ad hoc here. Each of the steps you describe is the result of applying a very small number of very elementary techniques: checking the possible combinations of sectors, propagating this to possible values of digits in the white cells, propagating back to combinations in sectors, and so on.
You can use shortcuts for specific configurations you come to know after some time of playing (e.g. "Where a 2-digit 16 intersects a 2-digit 17, that cell must be 9"), but even these are the result of the same basic rules.

If you ever try harder puzzles than the commercial ones proposed by Mepham, you'll be surprised to see how powerful such rules are.
This is also why I encouraged Saul to proceed with his project of developing a software for automatically keeping track of the remaining combinations and for displaying them on demand. That'd be a great help, as it would alleviate the boring burden of all this paper scratching work and allow one to concentrate on the most interesting parts.

[Smythe Dakota]

.... OK, I don't need more. Thanks for your answer. ....

Aw, darn. You're spoiling my fun. So I'll continue, at least for a bit.

Besides, this is just the point at which things were getting interesting.

• There must be a 9 in one of r4c1,r4c2, and also in one of r5c1,r5c2. That uses up all the possible 9's in columns 1 and 2. Thus, for example, r7c1,r7c2 cannot be 9-5, so they must be 8-6 (in some order).
• We now have three cells in c2 all of which must be at least 6. And one of them must be 9. That makes 9-7-6, or 22, the minimum possible sum for these three. Combined with the 3 at the bottom, that adds up to 25, making 5 the maximum possible sum for the remaining cells, r6c2,r8c2. Thus each must be 4 or less. But 3 and 4 are both unavailable for these cells, so they must be 1 and 2 (in some order).
• This forces r6c2,r8c2,r9c2 to add up to 6. So the three remaing cells in c2 must add up to 24, i.e. they must be 9-8-7. No 6. Thus r7c2 must be 8.
• This allows the rest of c1 and c2 to fall into place, except for r6c2,r8c2, which must be 1-2 (in some order).

I'll stop there for now. The above sequence is probably why Mepham gave it a D rating. (Or, maybe I missed a simpler approach somewhere.)

.... BTW, do you have any idea how the Mepham puzzles are rated G, M, T, D ? ....

No idea. I think you said M and D probably stand for Moderate and Diabolical. Maybe G and T are Gentle and Tough? In any case, the sequence G, M, T, D is obviously the correct order difficulty-wise, since these puzzles occur respectively on Mon-Tue, Wed-Thu, Fri-Sat, Sun. (Sometimes that's the only way I can tell which are which.)

Bill Smythe

[denis_berthier]

.... OK, I don't need more. Thanks for your answer. ....

Aw, darn. You're spoiling my fun. So I'll continue, at least for a bit.
Besides, this is just the point at which things were getting interesting.

• There must be a 9 in one of r4c1,r4c2, and also in one of r5c1,r5c2. That uses up all the possible 9's in columns 1 and 2. Thus, for example, r7c1,r7c2 cannot be 9-5, so they must be 8-6 (in some order).
• We now have three cells in c2 all of which must be at least 6. And one of them must be 9. That makes 9-7-6, or 22, the minimum possible sum for these three. Combined with the 3 at the bottom, that adds up to 25, making 5 the maximum possible sum for the remaining cells, r6c2,r8c2. Thus each must be 4 or less. But 3 and 4 are both unavailable for these cells, so they must be 1 and 2 (in some order).
• This forces r6c2,r8c2,r9c2 to add up to 6. So the three remaing cells in c2 must add up to 24, i.e. they must be 9-8-7. No 6. Thus r7c2 must be 8.
• This allows the rest of c1 and c2 to fall into place, except for r6c2,r8c2, which must be 1-2 (in some order).

I'll stop there for now.

OK, this is the same kind of reasoning as before and therefore the same remarks apply.

The above sequence is probably why Mepham gave it a D rating. (Or, maybe I missed a simpler approach somewhere.)

I have a solution using only combinations - no sums are ever computed. I don't know if you'd consider it simpler.

.... BTW, do you have any idea how the Mepham puzzles are rated G, M, T, D ? ....

No idea. I think you said M and D probably stand for Moderate and Diabolical. Maybe G and T are Gentle and Tough?

D is more prosaic: "Difficult".
In my approach, there's no clear difference between G, T and D.

[Smythe Dakota]

.... OK, this is the same kind of reasoning as before and therefore the same remarks apply. ....

Not quite. This is the first time in this puzzle I'd said "there must be a 9 here or here, and also there or there, so there can't be a 9 anywhere else in these two columns".

I have often found it useful, in examining a small chunk of the puzzle, to ask "how many 9's" (or 1's, or any other digit, but 1's and 9's are most common) "must/can there be here?" and then look at both rows and columns. If there are four rows, at least three of which need a 9, and just three columns, then you know that fourth row can't contain a 9. (Slightly more complicated versions of this idea come up from time to time, too.)

.... In my approach, there's no clear difference between G, T and D.

Nor in mine. Some D puzzles are easier than some G puzzles.

Bill Smythe

[denis_berthier]

.... OK, this is the same kind of reasoning as before and therefore the same remarks apply. ....

Not quite. This is the first time in this puzzle I'd said "there must be a 9 here or here, and also there or there, so there can't be a 9 anywhere else in these two columns".

Yes, I had overlooked it. In Sudoku, it'd be called an X-Wing (the easiest of the classical Fish patterns: Swordfish if 3 rows and columns, Quad if 4, ...). There's one also in my solution.
Of course, no one needs to know the name to apply it. AFAIK, no one knows when this pattern was first reported; it has probably been spontaneously found by lots of people. Similarly, you use it naturally in Kakuro.

[denis_berthier]

I've modified my KakuRules solver in such a way that I can now choose if the first (black) row/column is 0 or 1. That'll make it easier to use the same notation as you when we talk of some puzzle.
With these modifications, using your notation for rows/columns, the non-completely-trivial part of my solution looks like:

Code: Select all

naked-pairs-in-a-row: r8{c1 c5}{n7 n8} ==> r8c7 <> 8, r8c7 <> 7, r8c6 <> 8, r8c6 <> 7
naked-singles ==> r8c6 = 5, vr6c6 = 589
cell-to-verti-ctr  ==> vr3c7 <> 45678
horiz-sector-to-ctr  ==> hr9c4 <> 59
naked-singles ==> hr9c4 = 68, r9c6 = 8, r9c5 = 6, r7c6 = 9
hidden-single-in-magic-verti-sector ==> r6c5 = 9
naked-pairs-in-a-row: r8{c1 c5}{n7 n8} ==> r8c4 <> 8, r8c4 <> 7, r8c2 <> 8, r8c2 <> 7
whip[2]: r3c6{n7 n9} - vr1c6{n347 .} ==> r2c6 <> 7
cell-to-verti-ctr  ==> vr1c6 <> 347
ctr-to-verti-sector  ==> r4c6 <> 3
biv-chain[2]: r3c6{n7 n9} - r2c6{n9 n6} ==> vr1c6 <> 149

[Smythe Dakota]

.... In Sudoku, it'd be called an X-Wing ....

Well, how about that? I finally used an Advanced Solving Technique !!

.... I have a solution using only combinations - no sums are ever computed. I don't know if you'd consider it simpler. ....

It seems to me that, in order to solve Kakuro without any arithmetic whatsoever, your solver must have a huge number of small 3-dimensional tables built in. These tables (or perhaps an algorithm) would provide an immediate answer to any question of the form "what are all the ways of making N digits add up to A without using any of X,Y,Z?" (N is one dimension, A is another, and X,Y,Z is the third. Come to think of it, that last one is really more than one dimension, isn't it?)

For example, if you have a 5-digit word adding up to 30, and two of the digits are known to be 8 and 3, you would ask "how many ways can 3 digits add up to 19 without using 8 or 3?" In this case, the answer is "There is only one way: 9-6-4."

Such a set of tables, or such an algorithm, will necessarily need to have advance-solved all arithmetic that has ever occurred in any Kakuro puzzle that has ever been made, or could be made in the future. For the person using your program, Kakuro has been reduced to Sudoku. The fun part is gone, but the boredom and tedium remain.

Some of the above relates to the April 14 puzzle. Fast-forward to the final steps, which for me consisted of the 3x3 rectangle at r4c7-r6c9. By this time I had established that the bottom two digits in c7 were 8 and 3, so I asked the exact question I used in the example above. The rest of c7 had to be 9-6-4 (in some order). It was also easy to establish that c8 had to be 8-6-5, and c9 had to be 8-7-6. Now the 4 in c7 couldn't be at r4c7 or r5c7, because either of these would force a 9 into c8 or c9, where there already was a 9. That logic places a 4 in r6c7. Etc etc etc.

By the way, which kind of fish, reptile, or bird is that? Did I use another Advanced Solving Technique?

I've modified my KakuRules solver in such a way that I can now choose if the first (black) row/column is 0 or 1. That'll make it easier to use the same notation as you when we talk of some puzzle. ....

I'm glad you did that. To me, the top and left (black) rows aren't really there, anyway. They're just convenient places to put the sums. They could equally well be placed at the right and/or bottom edges. In fact, I think there's a Kakuro site somewhere that puts them at both the left and right, and both the top and bottom. But to me, the Mepham puzzles are 9x9, not 10x10 (let alone 11x11).

I have no problem counting from 0 rather than 1. I was a C programmer in an earlier life. "How many fingers does a C programmer have?" "Nine: 0,1,2,3,4,5,6,7,8,9."

Bill Smythe

[denis_berthier]

I have a solution using only combinations - no sums are ever computed. I don't know if you'd consider it simpler. ....

It seems to me that, in order to solve Kakuro without any arithmetic whatsoever, your solver must have a huge number of small 3-dimensional tables built in. These tables (or perhaps an algorithm) would provide an immediate answer to any question of the form "what are all the ways of making N digits add up to A without using any of X,Y,Z?" (N is one dimension, A is another, and X,Y,Z is the third.

That'd be much too complicated.
Given a puzzle, it is easy to compute the allowed combinations for each sector (and for the Mepham puzzles, with their small sectors, this is generally easy, even by hand).
All that I call the completely trivial part of the solution is the mere propagation of compatibility conditions between remaining combinations in sectors and remaining digits in the corresponding cells (you can see a few examples in the part of the solution I gave above). This is the simplest technique you can find on the few websites that describe techniques.

By this time I had established that the bottom two digits in c7 were 8 and 3, so I asked the exact question I used in the example above. The rest of c7 had to be 9-6-4 (in some order). It was also easy to establish that c8 had to be 8-6-5, and c9 had to be 8-7-6. Now the 4 in c7 couldn't be at r4c7 or r5c7, because either of these would force a 9 into c8 or c9, where there already was a 9. That logic places a 4 in r6c7. Etc etc etc.
By the way, which kind of fish, reptile, or bird is that? Did I use another Advanced Solving Technique?

As you describe it, it's a sequence of more elementary steps of the above kind.

[saul]

Here's another where I can't finish off the solution.

I got here without any trouble, and I've checked it in my solver, so I know it's right as far as it goes, but I don't see what to do next (barring trial and error.)

This illustrates what I was saying in a recent post, Bill. I want to write a manual solver that will allow me to ask for a hint at this point. The hint would not be to tell me the value of a specific cell, but would tell me something (probably the elimination of one or more candidates) that I could infer, and how.

Can either of you tell me what inference is available at this point in the solution? I've been looking at this on and off for several days now, and I just don't see anything. I found a couple of large cuts, but they aren't useful. Maybe I've just been looking at it too long.

[denis_berthier]

Here's another where I can't finish off the solution.

Can either of you tell me what inference is available at this point in the solution? I've been looking at this on and off for several days now, and I just don't see anything. I found a couple of large cuts, but they aren't useful.

As I don't know which values you have eliminated from the combinations, I can't tell for sure if the following is correct. But you can check.
The whip[3] shows the interaction of a horizontal and a vertical sector.

Code: Select all

Using your notation for rows and columns:
whip[3]: r8c3{n4 n6} - vr5c3{n247 n346} - r6c3{n5 .} ==> r7c3 <> 4
biv-chain[2]: r7c3{n2 n3} - hr7c0{n1246 n1345} ==> r7c4 <> 2
naked-pairs-in-a-column: c4{r4 r7}{n3 n4} ==> r8c4 <> 4


atk classification principles will remain a mystery. Unless we're missing some mysterious type of rule, this "moderate" puzzle is more difficult than many of the "hard" ones. The above should allow you to go a little further, maybe not to the end (there is another harder step).

[Smythe Dakota]

.... Can either of you tell me what inference is available at this point in the solution? ....

I hate to go against the title of this thread (well, no, that's a lie, I don't mind doing so at all) but a well-chosen trial-and-error attempt can go a long way.

In this case, I noticed that the single assumption (guess) that there is a 6 in r6c9 leads to a sequence of see-saws (if one goes up, another must go down, etc). So it looks promising.

It leads to a naked pair 7-8 in c9, and another in r8. This, in turn, forces 9 in r8c2, and a 5 just above it. Now we have naked pairs 4-6 in r8, and 3-4 in r7. This uses up all possible 4's in c3 and c4, so r4c4 must be a 3. Thus the bottom two cells in that word must be 4 and 6, forcing 8 and 5 (in some order) in r5c4 and r6c4. But neither 8 nor 5 works in r6c4. This disproves our original assumption of a 6 in r6c9, and thus forces a 6 in r8c9.

That's a lot of work to solve a single cell, but that's life. In some ways I am happier when a guess leads to a contradiction rather than to a solution. In the latter case, I may have "solved" the puzzle, but I have failed to establish uniqueness, which the purist in me tells me is just wrong.

I don't know whether the above is a whip or a braid or a trout or a turkey. I also don't know how similar this is to Denis' steps with the n's and v's and arrows and not-equal signs. I'll let him tell me "yeh, that's exactly what I just said" if that turns out to be the case.

Bill Smythe

[denis_berthier]

I don't know whether the above is a whip or a braid or a trout or a turkey.

No, nor is it any other species I know.

In some ways I am happier when a guess leads to a contradiction rather than to a solution. In the latter case, I may have "solved" the puzzle, but I have failed to establish uniqueness, which the purist in me tells me is just wrong

The first case (leads to a contradiction and justifies an elimination) is T&E, the second (leads to a solution) is guessing.
Even guessing isn't all white or black. It can be more or less justified. Guessing the same value at the start would have been quite arbitrary.

I also don't know how similar this is to Denis' steps with the n's and v's and arrows and not-equal signs. I'll let him tell me "yeh, that's exactly what I just said" if that turns out to be the case.

It can't be similar to any of my rules, because I have no means of guessing the value of a cell (apart from taking it as a given).

[saul]

In some ways I am happier when a guess leads to a contradiction rather than to a solution. In the latter case, I may have "solved" the puzzle, but I have failed to establish uniqueness, which the purist in me tells me is just wrong.
Bill Smythe

What I do in that case is to go back and try the other possibilities to verify that they lead to contradictions. Then I know I've proved uniqueness. This may seem a bit anal, but I was a math student in a prior life.

[saul]

As I don't know which values you have eliminated from the combinations, I can't tell for sure if the following is correct. But you can check.
The whip[3] shows the interaction of a horizontal and a vertical sector.

Code: Select all

Using your notation for rows and columns:
whip[3]: r8c3{n4 n6} - vr5c3{n247 n346} - r6c3{n5 .} ==> r7c3 <> 4
biv-chain[2]: r7c3{n2 n3} - hr7c0{n1246 n1345} ==> r7c4 <> 2
naked-pairs-in-a-column: c4{r4 r7}{n3 n4} ==> r8c4 <> 4


Thanks very much. I'm very busy with a project at work right now, so it will be a few days before I can really dig into this. I need to master your notation and dig into whips. I've started reading your book, but I'm still in the introductory sections. However, I can see at a glance that the conclusions will go a long way to solving the puzzle. I'm eagerly anticipating the later, harder situation.

atk classification principles will remain a mystery. Unless we're missing some mysterious type of rule, this "moderate" puzzle is more difficult than many of the "hard" ones. The above should allow you to go a little further, maybe not to the end (there is another harder step).

I wonder if they expect you to sometimes do some limited trial and error at the end. I agree with Bill in that doing a moderate bit of trial and error doesn't reduce my pleasure in the puzzles. My rule is, "As long as I can do it in my head, it's okay." Even when I get my program written, I expect there will be times when the program has no hints to offer.

It's too bad there aren't more online kakuro forums that discuss advanced solving rules, trial and error, and related issues. Or perhaps the best ones are all in Japanese.