The New Sudoku Players' Forum

[Smythe Dakota]

I don't see how you could call, for example, r7c7 a 1-cut in any helpful way.

It immediately gives r7c6 = (19+17)-(17+14)=5 ....

This doesn't come from anything being "cut" out of the puzzle. It comes from the simple fact that the horizontal sum of the five cells, minus the vertical sum of the four cells, is 5.

You could just as easily call r7c8 a 1-cut.

No, it doesn't separate the graph.

So what? It still immediately gives r7c6 = (19+17)-(17+14)=5, and for exactly the same reason.

In Kakuro, two cells connected by being in the same horizontal (or vertical) word are still connected if you remove a cell in between them. Removing r7c7 still leaves r7c6 and r7c8 connected, in any sense meaningful to kakuro.

Look at it this way. If you interchange the two columns in the bottom right corner (so that the answers are 5-6-8 instead of 5-8-6, and 8-9 instead of 9-8, and the vertical sums are 14 and 17 instead of 17 and 14), you have a puzzle which is isomorphic to the original. Yet, in some mysterious way, the cell that formerly was a 1-cut is no longer a 1-cut, and a cell that formerly wasn't a 1-cut has now become a 1-cut ??

Think of the grid as being composed of metal strips instead of paper cells. There is one horizontal metal strip for each horizontal sum, and one vertical metal strip for each vertical sum. Wherever a horizontal and vertical sum intersect, the corresponding horizontal and vertical metal strips are riveted together.

Think of removing a cell as being equivalent to removing the rivet connecting the corresponding horizontal and vertical metal strips.

If you remove the rivet at r7c7, the puzzle still doesn't come apart. r8c7 is still connected (via a horizontal metal strip) to r8c8, which in turn is still connected (via a vertical metal strip) to r7c8, which is still connected (via a horizontal metal strip) to both r7c7 and r7c6, the latter of which is still connected (via a vertical metal strip) to the main part of the puzzle.

Now, by contrast, remove the rivet at r7c6. Now the assembly consisting of two horizontal metal strips, r7c6-r7c7-r7c8 and r8c7-r8c8, and two vertical metal strips, r7c7-r8c7 and r7c8-r8c8, comes loose from the rest of the puzzle.

That's why I consider r7c6 to be a singularity (or whatever you want to call it), and r7c7 not.

Please note, also, that this r7c6 = (19+17)-(17+14)=5 business always gives you the answer at my singularity, rather than at your 1-cut.

Bill Smythe

[saul]

Bill,

The "singularities" and "doublarities" and whatever else you call them are all cuts in the graph theoretic sense. You and Denis are simply talking about different graphs. Since the graphs that you (and I) favor have higher connectivity than the graphs that Denis uses, it is apparent that his graphs will have more cuts, though not necessarily that they are more useful. Indeed, it seems reasonable to me that they would not be useful as often. Of course, any cut in your graph is a cut in Denis' graph also, so I would say that the burden of proof is on Denis.

In Denis' book, on page 430, there is an example of a 16 x 11 puzzle with 6 cuts, none of which would be a cut in my model, and these are used to analyze the graph. I haven't worked through the example, and at first glance I don't understand it completely. I think you ought to look at this example, Bill.

Denis,

Looking at Figure 15.5, I would say that the two cells immediately to the right of C1 form a 2-cut, and I would calculate their sum as 10. I gather that that's where the 10 clue in r3c3 of figure 15.6 comes from. I am, however, completely mystified by Figure 15.7. This has 13 white cells. As i understand it, the component P1 should have 8 while cells. How can C1 be in P1? Why are the 4 cells in the 2 x 2 at the lower right part of this component? Even if only the cells with candidates written in them are supposed to be part of P1, how can C1 get into this component? And if C1 is in P1 why is it not in P1 prime?

