Can You Solve This Without Trial and Error?

For fans of Kakuro

Re: Can You Solve This Without Trial and Error?

Postby saul » Sun Feb 24, 2013 3:15 pm

Thanks. I'm not really interested in the linear programming solution to Kakuro either, since it cannot show uniqueness. Besides, I'm primarily interested in this as an amusing puzzle, and linear programming is not relevant to that. (I did find a quadratic objective function. If n[d] is the number of times d occurs in a given sector, then n[d](n[d]-1) will be 0 iff d isn't repeated. Sum over all digits d and over all sectors to get the function to minimize. I don't know anything about quadratic programming, though; in particular, I don't know if there has been any progress on integer quadratic programming. I'm done thinking about this, however.)

Denis wrote:
BTW, which surface rule did you use to conclude that r3c7 = 2 ?

Well, by then I has deduced the values in the sector r4c10 through r4c12, and also the value in r5c10, so there was an easy surface sum available, consisting of the top two sectors on the right-hand side of the board.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Mon Feb 25, 2013 4:08 am

saul wrote:I did find a quadratic objective function. If n[d] is the number of times d occurs in a given sector, then n[d](n[d]-1) will be 0 iff d isn't repeated. Sum over all digits d and over all sectors to get the function to minimize.

n(d) is not linear in d.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby saul » Mon Feb 25, 2013 8:56 am

