The New Sudoku Players' Forum

Website · by **denis_berthier** » Mon Feb 25, 2013 2:33 pm

saul wrote:No, it's linear in the x[r][c][k].

Yep, using Boolean variables ; good idea.

by **saul** » Fri Mar 08, 2013 3:04 pm

Good Morning Denis,

Well, it's morning in Kansas, anyway. I thought you might be interested in this example

of a "complex" surface sum. (I use the term "simple surface sum" for a surface sum that constrains the value of a single cell, and "complex" for anything else.)

In the remarks below, I'm using my notation, which may be different from yours. rxcy means "row x column y" where the numbering of rows and columns starts at 0, with the borders of blue cells, so that the first row with white cells is row 1. Also, <> means "not equal."

Looking at the lower right-hand corner, we see that
r6c5 + r7c5 = 10 + 12 - 4 - 3 = 15, so in particular, r6c5 <> 5. (Also, r7c5 <> 7, but that turns out to be unimportant.)

It is now clear that the numbers in column 5 are 9-8-7-6-4-3-1, so
r5c5 = 3, r5c4 = 4, r5c1 = 1.

After this, the simplest kinds of inference solve the puzzle.

I still have no idea how to detect these surface sums automatically.

As I slowly improve in kakuro solving, I find myself using surface sums less frequently, but I have no idea how to solve this one without a surface sum. I've been too busy with other things to devote much time to this for the past couple of weeks, so I still haven't learned about whips, or made much progress on writing my solver.

Website · by **denis_berthier** » Fri Mar 08, 2013 5:42 pm

Hi Saul,
Here (Paris) it's already 6 p.m. (and raining).

saul wrote: I'm using my notation, which may be different from yours.

I start numbering with 1 instead of 0, but that's not a problem.

saul wrote: I still have no idea how to detect these surface sums automatically.

Detecting them is easy:
1) build the connection graph : vertices = white cells ; put an edge between two white cells iff they are adjacent;
2) use a standard algorithm for detecting 1-cuts in the connection graph (i.e. cells that disconnect it). More generally, you can detect cuts of any size, but starting with size 1 seems simpler.

The question is, how to use them afterwards. In case of 1-cuts, it's relatively easy, because they are equivalent to new sum constraints. But when you want to deal with 2-cuts, it leads to introduce new types of constraints (equalities between distant sums).
My experience with hundreds of puzzles (classified as hard in the atk collection) tend to show that surface sums do not generally lead to noticeable simplifications (in terms of the W rating) of the whip-based solutions.

saul wrote: I have no idea how to solve this one without a surface sum

Perhaps you don't completely track the allowed combinations (they appear as values of the hrc and vrc CSP variables in my resolution paths). Here's my solution without surface sums, again with all the details. It requires only whips[2] and pairs (but these are a special case of whips[2]).

Hidden Text: Show

by **Smythe Dakota** » Sat Mar 09, 2013 6:03 am

This one lends itself to some easy techniques, once you've gotten as far as the diagram.

In the lower right corner, the horizontal sum of the six cells is 22, while the vertical sum of the four cells is 7. Therefore the remaining two, r6c5 and r7c5, must add up to 15. This means either 6-9 or 7-8 (in some order). So r6c5 cannot be a 5.

Thus there is nowhere to put a 5 in column 5. Since the two missing digits in column 5 must add up to 7 (45 minus 38), the other missing digit must be 2. Eliminating all the 2's in column 5 immediately leads to the location of the 1, 3, 4 in that column.

Bill Smythe

Website · by **denis_berthier** » Sat Mar 09, 2013 7:07 am

