Can You Solve This Without Trial and Error?

For fans of Kakuro

Re: Can You Solve This Without Trial and Error?

Postby saul » Thu Jun 13, 2013 3:05 pm

denis_berthier wrote:
saul wrote: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.

Well, I haven't read the whole book. I meant I didn't understand what you were saying about surface sums in this thread.

It's clear that it isn't a complete model for surface sums. It doesn't capture, for example, two-cuts (in the sense that Bill and i use the term) where the two cells in the cut aren't adjacent; for example, what Bill calls "difference doublarities." I did a puzzle just yesterday that I solved with a two-cut of this sort, although it was a sum, not a difference.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby Smythe Dakota » Fri Jun 14, 2013 2:31 am

saul wrote: .... for example, what Bill calls "difference doublarities." I did a puzzle just yesterday that I solved with a two-cut of this sort, although it was a sum, not a difference.

Yes, it's entirely possible for a sum doubularity, too, to consist of non-adjacent cells, and even those not in the same word.

Imagine a U-shaped region, such as r8c345, r7c345, r6c3, r6c5, with other stuff going off to the left and right on r6. Then r6c3 and r6c5 constitute a sum doubularity, without being in the same word.

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

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Fri Jun 14, 2013 4:26 am

From what you both describe, I think I'd have a 2-cut, but I could be more precise with a pic.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Sun Jun 16, 2013 6:43 am

Hi, Saul & Bill,

Could you have a look at atk H2771 ?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby saul » Sun Jun 16, 2013 3:15 pm

denis_berthier wrote:Hi, Saul & Bill,

Could you have a look at atk H2771 ?


OK, I was able to solve this without trial and error. There were no surface sums. I don't see why this is classified as hard. It took between 1 and 2 hours, just because of the size. There was only one point where I used what I think of as an "advanced" technique. The only possible places for the 9 in the 45's in columns 8 and 9 had both been reduced to row 6 or row 10. Therefore, there had to be a 9 in one of those columns in both of those rows, and the 9's in other columns in those rows (and the same word) could be eliminated. I think this is one of the sudoku fish, but I've never even tried to learn those names.

It's certainly easier than a lot of "medium" atk puzzles.

Why did you call it to our attention, Denis? Was it just this classification question?
Last edited by saul on Sun Jun 16, 2013 4:18 pm, edited 1 time in total.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Sun Jun 16, 2013 3:25 pm

saul wrote:There was only one point where I used what I think of as an "advanced" technique. The only possible places for the 9 in the 45's in columns 8 and 9 had both been reduced to row 6 or row 10. Therefore, there had to be a 9 in one of those columns in both of those rows, and the 9's in other columns in those rows (and the same word) could be eliminated. I think this is one of the sudoku fish

yes, X-wing, a kind of fish.

saul wrote:Why did you call it to our attention, Denis? Was it just this classification question?

Yes, just to make sure we kept similar ideas of simplicity for large puzzles.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby saul » Thu Jun 20, 2013 5:51 pm

Here's an interesting series of inferences, I think.

In this position

Image

it's easy to see that r1c6 + r2c6 = 9. Indeed, I've already used this fact to deduce the values of the 3 known cells in the upper right-hand corner, as well as to eliminate some candidates in the surrounding cells. Now, if r4c6 = 5 or 6, then r6c6 = 6 or 5, and r1c6 + r2c6 = 7, contradiction. So, we eliminate two candidates from r4c6, and then we can see that row 4, as a 40 in 7, has exactly 2 cells less than 5, which must be in r4c1 and r4c6, so 1234 can be eliminated from all other cells in this row, giving

Image

From here on the puzzle is straightforward, although I used both the surface sum above and r4c1 + r4c6 = 5 again.

BTW, I also used an X-wing earlier in the solution, but it only eliminated one cell, and i'm not sure that it contributed materially to the solution. The inferences I noted here are available much earlier in the solution, but I don't going looking for recondite things until I've exhausted the obvious ones. (Well, the ones that are obvious to me.)

On another subject, typing "the upper right-hand corner" is tedious. From now on, I will call it the "northeast corner" or "NE corner" if no one minds.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Fri Jun 21, 2013 3:55 am

saul wrote:it's easy to see that r1c6 + r2c6 = 9.

A typical application of a 1-cut.

saul wrote:On another subject, typing "the upper right-hand corner" is tedious. From now on, I will call it the "northeast corner" or "NE corner" if no one minds.

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 Jun 21, 2013 6:18 am

denis_berthier wrote:
saul wrote:it's easy to see that r1c6 + r2c6 = 9.

A typical application of a 1-cut.

Of course. It's the part after that I found unusual, at least for me.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Fri Jun 21, 2013 8:03 am

saul wrote: It's the part after that I found unusual, at least for me.

OK, but I have nothing special to say about it. This puzzle is in W2, there are many ways to solve it.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Fri Jun 21, 2013 8:05 am

I think you may be interested by H11122.
There seems to be many cuts. But can many of them be used to simplify the puzzle ?
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 Jun 22, 2013 11:47 am

denis_berthier wrote:I think you may be interested by H11122. ....

Right on! This one is a -ularity lover's dream. There is a singularity at r4c4 (or, if you prefer, at r5c5) and another at its SE counterpart. (Yes, I like those directional abbreviations, too!) Also, there are tripularities at both ends of r7.

There is an entire circular chain of doubularities (four sum doubularities and four difference doubularities) at r7c6-r2c8-r3c10-r5c11-r7c8 and back around through the bottom half to r7c6 again. One of these, the sum doubularity at r7c6-r2c8, leads to the (almost) immediate conclusion that r2c8 must be 1 or 2. Thus, every cell in the entire chain must be one of two consecutive values (such as 2 or 3, or 5 or 6). The cell that cracks the case (and solves the entire chain) is r5c11, which can take on only one of its two possible values.

