Can You Solve This Without Trial and Error?

For fans of Kakuro

Re: Can You Solve This Without Trial and Error?

Postby saul » Thu Apr 04, 2013 4:14 pm

That explains the confusion; I'm going to have to think about the implications.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby Smythe Dakota » Thu Apr 11, 2013 12:41 am

Today's Michael Mepham puzzle at http://www.sudoku.org.uk/kakuroflash/kakuro.html -- April 10, 2013 -- is an example of a puzzle with four singularities (I guess the rest of you call these "1-cuts"), one near each corner, thus dividing the puzzle into five much smaller puzzles. (I told you Mepham does this every so often, remember?)

These puzzles only stay up for nine days, so if you want a looksee, look before April 19, 2013.

Bill Smythe
Smythe Dakota
 
Posts: 533
Joined: 11 February 2006

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Thu Apr 11, 2013 6:12 am

Smythe Dakota wrote:Today's Michael Mepham puzzle at http://www.sudoku.org.uk/kakuroflash/kakuro.html -- April 10, 2013 -- is an example of a puzzle with four singularities (I guess the rest of you call these "1-cuts"), one near each corner, thus dividing the puzzle into five much smaller puzzles.


In order to keep a reference to it after April 10, I copy it here: http://www.carva.org/denis.berthier/Misc/M-10-04-2013.png

Yes, there are four 1-cuts and they are of the simplest kind: only one cell outside the surface. Moreover, each of the four sub puzzles is independently solvable (3 by Singles and 1 in W2); after this, the remaining cells in the center can be solved by Singles.

Without using surface sums, the puzzle is solvable in W3. Each of the two whips[3] that appear in the resolution path lie entirely in a single sector (this is always the case for whips[2]). This means that the original puzzle can easily be solved by propagating constraints sector by sector.

One interesting point is that, even if the original puzzle has no 1-cell sector, such sectors may appear in the sub puzzles. That's one of the reasons why I kept the possibility of 1-cell sectors in my solver.

By combining small surfaces, one can build arbitrarily large puzzles. IMO, as surfaces are obvious to see, such totally decomposable puzzles are of little interest. One thing I like with atk is that, most of the time, they avoid decomposable puzzles.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby Smythe Dakota » Thu Apr 11, 2013 10:15 am

It happened again today -- April 11, 2013.

Bill Smythe
Smythe Dakota
 
Posts: 533
Joined: 11 February 2006

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Fri Apr 12, 2013 5:03 am

Smythe Dakota wrote:It happened again today -- April 11, 2013.

A copy is here: http://www.carva.org/denis.berthier/Misc/M-11-04-2013.png

At first sight, the two puzzles look much alike.
I didn't try to decompose the second into four independent surfaces as the first.

But the whole puzzle can be solved using only Singles and the obvious coupling rules (which are whips[1]) between candidates (digits) in white cells and candidates (combinations) for their sector.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby saul » Fri Apr 12, 2013 1:27 pm

denis_berthier wrote:One thing I like with atk is that, most of the time, they avoid decomposable puzzles.


But not always. M21161 is an example that decomposes into a large number of small puzzles. I call puzzles like this "dragons" because the white cells remind me of the dragon in a Chinese New Year's parade. I don't find these much fun to do, though.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Fri Apr 12, 2013 2:04 pm

saul wrote:M21161 is an example that decomposes into a large number of small puzzles.


One more example that can be solved (when not using the obvious surface sums) by whips[2] plus a unique whips[3] lying in a single sector.
I don't have large samples of puzzles with surface sums, but, from those I've seen , it seems the universal W rating remains a good indicator of their difficulty.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby saul » Sun Apr 14, 2013 12:43 am

Here's an interesting puzzle. (I number only rows and columns with white cells, starting at 1.)

Image
According to my way of thinking, r6c2 and r2c6 give a 2-cut, although if I understand it right, Denis would say that r6c2 gives a 1-cut (or a singularity as Bill would say). Regardless of terminology, we get
r2c6 - (r6c2 + r7c2) = 1.

The only possibilities are
1) r2c6 = 5, r6c2 = 1, r7c2 = 3
2) r2c6 = 8, r6c2 = 3, r7c2 = 4

and we can eliminate 2 candidates for r6c2:

Image