Hi Bill,
Nice to see someone else is interested in Kakuro.
OK with your solution, but Saul wanted one that doesn't use surface sums.
(In the present case, it's probably simpler to use surface sums)

by **Smythe Dakota** » Sun Mar 10, 2013 4:14 am

I don't even know what a "surface sum" is. And I don't feel like wading through old posts to find out. Probably it's just the name (unbeknownst to me) of the technique I already used.

If a puzzle has a 3-digit clue and a 2-digit clue in (for example) the bottom right corner, with the 3-digit clue sticking out over the 2-digit clue, then the stick-out cell is what I call a singularity. It could also be called a "gimme". If the horizontal sum of the five cells is H, and the vertical sum of the four that don't stick out is V, then the stick-out cell must be H minus V.

In the above example there is no singularity, but there is a "doubularity" (dub-you-lair-i-ty). The horizontal sum of six cells is 22, the vertical sum of four of them is 7, so the two cells that stick out horizontally must add up to 15.

There is also such a thing as a "difference doubularity". If, for example, there are four cells arranged in a square, plus an extra cell sticking out vertically and another sticking out horizontally, the difference between the two stick-out cells must be the same as the difference between the horizontal sum of one five-cell pattern and the vertical sum of the other. The larger this difference is, the closer to a "gimme" we have. In the most extreme case, if this difference is 8, then we do have a "gimme" -- 1 and 9.

Bill Smythe

Website · by **denis_berthier** » Sun Mar 10, 2013 4:46 am

Smythe Dakota wrote:I don't even know what a "surface sum" is. And I don't feel like wading through old posts to find out. Probably it's just the name (unbeknownst to me) of the technique I already used.

"Surface sum" is a name I found on several Kakuro websites. I adopted it in my book and here, because it seems quite appropriate: it deals with the difference between the horizontal and the vertical sums of the white cells making a surface separated from the rest of the puzzle by one (or more) white cell(s).
It is more general than the examples you give, e.g. there may be black cells inside the surface (provided they carry clues).

by **saul** » Sun Mar 10, 2013 7:22 pm

Denis wrote,

Nice to see someone else is interested in Kakuro.

I agree; welcome, Bill. I think if you work through my last post, you'll see that you and I solved the puzzle in exactly the same way. I should explain perhaps that I'm trying to write a computer program that will provide useful hints that will help me, and maybe others, to get better at kakuro. I haven't had much chance to work at it lately, unfortunately.

Denis wrote,

Detecting them is easy

Do you have a simple proof of this? I'm having trouble even coming up with the statement I want to prove. If the proof isn't simple, perhaps you could at least state the theorem for me. In the few examples I've looked at, the set of cells in the "surface" is indeed a cut set, but what then? Here's an example with (at least) two cut sets of cardinality two.

On the one hand, we easily see that the cells in row 4, columns 5 and 6 must sum to 14, and are therefore 8 and 6, respectively.
Alternatively, we can argue as follows:
1) The unknown cells in columns 5 thorough 8 sum to 57.
2) The unknown cells in rows 3, 4, and 6, on the right-hand side of the board only, sum to 54.
3) Therefore r7c8 - r4c4 = 3, and so r7c8 <> 4.

In either case, we get enough information to quickly solve the puzzle.

In both cases, the two cells involved give a cut set, but in one case we know their sum, and in the other case, we know their difference.
As I'm writing this, I'm starting to think that the statement is that the set of cut vertices can be partitioned into two subsets, one of which is perhaps empty, such the difference of the cells in the two sets is known. What I'm thinking is that, if we start one of the components in the graph that results from deleting the cut set, then adding certain of the cells in the cut set would complete all the columns, and adding the other cells in the cut set would complete all the rows. Then we would know the difference between the cells in the two subsets of the cut set. (This statement is perhaps too strong. We might not end up using all of the cells of the cut set. I also need to say that the cut set in minimal in the sense that no proper subset is a cut set.)

I feel, at least, that I'm closer to stating the theorem, if no closer to proving it. I also don't know an algorithm for finding cut sets of a given size (except, of course, for single vertices.)

Denis wrote,

The question is, how to use them afterwards.