It appears to me that each of the cuts in 15.5 corresponds to a cut in my graph, although none of mine are 1-cuts. The attraction of using 1-cuts, of course, is that it's easy to find articulation points. I'd have to research algorithms for finding 2-cuts, etc. I'm sure they exist, but I don't know how expensive they are. There is also a difference in approach that I hadn't understood till now. You are replacinging the original puzzle by two or more equivalent puzzles, whereas Bill and I are making inferences about the original puzzle without transforming it. Psychologically, I find the latter approach more appealing (and easier to follow.) As I consider the example above, I'm kind of torn. When I deduce that the two cells in question total 10, what can I do with this knowledge? Well, I may be able to eliminate candidates for one or both of the cells. I have the problem though, that I don't really have a good way to record the information. If later on, I eliminate a candidate fm one of these cells, I may not remember to check if this also eliminates a candidate for the other.

Your method certainly records the information, but at the cost of losing the original puzzle. I don't think anybody would take this approach when solving with pencil and paper, and even with a computer program, it seems confusing. Does your program allow for constructing equivalent puzzles like this?

[denis_berthier]

Hi Bill,

I think you are making much fuss about what is merely different conventions. When there is a 1-cut in my sense, there are always 2 equivalent ones, due to grid topology. Whether you choose to consider that the 1-cut cell is inside the smallest part of the puzzle or outside is both arbitrary and irrelevant.
Once more, 1-cuts are an easy way of spotting potentially interesting sub-puzzles; depending on additional conditions about the two sub-parts they separate, different conclusions may be drawn (one cell value is fixed, two complementary sub-sectors have their sums fixed, two orthogonal sub-sectors outside a surface have equal sums, ...); this is where your n-ularities play a role.

In Kakuro, two cells connected by being in the same horizontal (or vertical) word are still connected if you remove a cell in between them. Removing r7c7 still leaves r7c6 and r7c8 connected, in any sense meaningful to kakuro.

We've already discussed this. We have different definitions of "connected". For me, connected means adjacent. It leads to a way of applying standard graph theory for finding 1-cuts automatically.

Look at it this way. If you interchange the two columns in the bottom right corner (so that the answers are 5-6-8 instead of 5-8-6, and 8-9 instead of 9-8, and the vertical sums are 14 and 17 instead of 17 and 14), you have a puzzle which is isomorphic to the original. Yet, in some mysterious way, the cell that formerly was a 1-cut is no longer a 1-cut, and a cell that formerly wasn't a 1-cut has now become a 1-cut ??

Permutations of columns is not valid in Kakuro in general - nor is it in this particular puzzle.

[denis_berthier]

Hi Saul,

The final application part of my book is mainly about showing how my general pattern-based approach and my general purpose resolution rules can be applied to various logic games.
It also shows how some application-specific rules can easily be included in the general framework.

With this background recalled, in the Kakuro case, I briefly discussed "surface sums", but my purpose was not to be complete on this application-specific topic.
I have no problem with keeping all the data obtained from any of the sub-puzzles in the original one.
I don't have time today, but I'll give you later a more detailed answer about the example you mention.

[Smythe Dakota]

.... You and Denis are simply talking about different graphs. ....

You've hit the nail on the head.

In Denis' graphs, two points are joined by a line segment if and only if they are adjacent either horizontally or vertically. In my graphs, two points are joined by a line segment if and only if they are in the same horizontal or vertical word.

.... Since the graphs that you (and I) favor have higher connectivity than the graphs that Denis uses ....

True.

.... it is apparent that his graphs will have more cuts ....

True.

.... though not necessarily that they are more useful. ....

And that's my whole point. Adjacency has nothing to do with kakuro. The digit at one end of an 8-digit word has as much effect on the digit at the other end, as the two digits in the middle have on each other.

.... Indeed, it seems reasonable to me that they would not be useful as often. ....

I think you and I are in complete agreement.

.... We have different definitions of "connected". ....

Yes.

.... Permutations of columns is not valid in Kakuro in general - nor is it in this particular puzzle.

I did not permute any columns. I only permuted the two 2-digit vertical words in the lower right corner. This permutation, in this puzzle, is 100% valid.

Suppose Jane accidentally drops the puzzle into a shredder. Jane manages to rescue the puzzle with only the four cells in the lower right corner missing. By comparing with the upper left corner, and taking advantage of the 180-degree rotational symmetry enjoyed by almost all published puzzle patterns, Jane is able to reconstruct the shape of the puzzle (i.e. the relative cell locations) in the missing corner. Jane then examines the tiny shreds from the shredder, and finds only a 17 and a 14. Jane realizes that these must be the missing vertical clues.