Now in any possible combination making 36 in 7, there are exactly 3 numbers from the set 1234, so these must come from r3, r6 and r7, and we can eliminate the candidates 1234 in r4. I've used this kind of argument before, but it never struck me until now that this is neither a hidden nor a naked triple nor quadruple; I don't think I've ever seen it described. Have you noted this in your book, Denis? Does it have a name?
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Sun Apr 14, 2013 5:10 am

saul wrote:According to my way of thinking, r6c2 and r2c6 give a 2-cut, although if I understand it right, Denis would say that r6c2 gives a 1-cut

no, two cells => 2-cut

saul wrote:Now in any possible combination making 36 in 7, there are exactly 3 numbers from the set 1234, so these must come from r3, r6 and r7, and we can eliminate the candidates 1234 in r4. I've used this kind of argument before, but it never struck me until now that this is neither a hidden nor a naked triple nor quadruple; I don't think I've ever seen it described. Have you noted this in your book, Denis? Does it have a name?

No, I don't remember seeing this mentioned anywhere on the web.
And no, I don't mention it in my book either (BTW, as it is now available in pdf on arxiv.org http://arxiv.org/abs/1304.1628, you can easily read the Kakuro chapter).
The closest thing I've done is introducing pseudo-magic digits, i.e. digits that appear in all the combinations of a sector. They can be used in Hidden or Super-Hidden Subsets.
Probably we should give it more thought. I had noticed (and maybe also read on the web) that sets of combinations for some (S, p) pairs are "decomposable", but I hadn't tried to do anything with this. Your remark may open a way of using this to introduce more Hidden Subsets. As most Subsets are subsumed by whips, I don't think it would provide much more resolution power, but some people prefer Subsets.

Notice that, in your example, the same eliminations are available via several whip patterns, for whips lying completely in the only vertical sector in column c2. In your notations for rows and columns (and starting from your last PM - in which many candidates could be eliminated by much simpler rules):
whip[4]: r6c2{n1 n3} - r7c2{n3 n4} - r3c2{n4 n2} - vr4c0{ .} => r4c2 <> 1
I let you write similar ones for the other eliminations.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby Smythe Dakota » Fri Apr 19, 2013 11:22 am

Image
saul wrote:According to my way of thinking, r6c2 and r2c6 give a 2-cut, although if I understand it right, Denis would say that r6c2 gives a 1-cut (or a singularity as Bill would say). ....

I don't see how it's justified to call r6c2 a 1-cut, nor r6c2 and r2c6 a 2-cut.

To be sure, if you cut around all four sides of r6c2 with scissors, and do the same with r2c6, the remaining puzzle will immediately come apart into two disjoint pieces of paper.

But, in Kakuro, a word doesn't come apart just because you slice out one of the cells in the middle of the word! The remaining cells in the word are still connected mathematically, even if not physically.

For this reason, I find the terms "1-cut" and "2-cut" misleading. They have a different meaning in Kakuro than in graph theory (or whatever branch of mathematics those terms come from). Accordingly, I think I'll stick with "singularity", "doubularity", etc.

Given that, in the diagram, r2c7,r3c7,r5c1,r6c1 are all solved, you could call r1c6,r2c6,r6c2,r7c2 a "quadrupularity". The difference (r1c6+r2c6) - (r6c2+r7c2) is known. And since r1c6 is solved, you could even call the remaining three cells a "tripularity". I call it a "difference tripularity" because, unlike a "sum tripularity" where the sum of the three is known, here you know the difference between one of them and the sum of the other two.

Bill Smythe
Smythe Dakota
 
Posts: 533
Joined: 11 February 2006

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Fri Apr 19, 2013 2:14 pm

Smythe Dakota wrote:To be sure, if you cut around all four sides of r6c2 with scissors, and do the same with r2c6, the remaining puzzle will immediately come apart into two disjoint pieces of paper.
But, in Kakuro, a word doesn't come apart just because you slice out one of the cells in the middle of the word! The remaining cells in the word are still connected mathematically, even if not physically.
For this reason, I find the terms "1-cut" and "2-cut" misleading. They have a different meaning in Kakuro than in graph theory (or whatever branch of mathematics those terms come from).