Sometimes, so far as I can see, the information gained is useless. For example, going back to my previous post, one can apply the same logic in the upper left-hand corner of the diagram to find that the cells in column 3, rows 1 and 2, sum to 8, but this doesn't advance the cause at all.

Denis wrote,

My experience with hundreds of puzzles (classified as hard in the atk collection)

I've been meaning to ask about this. Do you just go to the website and manually copy the puzzles, or have you found a better way?

Website · by **denis_berthier** » Mon Mar 11, 2013 5:28 am

Hi Saul,
I'll take your questions in reverse order.

saul wrote:
Denis wrote:My experience with hundreds of puzzles (classified as hard in the atk collection)

I've been meaning to ask about this. Do you just go to the website and manually copy the puzzles, or have you found a better way?

Unfortunately, I have no better way than doing it manually. It could have been very frustrating. But, at the time I did it, a few months ago, I had a very good motivation.
As you may know, I first introduced all "my" chain rules (whips, braids, ...) in the context of Sudoku. Later, I showed that these rules (and the associated ratings) were meaningful for any finite CSP. Still later (and this was the reason why I started to write "Pattern-Based Constraint Satisfaction"), I showed that they could be concretely applied to various other CSPs: N-Queens, graph colouring, Futoshiki, Numbrix, Hidato.
Although the constraints are very different in nature in these puzzles, they still have a point in common: they are naturally binary.

In Kakuro, arithmetic constraints are highly non-binary (they can be up to 9-ary - or 8-ary if you consider the 45-in-9 as void).
There's a well known general technique for transforming any non-binary constraint into binary ones; but it is terribly inefficient in practice.
By introducing redundant CSP variables (representing combinations in the sectors), I thought I could solve at least the easy puzzles without doing any arithmetic (except of course the pre-computations replacing the sum constraints by the allowed combinations in the various sectors). As my purpose was only illustrative, I had planned to test this only with a few examples.
However, much to my surprise, the method was much more powerful than I expected and it also applied to hard puzzles. That's how I got very excited about it and I was led to spend on Kakuro much more time than I first expected. I thus tested hundreds of (mainly hard) examples (not all from atk, because I wanted to be sure they had nothing special that made them easier - indeed the atk hard ones are among the hardest I've found on the web, wrt to the W rating).

saul wrote:In the few examples I've looked at, the set of cells in the "surface" is indeed a cut set, but what then?

saul wrote:
Denis wrote:The question is, how to use them afterwards.
Sometimes, so far as I can see, the information gained is useless.