No, it's linear in the x[r][c][k].
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby 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.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby 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 Image
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.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby 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
***** KakuRules 1.2 based on CSP-Rules 1.2, config: W *****
horizontal magic sector 3-in-2, starting in r2c5, unique combination: 12
horizontal magic sector 7-in-3, starting in r3c1, unique combination: 124
horizontal magic sector 35-in-5, starting in r4c3, unique combination: 56789
vertical magic sector 3-in-2, starting in r1c3, unique combination: 12
vertical pseudo magic sector 36-in-7, starting in r1c4, for digits: (9)
vertical pseudo magic sector 38-in-7, starting in r1c6, for digits: (7 8 9)
vertical magic sector 4-in-2, starting in r6c7, unique combination: 13
vertical magic sector 3-in-2, starting in r6c8, unique combination: 12
naked-singles ==> r3c2 = 4, vr1c2 = 48, r2c2 = 8
ctr-to-horiz-sector ==> r2c4 <> 9
ctr-to-horiz-sector ==> r2c4 <> 4
cell-to-horiz-ctr ==> hr2c1 <> 358
ctr-to-horiz-sector ==> r2c4 <> 3
ctr-to-horiz-sector ==> r2c4 <> 5
cell-to-horiz-ctr ==> hr8c5 <> 246
cell-to-horiz-ctr ==> hr8c5 <> 345
cell-to-verti-ctr ==> vr3c5 <> 234
ctr-to-verti-sector ==> r5c5 <> 4
ctr-to-verti-sector ==> r6c5 <> 4
cell-to-verti-ctr ==> vr2c8 <> 34
ctr-to-verti-sector ==> r3c8 <> 3
ctr-to-verti-sector ==> r3c8 <> 4
naked-pairs-in-a-row r4{c5 c8}{n5 n6} ==> r4c7 <> 6
cell-to-verti-ctr ==> vr1c7 <> 1346
naked-pairs-in-a-row r4{c5 c8}{n5 n6} ==> r4c7 <> 5
cell-to-verti-ctr ==> vr1c7 <> 2345
cell-to-verti-ctr ==> vr1c7 <> 1256
ctr-to-verti-sector ==> r3c7 <> 5
ctr-to-verti-sector ==> r3c7 <> 6
ctr-to-verti-sector ==> r5c7 <> 5
ctr-to-verti-sector ==> r5c7 <> 6
naked-pairs-in-a-row r4{c5 c8}{n5 n6} ==> r4c6 <> 6, r4c6 <> 5, r4c4 <> 6, r4c4 <> 5
biv-chain[2]: c8n1{r7 r8} - c7n1{r8 r7} ==> hr7c5 <> 235, r7c6 <> 1
biv-chain[2]: vr2c8{n16 n25} - r4c8{n6 n5} ==> r3c8 <> 5
cell-to-horiz-ctr ==> hr3c5 <> 345
biv-chain[2]: vr3c5{n126 n135} - r4c5{n6 n5} ==> r6c5 <> 5, r5c5 <> 5
biv-chain[2]: hr2c1{n178 n268} - r2c3{n1 n2} ==> r2c4 <> 2
biv-chain[2]: r2c3{n1 n2} - hr2c1{n178 n268} ==> r2c4 <> 1
biv-chain[2]: vr1c7{n1238 n1247} - r4c7{n8 n7} ==> r5c7 <> 7, r3c7 <> 7
whip[2]: c7n1{r8 r7} - c8n1{r7 .} ==> r8c6 <> 1
whip[2]: r4c7{n8 n7} - vr1c7{n1238 .} ==> r3c7 <> 8
whip[2]: r4c8{n6 n5} - vr2c8{n16 .} ==> r3c8 <> 6
whip[2]: r3c8{n2 n1} - r3c7{n1 .} ==> hr3c5 <> 156
ctr-to-horiz-sector ==> r3c6 <> 5
whip[2]: r4c5{n6 n5} - vr3c5{n126 .} ==> r5c5 <> 6
whip[2]: r4c7{n8 n7} - vr1c7{n1238 .} ==> r5c7 <> 8
whip[2]: r4c5{n6 n5} - vr3c5{n126 .} ==> r6c5 <> 6
whip[2]: hr7c1{n126 n135} - r7c2{n4 .} ==> r7c4 <> 5
whip[2]: hr7c1{n126 n234} - r7c2{n5 .} ==> r7c4 <> 4
whip[2]: hr7c1{n126 n135} - r7c2{n4 .} ==> r7c3 <> 5
whip[2]: hr7c1{n126 n234} - r7c2{n5 .} ==> r7c3 <> 4
whip[2]: r7c3{n6 n3} - hr7c1{n126 .} ==> r7c2 <> 6
cell-to-horiz-ctr ==> hr7c1 <> 126
ctr-to-horiz-sector ==> r7c3 <> 6
naked-singles ==> r7c3 = 3, vr4c3 = 3789
ctr-to-horiz-sector ==> r7c4 <> 6
cell-to-horiz-ctr ==> hr8c2 <> 46
ctr-to-horiz-sector ==> r8c4 <> 4
ctr-to-horiz-sector ==> r8c4 <> 6
cell-to-verti-ctr ==> vr5c2 <> 67
ctr-to-verti-sector ==> r6c2 <> 6
ctr-to-verti-sector ==> r6c2 <> 7
naked-pairs-in-a-column c4{r3 r7}{n1 n2} ==> r8c4 <> 2
horiz-sector-to-ctr ==> hr8c2 <> 28
ctr-to-horiz-sector ==> r8c3 <> 8
ctr-to-horiz-sector ==> r8c4 <> 8
naked-pairs-in-a-column c4{r3 r7}{n1 n2} ==> r8c4 <> 1
horiz-sector-to-ctr ==> hr8c2 <> 19
naked-singles ==> hr8c2 = 37, r8c3 = 7, r8c4 = 3
cell-to-horiz-ctr ==> hr5c2 <> 24567
naked-pairs-in-a-column c4{r3 r7}{n1 n2} ==> r6c4 <> 2, r6c4 <> 1, r5c4 <> 2, r5c4 <> 1
biv-chain[2]: r7c2{n4 n5} - vr5c2{n49 n58} ==> r6c2 <> 4
biv-chain[2]: vr5c2{n49 n58} - r7c2{n4 n5} ==> r6c2 <> 5
naked-pairs-in-a-row r6{c2 c3}{n8 n9} ==> r6c6 <> 9, r6c6 <> 8, r6c4 <> 9, r6c4 <> 8
biv-chain[2]: r6c3{n8 n9} - r6c2{n9 n8} ==> hr6c1 <> 34579, hr6c1 <> 24679, hr6c1 <> 15679
biv-chain[2]: r3c4{n1 n2} - r7c4{n2 n1} ==> vr1c4 <> 2345679
whip[2]: r6c2{n9 n8} - r6c3{n8 .} ==> hr6c1 <> 25678, hr6c1 <> 34678
whip[2]: hr6c1{n14689 n13789} - r6c4{n4 .} ==> r6c6 <> 7
whip[2]: r7c4{n2 n1} - r3c4{n1 .} ==> vr1c4 <> 1345689
naked-single ==> vr1c4 = 1236789
cell-to-horiz-ctr ==> hr6c1 <> 24589
ctr-to-horiz-sector ==> r6c6 <> 5
naked-pairs-in-a-column c4{r2 r6}{n6 n7} ==> r5c4 <> 7, r5c4 <> 6
naked-pairs-in-a-row r5{c3 c4}{n8 n9} ==> r5c6 <> 9, r5c6 <> 8
naked-pairs-in-a-column c4{r2 r6}{n6 n7} ==> r4c4 <> 7
biv-chain[2]: r5c3{n8 n9} - r5c4{n9 n8} ==> hr5c2 <> 23469, hr5c2 <> 13569, hr5c2 <> 13479, hr5c2 <> 12579
whip[2]: r5c3{n9 n8} - r5c4{n8 .} ==> hr5c2 <> 12678, hr5c2 <> 23478, hr5c2 <> 13578
ctr-to-horiz-sector ==> r5c6 <> 7
whip[2]: r5c4{n9 n8} - r5c3{n8 .} ==> hr5c2 <> 23568
ctr-to-horiz-sector ==> r5c5 <> 3
ctr-to-horiz-sector ==> r5c6 <> 3
ctr-to-horiz-sector ==> r5c7 <> 3
whip[2]: r5c4{n9 n8} - r5c3{n8 .} ==> hr5c2 <> 14568
naked-single ==> hr5c2 = 12489
whip[2]: r6c4{n6 n7} - hr6c1{n23689 .} ==> r6c6 <> 6
whip[2]: r7c8{n2 n1} - r7c7{n1 .} ==> hr7c5 <> 145
ctr-to-horiz-sector ==> r7c6 <> 4
ctr-to-horiz-sector ==> r7c6 <> 5
whip[2]: r8c8{n2 n1} - r8c7{n1 .} ==> hr8c5 <> 147
ctr-to-horiz-sector ==> r8c6 <> 4
whip[2]: r8c8{n2 n1} - r8c7{n1 .} ==> hr8c5 <> 156
ctr-to-horiz-sector ==> r8c6 <> 5
ctr-to-horiz-sector ==> r8c6 <> 6
verti-sector-to-ctr ==> vr1c6 <> 1256789
verti-sector-to-ctr ==> vr1c6 <> 2345789
singles to the end (for ordinary, hrc and vrc CSP variables)
GRID SOLVED. rating-type = W, MOST COMPLEX RULE = Whip[2]
--------
-826-12-
-412-642
---86975
--89241-
-89713--
-531-712
--73-831
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby 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.

Image

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
Smythe Dakota
 
Posts: 533
Joined: 11 February 2006

Re: Can You Solve This Without Trial and Error?

Postby 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)
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby 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
Smythe Dakota
 
Posts: 533
Joined: 11 February 2006

Re: Can You Solve This Without Trial and Error?

Postby 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).
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby 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.

Image

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?
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby 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.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby 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
Smythe Dakota
 
Posts: 533
Joined: 11 February 2006

Re: Can You Solve This Without Trial and Error?

Postby 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.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby 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:
Image
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?
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Next

Return to Kakuro