The New Sudoku Players' Forum

[denis_berthier]

I prefer to get there via http://www.sudoku.org.uk/kakuroflash/kakuro.html

Thanks for this direct link, I didn't know it.

I suppose those stand for Gentle, Medium, Tough, and Difficult, or something like that.

If they use the same notation as for Sudoku and Jigsaw, M is Moderate and D Diabolical.
I don't like much the white arrows in the black cells. When I try to copy the puzzle, it's confusing. And it's ugly (well, personal tastes ...). Also I don't like having access only to the last 10; if I want 10 more, I have to wait 10 days (that'll be next season!).


Yesterday evening, I've tried the 10 I could see there (2 Gs, 3 Ms, 4 Ts, 1 D). I don't see much difference in difficulty: they are all in W2 except 3 Ts (sic, not Ds) in W3. In Kakuro, W2 implies that any elimination can be done by considering only one sector at a time (see my previous examples of whips[2]).
Even for the 3 in W3, each has at most 2 or 3 whips[3], and there's only one case in total of such a whip that involves several sectors.
So, as Bill suggested, they are quite easy, compared to the atk ones (even restricted to the Medium ones) - recalling however that I had only a small sample.

One other limitation is size: they are all 10x10 (at least the 10 I could see). This puts drastic restrictions on the possible combinations and there are many small sized sectors.
On atksolutions.com (I have no shares there), they have puzzles with 5 different sizes (10 to 14) and with 3 levels of difficulty. I like their clean and sober presentation with blue cells and white numbers inside. Unfortunately, you can choose the level but not the size and the 10x10 ones do not come out often.

Notice that size is not the only factor of difficulty: even with size 10, difficulty can be much higher than on the Mepham website.
I've seen a 10x10 atk one in W11 (in the Wn rating, difficulty increases ~exponentially wrt n). In the 14x14 collection, I've even seen one in W22.
This is consistent with what I had noticed for Sudoku long ago: all the Mepham puzzles are relatively easy.

However, the case of Kakuro puzzles can hardly be compared with Sudoku: for lack of any discussion forum, we have little knowledge of how people solve them and of what should be considered as difficult for manual solving. Scanning the Kakuro part of this forum, I've seen two that seemed to be harder than usual:
- the Surfertje thread ("Tough ending"), but it's "only" in W6;
- the h3lix thread ("Incredibly difficult kakuro (14x14)"), but it's "only" in W7.

There also seems to be two different approaches: people looking for puzzles amenable to treatment by surface sums (and thus doing much arithmetic) and people preferring to track allowed combinations (and hopefully to do little arithmetic). My approach is clearly of the second kind, pushed to the extreme of doing no arithmetic at all - although, of course, I can also occasionally use surface sums. It seems Bill prefers the first type of puzzles.

I once saw a puzzle that appeared to have been created by chopping off the bottom two rows or so from a larger puzzle. (That made the diagram lose the 180-degree rotational symmetry common in newspaper puzzles.) As a result, there was at least one vertical "word" consisting of just one digit. But the puzzle still specified the "sum", i.e. the digit, in that cell.

Formally, this doesn't raise any problem; allowing one-cell sectors can make it easier to create hard puzzles. But I agree it isn't not very elegant.

[Smythe Dakota]

.... [ In the online Mepham puzzles ] I don't like much the white arrows in the black cells. When I try to copy the puzzle, it's confusing. And it's ugly ....

I agree. The arrows look as though they're pointing backwards. But I've gotten used to it.

.... I don't see much difference in difficulty: they are all in W2 except 3 ....

That's true. Some G's seem more difficult than some D's. But for me, Kakuro is not my life, it's just an enjoyable pasttime. It's much richer than Sudoku in its variety of solving techniques. One almost invents a new solving technique every time one solves another puzzle (well, at least for me). I have no desire to master techniques so advanced that they have names, like whips and braids. And I don't mind arithmetic at all. Chevy Chase, as Gerald Ford in a presidential debate sketch on SNL, once said "Um, it was my understanding that there was to be no math ...."

One other limitation is size: they are all 10x10 ....

Actually 9x9, if you don't count the purely black edges at the top and left, whose only purpose is to have a place to specify the sums. If the sums were specified at both ends of each word, and you counted all the edges, it would be 11x11.

There are a couple of elementary (but well known) Sudoku techniques that come up even more frequently in Kakuro than in Sudoku. One of these is naked (or hidden) pairs, triples, quads, etc. For example, if I find three cells in a long word, all of which must be at least 7, then I know the remaining cells in that word must all be at most 6.

The other is the much-disparaged (and rightly so) uniqueness technique. I often see cases (usually with 1's and 2's, or 8's and 9's) where, for example, there could not be a 1 or 2 in such-and-such a cell because that cell would become one corner of a rectangle already known to contain either a 1 or a 2 in the other three corners. The purist in me feels it is one of the solver's duties to establish uniqueness. It feels like cheating to assume uniqueness.

I must admit, however, that if a certain value can't be in a certain cell because it would create a uniqueness problem with the eventual solution, then I am naturally driven to find a "legitimate" reason why that value couldn't be in that cell.

Bill Smythe

[denis_berthier]

One other limitation is size: they are all 10x10 ....

Actually 9x9, if you don't count the purely black edges at the top and left, whose only purpose is to have a place to specify the sums. If the sums were specified at both ends of each word, and you counted all the edges, it would be 11x11.

But that'd be quite redundant.
There doesn't seem to be any standard for defining size. I've chosen to count the 1st row and column of black cells because, in my modeling of this CSP, they hold CSP variables that are dealt with exactly as the CSP variables in the white cells.

There are a couple of elementary (but well known) Sudoku techniques that come up even more frequently in Kakuro than in Sudoku. One of these is naked (or hidden) pairs, triples, quads, etc.

Of course, you have to restrict these patterns to sectors. And, for the hidden ones, you have to check that the relevant digits must be present in the sector, whichever of the remaining combinations is the right one (i.e. that they belong to all these combs). You can even find Fish, with conditions on both types of relevant sectors (horiz and verti).
I haven't noticed that Subsets (except maybe Pairs) appear so frequently - but it may be due to the fact that I've dealt with harder puzzles. In Sudoku also, Subsets appear more frequently in easy puzzles (they are designed for this).

The purist in me feels it is one of the solver's duties to establish uniqueness. It feels like cheating to assume uniqueness.
I must admit, however, that if a certain value can't be in a certain cell because it would create a uniqueness problem with the eventual solution, then I am naturally driven to find a "legitimate" reason why that value couldn't be in that cell.

+1

[Smythe Dakota]

.... And, for the hidden [ pairs, triples, quads ] , you have to check that the relevant digits must be present in the sector ....

Which is one reason I prefer Kakuro to sudoku. It's one of the "richer" techniques I was talking about. For example, if 3 digits add up to 8, there must be a 1 in there somewhere. Same if 4 digits add up to 27 -- there must be a 9 somewhere. There are gazillions of those.

.... +1

Does that mean "right on"?

Bill Smythe

[denis_berthier]

.... And, for the hidden [ pairs, triples, quads ] , you have to check that the relevant digits must be present in the sector ....

Which is one reason I prefer Kakuro to sudoku. It's one of the "richer" techniques I was talking about. For example, if 3 digits add up to 8, there must be a 1 in there somewhere. Same if 4 digits add up to 27 -- there must be a 9 somewhere. There are gazillions of those.

While playing, one must indeed be able to detect such varied situations. But it is also interesting to be aware of the unique logic behind the multiple appearances:

- for Naked, Hidden or Super-Hiddden (Fish) Subsets, the additional conditions that appear in Kakuro wrt Sudoku are merely the way the general Subset rule, formulated in terms of CSP variables and constraints, and valid in any finite CSP, translates into the particular vocabulary of Kakuro;

- the various sum constraints, when translated into allowed combination constraints, allow to consider rn or cn (but not bn) CSP variables analogous to those now familiar in the Sudoku case (in addition to the "standard" rc ones); this way of seeing things may not be essential when you deal only with Hidden Singles or Hidden Subsets (you can see the situations on the fly), but it becomes essential when you need to use these variables in chains.

[denis_berthier]

Hi Bill and Saul,

I've found an atk puzzle that may interest you.
http://www.carva.org/denis.berthier/Misc/H53902.png

There are many potentially useful surfaces, but I find none leading to drastic simplifications.
I'd like to know if you have an easy solution using (any kind of) surface sum rules.

[saul]

Hi Bill and Saul,

I've found an atk puzzle that may interest you.
http://www.carva.org/denis.berthier/Misc/H53902.png

There are many potentially useful surfaces, but I find none leading to drastic simplifications.
I'd like to know if you have an easy solution using (any kind of) surface sum rules.

I have never successfully solved a hard atk puzzle manually, so I certainly don't have an "easy" solution, but I've started working on it, and I'll send you anything that seems interesting as I go along. I'm use the term "n-cut" to mean "a cutset with n elements" for n = 1, 2, ... . I've used some 1- and 2-cuts to get to this point, but here's a useful 3-cut.

In this position,

look at the last 3 coulmns (11-13) in rows 4-8. Summing horizontally, and ignoring the cells whose values are known, we get 9+17+12+6 = 44. Summing vertically in the last two columns, we get 6 + 26 = 32, so r5c11 + r6c11 + r7c11 = 12. The only possibilities, given the candidates we already have are 138 and 129, so we quickly deduce that the situation is this
.
In column 11, once we know that 1238 is a subset, the remaining elements are determined.

I find this interesting because, in my experience, useful 3-cuts are quite unusual.

"Drastic" is in the eye of the beholder, but this seems like a valuable simplification to me, for only a small effort. Still, I wonder if this would be of any use in the kind of pattern-based solving you're interested in, because we can't exploit the value of the cut until we've reduced the set of candidates. In the symmetric position column 3, we can say that the sum f rows 7-9 is 10, but I don't see any way to use that yet.

Is this reply the kind of information you're looking for? If so, I'll send anything else I find. I should say, of course, that I don't know for certain all the inferences I've made to this point are correct, and that if I've made a mistake, then the information in this post might be wrong.

[saul]

I'm delighted to report that I solved the puzzle -- my first hard-level atk puzzle. Thanks Denis, for calling it to my attention. The second 3-cut that I mentioned eventually did come in handy, but I'm sorry to say that I neglected to copy the diagram. I had filled in all the cells of the 28 in column 2, except for the 2 in row 3 and the 4 in row 8. Almost all the cells were filled, but I couldn't see what to do. I was nonplussed for a while, but then I remembered the 3-cut. This broke it into two small puzzles that were easily solved.

All I can say is that I know I could not have solved this puzzle without using surface sums, except by extensive trial and error.

[denis_berthier]

"Drastic" is in the eye of the beholder

more or less.

Considering the exceptionally large (at least in the hard atk collection) number of potential 1-cuts available at the start, with up to 3 levels of embedding, what I had in mind is splitting the puzzle into fully independent smaller ones. But, in fact, only few of the sub-puzzles can be solved independently of the rest.

The first thing I had noticed is the two 1-cuts isolating two large sub-puzzles:
- upper-left sub-puzzle, isolated by cell r7c6 (r6c5 for you)
- and lower-right sub-puzzle, isolated by cell r9c10 (r8c9 for you)
(I usually choose the 1-cut cell inside the surface I'm interested in.)

It is easy to see that

Code: Select all

r8c6 =
 ( -
   ; vertical sums, rightwards inside the surface
   (+ 29 16 19 21 28  33 16 28 13 13 13 11 6 9 14 8 4)
   ; horizontal sums, downwards inside the surface
   (+ 14 14 10 15 17 24 15 17 37 6 21 22 22 14 15 12)
)
= 6


and similarly

Code: Select all

r8c10 =
 ( -
   ; vertical sums, rightwards inside the surface
   (+ 16 15 11 6 14 10 16 14 5 28 6 31 36 13 35 26 15)
   ; horizontal sums, downwards inside the surface
   (+ 9 29 13 6 16 17 14 39 21 21 25 24 7 19 18 14)
)
= 5

(The latter can also be obtained in a simpler way, using the previous result and the small diagonal surface in the middle.)


After this, the upper-left sub-puzzle can indeed be solved independently of the rest, but its solution is not "drastically" simpler than that for the original puzzle: it only passes from W7 to W6.
For this reason, I didn't consider the lower-right sub-puzzle (which was an error because it is finally much easier).
I also considered three smaller sub-sub-puzzles (the small one in the middle left, the larger one available in the upper right and the small one on the upper left), but none of them can be solved independently of the rest.

here's a useful 3-cut. In this position,

look at the last 3 coulmns (11-13) in rows 4-8. Summing horizontally, and ignoring the cells whose values are known, we get 9+17+12+6 = 44. Summing vertically in the last two columns, we get 6 + 26 = 32, so r5c11 + r6c11 + r7c11 = 12.

For me, this is merely a 1-cut: cell r8c11 (r7c10 in your notation) isolates the small sub-puzzle on the middle right from the rest of the puzzle. Ignoring (or not) the known cells, we do get r5c11 + r6c11 + r7c11 = 12 (in your notation) and the small puzzle is easily solved.

[Edit 04/03 (thanks to Saul)]: corrected "cell r8c11 (r7c10 in your notation)" to "cell r8c12 (r7c11 in your notation)".

I wonder if this would be of any use in the kind of pattern-based solving you're interested in, because we can't exploit the value of the cut until we've reduced the set of candidates. In the symmetric position column 3, we can say that the sum f rows 7-9 is 10, but I don't see any way to use that yet.

In my approach, I can create more CSP variables than the standard ones. Creating a sum for a group of rows (or columns) that is a subset of one of the given sectors is not a problem.


Now, I have a technical question: how do you proceed to make changes (add values and candidates) to a .png copy of an atk puzzle ? Am I missing anything on the atk website that'd allow to re-inject a puzzle into their online solving software ?

[saul]

"Drastic" is in the eye of the beholder

more or less.
It is easy to see that

Code: Select all

r8c6 =
 ( -
   ; vertical sums, rightwards inside the surface
   (+ 29 16 19 21 28  33 16 28 13 13 13 11 6 9 14 8 4)
   ; horizontal sums, downwards inside the surface
   (+ 14 14 10 15 17 24 15 17 37 6 21 22 22 14 15 12)
)
= 6


and similarly

Code: Select all

r8c10 =
 ( -
   ; vertical sums, rightwards inside the surface
   (+ 16 15 11 6 14 10 16 14 5 28 6 31 36 13 35 26 15)
   ; horizontal sums, downwards inside the surface
   (+ 9 29 13 6 16 17 14 39 21 21 25 24 7 19 18 14)
)
= 5

(The latter can also be obtained in a simpler way, using the previous result and the small diagonal surface in the middle.)

Good. I didn't notice these 1-cuts, but there's more arithmetic than I can reliably carry out in my head these days. I treated the two of them together as a 2-cut, which is how I solved the little diamond in the middle.

For me, this is merely a 1-cut: cell r8c11 (r7c10 in your notation) isolates the small sub-puzzle on the middle right from the rest of the puzzle. Ignoring (or not) the known cells, we do get r5c11 + r6c11 + r7c11 = 12 (in your notation) and the small puzzle is easily solved.

I don't follow this. It looks to me like r8c11 is a clue (6 across, 31 down) which I wouldn't represent in the graph at all. I thought at first it was a typo, but I don't see any nearby 1-cut, so perhaps you're using a more sophisticated graph model than I am. In my model, only the white cells are vertices, and adjacent vertices are cells in the same sector. Or am I just overlooking something?

Now, I have a technical question: how do you proceed to make changes (add values and candidates) to a .png copy of an atk puzzle ? Am I missing anything on the atk website that'd allow to re-inject a puzzle into their online solving software ?

If you click the puzzle icon in the lower right-hand corner of the atk web page,

you can enter a puzzle name -- H53902 in this case. I found this accidentally when I missed clicking on the neighbor icon that turns off the annoying music.

I've been meaning to ask you, is your software available publicly at all?
Also, you mention that you use additional CSP variables. Are these essentially sector variables taking values over all possible permutations with the correct sum? I gather that something like this is described in http://4c.ucc.ie/~hsimonis/kakuro%20modref08.pdf but because I don't know the technical vocabulary, I can't be certain. It's clear to me that the approach described in that paper isn't useful for manual solution, so I haven't tried very hard to read it, but it has given me a yen to look at ECLiPSe sometime.

Saul

[denis_berthier]

here's a useful 3-cut.

For me, this is merely a 1-cut: cell r8c11 (r7c10 in your notation) isolates the small sub-puzzle on the middle right from the rest of the puzzle. Ignoring (or not) the known cells, we do get r5c11 + r6c11 + r7c11 = 12 (in your notation) and the small puzzle is easily solved.

I don't follow this.

Sorry, I made an error in counting the columns. I meant r8c12 (r7c11 in your notation). I'll correct my previous post.

Now, I have a technical question: how do you proceed to make changes (add values and candidates) to a .png copy of an atk puzzle ? Am I missing anything on the atk website that'd allow to re-inject a puzzle into their online solving software ?

If you click the puzzle icon in the lower right-hand corner of the atk web page,

you can enter a puzzle name -- H53902 in this case. I found this accidentally when I missed clicking on the neighbor icon that turns off the annoying music.

Thanks. I think I would never have found it. Actually, I don't use their software to play. I just copy (in the stupid way we talked about) their puzzles into mine.
On the rare random occasions when I get two puzzles with close names, they often have the same pattern of black cells. This may give the opportunity to compare various data sets sharing the same pattern.

I've been meaning to ask you, is your software available publicly at all?

No. If, some day, I decided to make CSP-Rules public, even considering that the general theory is written in full detail my last book ("Pattern-Based Constraint Satisfaction"), I would have first to write a user manual - about CSP-Rules itself, about its interfaces to all the games already programmed in it and about how to use it for programming new CSPs.

Also, you mention that you use additional CSP variables. Are these essentially sector variables taking values over all possible permutations with the correct sum?

They are sector variables representing the possible COMBINATIONS in the sector. Tracking combinations seems to be a standard technique, as I saw it mentioned on several websites. I just formalised this by defining the relevant CSP variables.
Using permutations would be totally absurd both for a human solver and from a programming POV.
In the worst case, the cardinal of the domain is: Perm(45, 9) = 9! = 362,880 , resp. Comb(45, 9) = 1.
Magic sectors (also a standard notion) correspond to cases where there is only one combination: in my approach, these unique combinations are the givens (totally replacing the sum constraints).
I can also have givens in the white cells, which is useful when I apply surface sum rules before resolution.

I gather that something like this is described in http://4c.ucc.ie/~hsimonis/kakuro%20modref08.pdf

No, it's very different; he doesn't replace sums by combinations (or permutations).

but because I don't know the technical vocabulary, I can't be certain. It's clear to me that the approach described in that paper isn't useful for manual solution, so I haven't tried very hard to read it, but it has given me a yen to look at ECLiPSe sometime.

Well, I didn't read the details either. The paper is a mere exercise in programming ECLIPSe and Mini-SAT, with no new idea (as 99.99% of the published "scientific" papers - a result of the "publish or perish" constraint).



Could we come back to the puzzle I mentioned above? After applying easy surface sums and then simple rules in each sector (rules in W1 and W2), I get the following situation (candidates are not displayed): http://www.carva.org/denis.berthier/Misc/H53902-UL.png
The remaining puzzle is simpler than the original one, but it is still in W6. You said you had an easy trick with a 3-cut but I didn't get it. Could you show it on this "new" puzzle?

[saul]

Sorry, I made an error in counting the columns. I meant r8c12 (r7c11 in your notation). I'll correct my previous post.

I'm afraid I still don't follow. As I count the columns, this is the one with the 36 down sector. If you eliminate one of the cells in this sector, the remaining cells are still adjacent, so the puzzle isn't disconnected.

They are sector variables representing the possible COMBINATIONS in the sector. Tracking combinations seems to be a standard technique, as I saw it mentioned on several websites. I just formalised this by defining the relevant CSP variables.
Using permutations would be totally absurd both for a human solver and from a programming POV.

Yes, I try to track combinations myself; this makes much more sense than what I imagined. One of my plans for my solver, if I can ever get back to working on it, is to modify the help in the atk solver in this regard. If you right-click on a clue, a popup shows all possible combinations for the corresponding sector. I plan to modify it so that the combinations excluded by the cells already solved are eliminated.

Could we come back to the puzzle I mentioned above? After applying easy surface sums and then simple rules in each sector (rules in W1 and W2), I get the following situation (candidates are not displayed): http://www.carva.org/denis.berthier/Misc/H53902-UL.png
The remaining puzzle is simpler than the original one, but it is still in W6. You said you had an easy trick with a 3-cut but I didn't get it. Could you show it on this "new" puzzle?

Sorry, I guess I sacrificed clarity for brevity. What I was trying to say was that in the middle section on the left we have row sums 22+14+15+12=63 and column sums 16+21+16=53 so that r7c3+r8c3+r9c3=10, using my notation. (This is symmetric to the position we were discussing earlier that I think is a 3-cut and you say is a 1-cut, so presumably you would say this is a 1-cut also.)

Since the atk puzzles seem to be always radially symmetric, every time I find a surface sum I check the symmetric one also. At the time I first found this one, it wasn't useful to me at all. I consider an inference useful if it allows me to eliminate a candidate, with the convention that all cells start with candidates 1-9. However, much later on in the solution process, when i was stymied, I remembered this surface sum and went back to it. By that time, I had made some more deductions, and the surface sum allowed me to complete the puzzle. I don't know if I can recreate this latter situation, because I'm not at all systematic in my approach to solving. Also, I suspect that if I did manage to recreate it, it wouldn't be of much interest to you. If you think it would be of interest, I'm willing to take a shot at reproducing it, but I may not be successful.

[denis_berthier]

Sorry, I made an error in counting the columns. I meant r8c12 (r7c11 in your notation). I'll correct my previous post.

I'm afraid I still don't follow. As I count the columns, this is the one with the 36 down sector. If you eliminate one of the cells in this sector, the remaining cells are still adjacent, so the puzzle isn't disconnected.

After this cell is eliminated, the small white triangle on the right is disconnected from the rest of the white cells. (Connections can only be horiz or verti, not diagonal).
This is a 1-cut because it eliminating only one cell is enough to disconnect the connection graph.

I try to track combinations myself; this makes much more sense than what I imagined.

yes, it is very powerful.

One of my plans for my solver, if I can ever get back to working on it, is to modify the help in the atk solver in this regard. If you right-click on a clue, a popup shows all possible combinations for the corresponding sector. I plan to modify it so that the combinations excluded by the cells already solved are eliminated.

I think that'd be very helpful. It is really boring to do it manually.

the following situation (candidates are not displayed): http://www.carva.org/denis.berthier/Misc/H53902-UL.pngThe remaining puzzle is simpler than the original one, but it is still in W6. You said you had an easy trick with a 3-cut but I didn't get it. Could you show it on this "new" puzzle?

Sorry, I guess I sacrificed clarity for brevity. What I was trying to say was that in the middle section on the left we have row sums 22+14+15+12=63 and column sums 16+21+16=53 so that r7c3+r8c3+r9c3=10, using my notation. (This is symmetric to the position we were discussing earlier that I think is a 3-cut and you say is a 1-cut, so presumably you would say this is a 1-cut also.)

Yep, 1-cut. What counts isn't the number of cells in the sector but the number of cells necessary to disconnect the puzzle.
The central "diamond", as you call it, is a 2-cut.
You could have a 3-cut with the small vertical rectangle in the upper left corner.

[saul]

We seem to be using the same definitions, and yet your statements leave me puzzled. Can you tell me what are the coordinates of the cells in "the small white triangle on the right?"
Yes, I agree that the size of the cut is the number of cells eliminated, as in graph theory. I also agree that diagonal adjacency has nothing to do with it. I take two cells to be adjacent if they are in the same sector, horizontal or vertical, so in a sector or 7 cells, each would be adjacent to the other 6. Do you make the same definition?

[denis_berthier]

I take two cells to be adjacent if they are in the same sector, horizontal or vertical, so in a sector or 7 cells, each would be adjacent to the other 6. Do you make the same definition?

No. Being in the same sector is not enough. They must be adjacent in the usual sense, i.e. touch each other: (r'=r and c'=c+-1) or (c'=c and r'=r+-1).