Yes, that's why I think the first step should be to state clearly which cases you want to consider (and to assemble a corresponding collection of puzzles).
As for me, for the reasons mentioned in the previous paragraphs, I was interested in a pattern-based, non-arithmetic solution. So I haven't explored all the possibilities of complex surface sums (and I don't mean to do it now, as I don't think they can be very useful). Indeed, in my book, I've considered only 1-cuts. (I've considered surface sums as an example of application-specific rules).

saul wrote:
Denis wrote:Detecting them is easy
Do you have a simple proof of this? I'm having trouble even coming up with the statement I want to prove. If the proof isn't simple, perhaps you could at least state the theorem for me.

If you mean a proof of the sum rules themselves, once the surface has been correctly defined, it's only commutativity and associativity of addition (sum of row sums = sum of column sums).
For 1-cuts, there are only two possibilities: there are either one or two sectors crossing the border of the surface at the cut point. The first case is easy; in the second case, you must consider differences.
For 2-cuts, it gets more complex as there are 4 possibilities. I haven't explored such cases, because I doubt they can be very useful. Maybe, if Bill has some experience of such cases, he could tell us more about them.

by **Smythe Dakota** » Wed Mar 13, 2013 9:28 am

Yes, I guess I've been using some of the "standard" techniques, without reading about them, and I've invented my own names. What you guys call a "surface sum" I call a "-ularity" of some degree or another -- singularity, doubularity, tripularity, etc. And I still don't know what an "n-cut" is.

There are "sum doubularities" where the two stick-outs are both horizontal or both vertical. In this case you know what the sum of the two cells is. There are also "difference doubularities", with one horizontal and one vertical stick-out. In this case you know what the difference is.

Tripularities work the same way. Either you know the sum of all three stick-outs, or you know the difference between one of them and the sum of the other two.

My favorite Kakuro puzzles are those by Michael Mepham. I find them to be just the right degree of difficulty and interest. Often there is a "sum tripularity" in one corner, typically with two white cells at r7c89, three at r9c789, and a niner (sum 45) at r8c123456789. In this case you know the sum of r8c789. Sometimes this is enough to solve that corner, sometimes not, but it is almost always useful to know the sum.

Some of the Mepham puzzles have four singularities, one fairly close to each corner, which divide the puzzle into five small independent puzzles (one in each corner, and one in the center). I suppose these would be considered too easy by most of you.

From time to time I even encounter a "global difference doubularity" -- two cells, in diametrically opposite positions, which divide the puzzle into two equal-sized, equal-shaped independent puzzles (you can fit the two pieces on top of each other by rotating one of them 180 degrees). These can be a bit tedious, though, adding up all those cells without making a mistake. In this case I usually perform both the horizontal and vertical additions on both sides of the puzzle, just to check my arithmetic. Sometimes it's worth the effort, sometimes not. (If the difference between the two cells is 8, it's definitely worth it.

)

denis_berthier wrote: .... It is more general than the examples you give, e.g. there may be black cells inside the surface (provided they carry clues).

What difference would it make if the black cells carry clues? The location of the clues is just an arbitrary convention. Instead of clues at the left or top of each word, they could just as easily be at the right or bottom.

If you rotate an entire puzzle 180 degrees, without changing any of the sums or numbers, you have the same puzzle you had before, but now the clues are in different places. Black cells carrying clues tend to become black cells not carrying clues, and vice versa.

Bill Smythe

Website · by **denis_berthier** » Wed Mar 13, 2013 10:49 am

Smythe Dakota wrote:Yes, I guess I've been using some of the "standard" techniques, without reading about them, and I've invented my own names. What you guys call a "surface sum" I call a "-ularity" of some degree or another -- singularity, doubularity, tripularity, etc. And I still don't know what an "n-cut" is.

In graph theory, an n-cut is a set of n vertices that disconnects the graph if you take them out.
For manual solving, you need not know this; but I spoke of this because Saul wanted a way of finding automatically potentially useful surfaces.

Smythe Dakota wrote:My favorite Kakuro puzzles are those by Michael Mepham.

Could you give an example that you consider as typical of his hardest ?

Smythe Dakota wrote:Some of the Mepham puzzles have four singularities, one fairly close to each corner, which divide the puzzle into five small independent puzzles (one in each corner, and one in the center). I suppose these would be considered too easy by most of you.

If there is a complete decomposition of the puzzle (i.e. you can solve each of them totally independently of the others), well ... that's independent puzzles.
What I've seen more often is only a partial decomposition (e.g. you must use the results of one puzzle to solve the other).

Smythe Dakota wrote:
denis_berthier wrote: there may be black cells inside the surface (provided they carry clues).
What difference would it make if the black cells carry clues?

My wording wasn't correct. I meant the sums of all the sectors intersecting the surface must be specified (so that horizontal and vertical sums can be done).
The reason why I say this is that, on some websites, Kakuro may have sectors with unspecified sums. I don't like this, but there's no standard. And, from a theoretical POV, it may not be absurd to allow sectors with unspecified sums, especially if you are interested in minimal sets of clues.

by **saul** » Wed Mar 13, 2013 3:52 pm

Denis wrote:

My wording wasn't correct. I meant the sums of all the sectors intersecting the surface must be specified (so that horizontal and vertical sums can be done).