That's why I find kakuro so much more interesting than sudoku. You almost invent a whole new solving technique every time you solve a puzzle! You don't get stuck in a rut so much.

Incidentally, there is also a "global difference doubularity" at r7c6-r7c8. These two cells divide the entire puzzle into two equal-sized, same-shape pieces. (Rotational symmetry.) But you'd have to do a lot of arithmetic (with many chances for errors, including data entry errors if you use a calculator or computer) to arrive at the same conclusion you'd reach through the chain, and without the ancillary benefits as above. Note, also, that this global difference doubularity consists essentially of two diamatrically opposite points on the original 8-cell circle.

Now this is an interesting puzzle!

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

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Sat Jun 22, 2013 2:20 pm

Hi Bill,

I thought you'd be interested. If I find more, I'll tell you; but this kind is very rare in the hard ones.


I have a very different approach of the solution:

- the NW sub-puzzle cut out by cell r5c5 can be solved in a way totally independent of the rest (once the surface sum has been applied)

- the symmetric SE sub-puzzle cut out by cell r9c9 can also be solved in a way totally independent of the rest

- the central puzzle that remains after cutting out
    the above NW and SE sub-puzzles,
    the small 2x2 NE and SW sub-puzzles,
    the central W and E sub-puzzles
and applying the relevant surface sums to define the sums for its sectors
can also be solved independently of the rest; this is the closest thing I have to your chain of n-ularities.

Code: Select all
--------------
---------98---
--------264---
-------56-378-
-------91--59-
------98--68--
------17-31---
----895-248---
----42-51-----
---32--76-----
--79--54------
--654-12------
----362-------
----25--------
(first black row and column and black cells are displayed as "-")


Once these 3 sub-puzzles are solved, the rest is solvable by singles.
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 Jun 22, 2013 6:01 pm

denis_berthier wrote: .... I have a very different approach of the solution: ....
I'm not so sure our solutions are even all that different.
.... the central puzzle that remains after cutting out .... the above NW and SE sub-puzzles, ....
That's just using the singularities. Once you notice they're there, you know those little pieces will solve by themselves, otherwise the overall solution wouldn't be unique.
.... the small 2x2 NE and SW sub-puzzles, ....
I don't really see the point of this. Those 2x2 sub-puzzles don't solve by themselves. (The NE one will solve with just a little outside help, from r1c12+r2c12+r3c12+r4c12 only.)
.... the central W and E sub-puzzles ....
That's the global difference doubularity I was talking about.

Here's my approach, in plain English:

  • First solve the NW and SE corners, using the two singularities (r5c5=5 and r9c9=1).
  • Now semi-solve the W and E side chunks, using the two tripularities (r7c4+r7c5+r7c6=22 and r7c8+r7c9+r7c10=14).
  • Notice that r2c8 and r7c6 form a sum doubularity (r2c8+r7c6=7). Because r7c6 must be at least 5 (it's part of the 3-digit 22 in the above step) it must be either 5 or 6, and r2c8 must be 2 or 1 respectively.
  • Using the next doubularity in the chain, r3c10 must be 3 or 2 respectively.
  • Using the doubularity after that, r5c11 must be 8 or 7 respectively.
  • r5c11 cannot be 7, so it must be 8.
  • This allows the entire circular chain of eight doubularities to be solved instantly, and the rest is easy.
Bill Smythe
Smythe Dakota
 
Posts: 534
Joined: 11 February 2006

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Sun Jun 23, 2013 4:31 am

Hi Bill,

With the details you give, our solutions appear to be closer than I thought. We use the same central part, but we deal with it in different ways.

Smythe Dakota wrote:
denis_berthier wrote: the central puzzle that remains after cutting out .... the above NW and SE sub-puzzles, ....
That's just using the singularities. Once you notice they're there, you know those little pieces will solve by themselves, otherwise the overall solution wouldn't be unique.


Actually, uniqueness of the global puzzle doesn't imply uniqueness for a sub-puzzle (even for one defined by a 1-cut).
Well, that depends on how you define a sub-puzzle. But when I say it can be solved independently, I mean that, after assigning proper sums to the parts of the segments it includes (and that have been cut into two parts), it can be solved. For the NW puzzle, for instance, this means assigning sum 5 to the trivial 1-cell horizontal sector starting at the right of r5c4 (the remaining two cells have been cut out).
The reason why uniqueness is not guaranteed in this case (I mean in the general case, not in the NW special 1-cell example) is that the constraints that should be inherited by the global segments are (momentarily) forgotten (the simplest example is the two small 2x2 NE and SW sub-puzzles).

I don't mean that 1-cuts must always be used this way. Most of the time, it's more efficient not to isolate a sub-puzzle from the global one.
But in the present case, the central sub-puzzle can indeed be solved independently.
From my experience of trying to solve independent sub-puzzles, it is sometimes easier to solve the largest one than the smallest - always for the same reason that part of the constraints are momentarily forgotten.


Smythe Dakota wrote:
denis_berthier wrote: .... the small 2x2 NE and SW sub-puzzles, ....

I don't really see the point of this. Those 2x2 sub-puzzles don't solve by themselves. (The NE one will solve with just a little outside help, from r1c12+r2c12+r3c12+r4c12 only.)

My idea was to have the smallest possible central part.
It doesn't matter if the two small ones can't be solved independently. Once the NW, SE and central ones are solved, the rest is trivial.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Kakuro