1-cut and 2-cut do come from graph theory. I introduced them in Kakuro (in my last book) for the purpose of formalising (e.g. for programming them) physical cell patterns (independent of the values of the digits in them) that can easily be spotted (by human eyes) and that have a POTENTIAL application to surface sums. It's obvious that they are not sufficient conditions, but they are necessary ones.
Before you can write any of your n-ularities, you have to find some k-cut.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby saul » Fri Apr 19, 2013 3:01 pm

Smythe Dakota wrote:
Image
saul wrote:According to my way of thinking, r6c2 and r2c6 give a 2-cut, although if I understand it right, Denis would say that r6c2 gives a 1-cut (or a singularity as Bill would say). ....

I don't see how it's justified to call r6c2 a 1-cut, nor r6c2 and r2c6 a 2-cut.

My mistake. I should have said, "According to my way of thinking, r6c2, r7c2, and r2c6 give a 3-cut." I thought something was fishy when I was writing the email, because I was able to make an inference about a cell not in the cut, but I was in a hurry, and my main interest was in the new (or newly recognized) inference rule. My view of the matter is (provisionally) the same as yours, and I'm still trying to come to terms with Denis's view. I really need to find the time to read his book! In any event, Denis and I are using the term "cut" in exactly the same way, but we're talking about different graphs. It isn't a matter of one being right and the other wrong, but of which is more useful for programming. Perhaps each is more useful for attacking a different aspect of the problem.

When you talk about cells being connected even if they aren't physically adjacent, you're talking about the same graph model that I'm using.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby Smythe Dakota » Sat Apr 20, 2013 11:55 am

saul wrote: .... My mistake. I should have said, "According to my way of thinking, r6c2, r7c2, and r2c6 give a 3-cut." ....

Yes, now you and I are on the same page.

But I don't think either of us is quite on the same page as Denis. And in my case, I probably never will be. He is obviously the expert among us. I regard myself as a recreational solver, not interested in any puzzle that takes more than 2 hours to solve manually.

There aren't many recreational solvers on these forums. Most recreational solvers don't bother to speak out. I guess I'm enough of a blabbermouth to be the exception.

Most posters here are heavily into Advanced Solving Techniques, with names like Flying Turtle Chicken Wings, Semi-Masked Non-Negotiable Triples, and Jelly Fish Nets. That's not for me. When solving becomes a chore, or a task for a computer program, I've left the scene.

Speaking of recreational solving, the Michael Mepham site recently has had a rash of puzzles with four singularities, one near each corner, that divide the puzzle into five independent puzzles. The four entries on April 11-12-15-16, 2013, have all been in this category. And the puzzle on April 17 actually had six singularities. On April 19 there was a global difference doubularity, i.e. two cells diametrically opposite each other which divide the entire puzzle into two equal-size, same-shape sub-puzzles. You know the difference between the two cells if you want to do a whole bunch of adding (and checking, to make sure you added correctly). The one on April 13, likewise, had a global difference doubularity, along with two "regular" sum doubularities.

Bill Smythe
Smythe Dakota
 
Posts: 533
Joined: 11 February 2006

Re: Can You Solve This Without Trial and Error?

Postby saul » Sun Apr 21, 2013 5:02 pm

Smythe Dakota wrote: That's not for me. When solving becomes a chore, or a task for a computer program, I've left the scene.
Bill Smythe


I agree. I'm a recreational solver too. I'm interested in a computer solver not so that I can solve puzzles too difficult to do by hand, but because I want to develop a program that will give me hints, and allow me to become a better recreational solver. I'm not interested in any techniques that are too difficult to apply manually.
Of course, I program for recreation, too.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Sun Apr 21, 2013 5:04 pm

Smythe Dakota wrote:Speaking of recreational solving, the Michael Mepham site recently has had a rash of puzzles with four singularities, one near each corner, that divide the puzzle into five independent puzzles. The four entries on April 11-12-15-16, 2013, have all been in this category. And the puzzle on April 17 actually had six singularities. On April 19 there was a global difference doubularity, i.e. two cells diametrically opposite each other which divide the entire puzzle into two equal-size, same-shape sub-puzzles. You know the difference between the two cells if you want to do a whole bunch of adding (and checking, to make sure you added correctly). The one on April 13, likewise, had a global difference doubularity, along with two "regular" sum doubularities.

Which techniques do you use when surface sums are not available or don't allow you to go very far?
Did you try e.g. the April 14 puzzle? If so, did you find it difficult?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Kakuro