I guess what you're saying is that in a situation like this, in the lower right-hand corner of the board:

the highlighted cell is a cut vertex, but deleting it gives no information, because we don't know anything about the cell in the lower right-hand corner. BTW, this seems to be a case where it makes sense to have an "unclued" sector, since a clue would be tantamount to specifying the value of the cell.

As to my questions about proving a theorem, this clarifies the issue for me. I was trying to find necessary and sufficient conditions so that removing the cut would give additional information, useful or not. Now I think that's a waste of time. Just find a cut and test it. If it gives no information, or the information isn't useful, look for the next cut.

Bill wrote:

]My favorite Kakuro puzzles are those by Michael Mepham.
<snip>
I suppose these would be considered too easy by most of you.

Is http://www.sudoku.org.uk/Puzzles/Kakuro.asp an example? I got here by googling "michael mepham" It's a nice puzzle, and certainly not "too easy" for me, but I don't like the user interface. The "pencil marks" are so small I have difficulty seeing them. Also, once a cell on the lower or right-hand edge has been highlighted once, it remains highlighted forever. So, if you put pencil marks in one of these cells and want to go back and modify them, you get no visual confirmation that you're working on the right cell. Also, after I completed the puzzle and clicked the "Check now" button, nothing happened. I do like his input method a lot better than atk's, though I prefer to use the keyboard.

Denis, I was interested in your remarks, in your previous post, on applying your techniques to non-binary puzzles. Have you tried slither link? If each edge is represented by a boolean variable, the constraints given by the numbers would be quaternary. Also, for the edges meeting at a vertex, either two or zero of them must be 1, so we can say that the sum is less than 3 and not equal to one. In general, these would be quaternary constraints, but at the edges of the board they would be ternary, and binary at the corners.

The complication is the requirement that the solution consists of a single loop; the constraints above only ensure that we get a union of disjoint loops. It seems that you would have to generate all solutions and then reject the ones with multiple loops, but there are lots of incorrect solutions. For any cell not adjacent to a number, and not adjacent to the correct solution, we could add all its edges and satisfy the constraints. You would probably want to add a constraint for each cell to avoid this. But what about rectangles consisting of two cells? This would take some experimentation with actual puzzles.

Of course, this is "generate and test," and rather than finding all solutions, one would like to test the partial solutions to check that no loop had been created. I don't know if that fits into the CSP paradigm at all.

Would your techniques apply to slither link, do your think?

By the way, you guys obviously know how to quote automatically from prior posts so that the author is indicated, but I have been doing it manually. Can you tell me the secret?

Website · by **denis_berthier** » Wed Mar 13, 2013 6:06 pm

saul wrote:
Denis wrote:My wording wasn't correct. I meant the sums of all the sectors intersecting the surface must be specified (so that horizontal and vertical sums can be done).

I guess what you're saying is that in a situation like this, in the lower right-hand corner of the board ...

I meant that there may be islands of black cells inside the white surface, but the rightmost and lowermost cells of each island must have clues for the sectors they control.

saul wrote:Denis, I was interested in your remarks, in your previous post, on applying your techniques to non-binary puzzles. Have you tried slither link?

No, I've never tried.

saul wrote:The complication is the requirement that the solution consists of a single loop; [...] I don't know if that fits into the CSP paradigm at all. Would your techniques apply to slither link, do your think?

I don't know. The problem formulation is not standard CSP. But, perhaps, one can find a model that turns it into a CSP.
In Numbrix or Hidato, although there's also a global path constraint, I found a way to apply my method. For Slitherlink, it seems to be less obvious.

saul wrote:By the way, you guys obviously know how to quote automatically from prior posts so that the author is indicated, but I have been doing it manually. Can you tell me the secret?