Jane now has enough information to solve the puzzle. Her reasoning goes like this: The singularity produces a 5 in r7c6. The remaining two cells in r7 must add up to 14, so we must have a 6 and an 8 (can't be 5 and 9 since we already have the 5). The 6 can't go in the column with the two-digit 17, so the 6 goes in the other column with the two-digit 14. The rest is trivial.

This demonstrates that the two puzzles are isomorphic -- the puzzle with the 17 on the left and the 14 on the right, and the one with the opposite arrangement. Yet, with the "adjacent" graph model, the 1-cut is in one case under the 17 and in the other case under the 14. This tells me that the "adjacent" graph model does not fit as well with the rules and concepts of kakuro as does the "in the same word" graph model.

Bill Smythe

[denis_berthier]

Hi Bill,

Note that 1-cuts depend only on the topology of white cells, not on the givens.
If you permute the givens instead of permuting the columns, your argument falls down: the 1-cut cell is unchanged.

[Smythe Dakota]

My point is that, if two puzzles are isomorphic as kakuro puzzles, but not as graphs, then the graph-theory model chosen is likely not the best fit.

Bill Smythe

[denis_berthier]

My point is that, if two puzzles are isomorphic as kakuro puzzles, but not as graphs, then the graph-theory model chosen is likely not the best fit.

The graph-theory model is not intended as a full model of Kakuro, but only as a model of white cell topology and only as a preliminary way of finding useful surface sums.

[denis_berthier]

Looking at Figure 15.5, I would say that the two cells immediately to the right of C1 form a 2-cut, and I would calculate their sum as 10. I gather that that's where the 10 clue in r3c3 of figure 15.6 comes from.

1-cut with my definition, but right for the origin of the 10 clue in P'1. Notice that whether there are 2, 3, ... or 9 cells to the right of C1 is irrelevant to the presence of this 10 clue in P'1.

I am, however, completely mystified by Figure 15.7. This has 13 white cells. As i understand it, the component P1 should have 8 while cells. How can C1 be in P1?

P1 has 9 cells, including C1.
C1 is a 1-cut cell, it is used to find the potentially useful surface, but it doesn't have to be deleted from all the sub-puzzles.

Why are the 4 cells in the 2 x 2 at the lower right part of this component?

Just as an illustration that there is something beyond P1.

Even if only the cells with candidates written in them are supposed to be part of P1, how can C1 get into this component?

See answer 2 above

And if C1 is in P1 why is it not in P1 prime?

Because I don't count it twice.
Notice that I could choose to keep it in P'1 instead of P1, if I was more interested in P'1 than in P1.

It appears to me that each of the cuts in 15.5 corresponds to a cut in my graph, although none of mine are 1-cuts.

With your definition of connectedness, your 1-cuts will be rare and they will correspond to the trivial assignment of a value for a cell. With my definition, you'll find more potentialities; the advantage is, you have a simpler algorithm; the counterpart of this generality is you'll have to make further checks before you can use them.

There is also a difference in approach that I hadn't understood till now. You are replacinging the original puzzle by two or more equivalent puzzles, whereas Bill and I are making inferences about the original puzzle without transforming it. Psychologically, I find the latter approach more appealing (and easier to follow.)

You shouldn't forget the context of this example: I only wanted to illustrate the fact that surface sums are more general than "singularities". I also wanted to show how sub-puzzles can sometimes be solved independently.

Your method certainly records the information, but at the cost of losing the original puzzle.

No, everything can be done in the original puzzle. Once a sub-puzzle is solved (or partially solved), its solution becomes part of the original puzzle.

[Smythe Dakota]

.... The graph-theory model is not intended as a full model of Kakuro, but only as a model of white cell topology and only as a preliminary way of finding useful surface sums.

In the example we've been discussing, wouldn't treating r7c8 as a 1-cut and treating r7c7 as a 1-cut provide precisely equal chances of being useful?

Bill Smythe

[denis_berthier]

.... The graph-theory model is not intended as a full model of Kakuro, but only as a model of white cell topology and only as a preliminary way of finding useful surface sums.

In the example we've been discussing, wouldn't treating r7c8 as a 1-cut and treating r7c7 as a 1-cut provide precisely equal chances of being useful?

If you mean r7c6 and r7c7, yes. As I said previously, most of the time there is such a choice.
r7c8 isn't a 1-cut.

[Smythe Dakota]

.... If you mean r7c6 and r7c7, yes. As I said previously, most of the time there is such a choice. ....

No, I meant r7c8.

If you interchange the two columns in the lower right corner, the new puzzle is kakuro-wise isomorphic to the original. Yet, by your graph-theory model, the new r7c7 (which now has a 14 over it instead of a 17) is still the 1-cut, and r7c8 (now with a 17 over it) still isn't.

To look at it another way, suppose you re-define "connected to" in your model as follows: Cell X is connected to cell Y if and only if X and Y were connected before, except for r7c6-r7c7-r7c8, where we re-define r7c8, rather than r7c7, to be the one that is connected to the other two.

That model is as valid as yours. In fact, it's graph-wise isomorphic to yours. But in this new model, r7c8 is the 1-cut, and r7c7 isn't. (Of course, r7c6 is still a 1-cut too, and in fact it is a singularity in both models.)

So, by changing the definition of "connected to" at will (but still respecting the edict that only cells in the same vertical or horizontal word can be connected, and also the edict that, in any N-digit word, there will be N-1 connections), you can come up with a whole bunch of potential 1-cuts, many more than before. It might even be possible (I'm not sure) that, given any cell, a graph can be devised in which that cell will be a 1-cut.

Bill Smythe

[denis_berthier]

If you interchange the two columns in the lower right corner, the new puzzle is kakuro-wise isomorphic to the original.

I already answered this: you can't interchange columns in Kakuro. And if you interchange the givens instead of the columns, the 1-cut cells are unchanged.

[saul]

If you interchange the two columns in the lower right corner, the new puzzle is kakuro-wise isomorphic to the original.

I already answered this: you can't interchange columns in Kakuro. And if you interchange the givens instead of the columns, the 1-cut cells are unchanged.

You two must be talking at cross-purposes. What Bill is saying is that if you interchange the bottom two cells in the last two columns, including the clues, you get an isomorphic puzzle, which is indeed the case. On the other hand, Denis is correct in that the cut would not move.

Denis, I'm glad you explained that your graph model was not intended to be a full model of the kakuro puzzle. I hadn't realized that before, and it really kept me from following what you were saying. I want to respond to your last post on this subject, but I need some time to formulate my thoughts.

[denis_berthier]

Denis, I'm glad you explained that your graph model was not intended to be a full model of the kakuro puzzle. I hadn't realized that before, and it really kept me from following what you were saying.

It isn't even a full model of surface sums.
I thought this was obvious from the whole context of the book.

To be more precise, I could write the same thing for all the logic puzzles I've studied as for Sudoku:
- whips and braids constitute the main set of resolution rules (and, of course, in Kakuro, they are totally independent of surface sums);
- most of the puzzles can be solved by short whips;
- the difference with Sudoku is, I don't have precise statistics about the previous claim, for lack of a large collection of unbiased (or controlled-bias) puzzles; for each type of puzzle, I rely only on a few hundred puzzles taken from the hardest of several websites;
- g-whips (as in the last example that blocked you) allow to go a little farther than whips;
- as a result, the W and gW ratings constitute the backbones of two rating systems for any CSP; most of the time, these two ratings are equal.

For each type of puzzle, there can also be application-specific rules. Many of these can be interpreted as whips and they therefore naturally find their place in my hierarchy of rules.
In particular, in Kakuro, the most elementary interaction rules between the candidate-digits in a sector and the candidate-combinations in a black cell are whips[1].
Surface sums are different, they are really application-specific. When you use them, you can sometimes get a solution with shorter whips. How frequent this can happen depends of course on the size of the grid and the density of black cells. For large puzzles and low black density, this must be rather rare; but I have no precise figures. Even in small puzzles, surface sums are very rarely enough to solve a puzzle; you have to fall back on whips.