When you want to answer a post written by xxx, you select "quote" on the upper right-hand side. You get something like
[ quote="xxx"] text of the whole post [ /quote], without spaces after the "["
Generally, you want to answer only parts of the post.
You can split it into as many parts as needed, provided you enclose each of them in the same square brackets:
[ quote="xxx"] part of the post [ /quote].
You can use "Preview" before "Submit" to check that you get the desired result.

by **Smythe Dakota** » Sat Mar 16, 2013 11:24 am

Yes, just select "quote" at the top of the post, rather than "post reply" at the bottom.

If you are quoting multiple times from the same post, you can edit the [ quote="xxx"] down to just [ quote] on all but the first occurrence, if you like the way that looks. (No reason to repeat the author's name each time.)

If you want to quote from two different posts (by the same or different authors), you can pretend to quote the first post, then capture it to the clipboard, then use the browser's back-arrow key without submitting. Then quote the second post, place the cursor at either the end or the beginning of the reply window, and paste in the other quote.

The details:

Select "quote" at the top of the first post you want to quote.
Locate the cursor anywhere inside the reply window.
Press control-A, highlighting the entire reply window.
Press control-C to copy the highlighted area to the clipboard. (You will not see any visual change by pressing control-C, but you still have to do it.)
Do not submit. Instead, use your browser's back-arrow button to return to the previous page.
Locate the second post and select "quote" at the top of it.
In the reply window, locate the cursor at either the end or the beginning (depending on which order you wish the quotes to appear).
Press control-V to paste. Bingo!

Bill Smythe

by **Smythe Dakota** » Sat Mar 16, 2013 12:54 pm

I wrote: .... My favorite Kakuro puzzles are those by Michael Mepham. ....

In response, denis_berthier wrote: .... Could you give an example that you consider as typical of his hardest ? ....

And saul wrote: .... Is http://www.sudoku.org.uk/Puzzles/Kakuro.asp an example? ....

Yes, although I prefer to get there via http://www.sudoku.org.uk/kakuroflash/kakuro.html, which omits the big heading at the top. That site, whichever way you get to it, presents a new puzzle every day, and (did you notice?) you can scroll back up to 10 days, using the little down-arrow in the lower left corner.

Those puzzles are graded G on Monday and Tuesday, M on Wednesday and Thursday, T on Friday and Saturday, and D on Sunday. I suppose those stand for Gentle, Medium, Tough, and Difficult, or something like that.

I don't care for the user interface either, but it doesn't matter because I prefer to print them out and solve them on paper. That's one reason I prefer the "kakuroflash" over the "puzzles" URL. You should print in Landscape mode to make the diagram slightly larger.

denis_berthier wrote: .... on some websites, Kakuro may have sectors with unspecified sums. I don't like this ....

I have never seen this, but I'm sure I wouldn't like it either. Give me those singularities, doubularities, and tripularities!

Related to this, saul wrote: .... I guess what you're saying is that in a situation like this, in the lower right-hand corner of the board:

the highlighted cell is a cut vertex, but deleting it gives no information .... this seems to be a case where it makes sense to have an "unclued" sector, since a clue would be tantamount to specifying the value of the cell. ....

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.

Bill Smythe

The New Sudoku Players' Forum

Can You Solve This Without Trial and Error?

Re: Can You Solve This Without Trial and Error?

Re: Can You Solve This Without Trial and Error?

Re: Can You Solve This Without Trial and Error?

Re: Can You Solve This Without Trial and Error?

Re: Can You Solve This Without Trial and Error?

Re: Can You Solve This Without Trial and Error?

Re: Can You Solve This Without Trial and Error?

Re: Can You Solve This Without Trial and Error?

Re: Can You Solve This Without Trial and Error?

Re: Can You Solve This Without Trial and Error?

Re: Can You Solve This Without Trial and Error?

Re: Can You Solve This Without Trial and Error?

Re: Can You Solve This Without Trial and Error?

Re: Can You Solve This Without Trial and Error?

Re: Can You Solve This Without Trial and Error?