The New Sudoku Players' Forum

[Smythe Dakota]

.... Actually, uniqueness of the global puzzle doesn't imply uniqueness for a sub-puzzle (even for one defined by a 1-cut). ....

If the 1-cut is a singularity (in my narrower sense), uniqueness of the overall puzzle does, of course, imply uniqueness for the sub-puzzle. Otherwise, once you find an overall solution, you could substitute the other solution for the sub-puzzle, and you'd have a second solution for the overall.

Of course, this doesn't work for doubularities. In that case, all that can be established is either the sum or the difference of the two cells in the doubularity. And that's not enough to guarantee uniqueness in the sub-puzzle.

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

I wish I could understand sentences like that.

.... 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 only reason you can assign 5 to r5c5 (and the reason it is trivial) is that r5c5 is a singularity (in my narrower sense).

.... The reason why uniqueness is not guaranteed .... in the general case .... is that the constraints that should be inherited by the global segments are (momentarily) forgotten ....

Again, that's too vague to allow me to figure out what you're saying.

.... (the simplest example is the two small 2x2 NE and SW sub-puzzles). ....

The reason uniqueness is not guaranteed in these two cases is extremely simple: There is no singularity (in my narrower sense) associated with either of these two. There is only a doubularity -- r3c12-r4c12 in the NE case, and its mirror image in the SW case.

.... From my experience of trying to solve independent sub-puzzles, it is sometimes easier to solve the largest one than the smallest ....

If the smaller puzzle is cut off from the larger puzzle as the result of a singularity, then of course that's not true. Once the division has occurred, solving either puzzle is truly independent of solving the other. The solution of the larger provides no information that helps solve the smaller, nor vice versa. It makes absolutely no difference which one is solved first.

I must admit, though, that once I have isolated a singularity, I prefer to solve the smaller puzzle first. That way, in case I made a computational error in evaluating the singularity, I will discover it sooner, and waste less time.

Bill Smythe

[denis_berthier]

.... Actually, uniqueness of the global puzzle doesn't imply uniqueness for a sub-puzzle (even for one defined by a 1-cut). ....

If the 1-cut is a singularity (in my narrower sense), uniqueness of the overall puzzle does, of course, imply uniqueness for the sub-puzzle.

Yes, of course, but singularities are the trivial case that I excluded from my remarks.

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

I wish I could understand sentences like that.

It's very simple. Take the leftmost horizontal sector in row r7, a 37-in-6.
r7c3 is a 1-cut cell. If you use it to cut out the small sub-puzzle Q on the W side of this cell (including r7c3) AND IF you try to solve Q independently of the rest, then you have to split the global r7c1-r7c6 sector into two parts, one of which (r7c1-r7c3) is included in Q. Using the surface sum, the sub-sector inside Q becomes a 15-in-3 (the remaining part will be a 12-in-3 included in the complementary sub-puzzle).
Considered as an independent puzzle, Q doesn't have a unique solution.
This doesn't contradict the fact that the global puzzle P has a unique solution, because considering Q as an independent puzzle doesn't take all the original constraints (those bearing on the whole r7c1-r7c6 sector) into account. That's what I meant by:

.... The reason why uniqueness is not guaranteed .... in the general case .... is that the constraints that should be inherited by the global segments are (momentarily) forgotten ....

.... From my experience of trying to solve independent sub-puzzles, it is sometimes easier to solve the largest one than the smallest ....

... once I have isolated a singularity, I prefer to solve the smaller puzzle first. That way, in case I made a computational error in evaluating the singularity, I will discover it sooner, and waste less time.

Of course, I also try the smallest sub-puzzle first when I have a 1-cut. But if it doesn't work, I try the largest.

Of course also, there's no reason why there should always be one of the two sub-puzzles having an independent solution in the above sense. Indeed, I think it's rather rare; but, when it's the case, I like to use it.

[saul]

M44252 is another 8-by-8 "medium" puzzle that seems much harder than the "hard" puzzle Denis brought to our attention the other day. I haven't been able to get much of anywhere with it. It has very few uniques, and a very high density of white cells, if you consider the puzzle to be bounded by white cells.

[denis_berthier]

M44252 is another 8-by-8 "medium" puzzle [...] I haven't been able to get much of anywhere with it. It has very few uniques, and a very high density of white cells, if you consider the puzzle to be bounded by white cells.

I confirm: it's absurdly difficult for a "moderate" puzzle. It can't even be solved by any combination of Subsets and g-whips.

[Smythe Dakota]

.... I confirm: it's absurdly difficult for a "moderate" puzzle. ....

Yeh, I finally got it, but it took longer than it was worth, and now I'll be sleepy when I go to work in the morning.

It helped when I noticed that the main diagonal r2c2-r4c4-r5c5-r7c7 forms a sum-difference quadrupularity. By comparing horizontal and vertical sums in the SW half of the puzzle, one concludes that the vertical stick-outs (r2c2 and r5c5) exceed the horizontal stick-outs (r4c4 and r7c7) by 8, i.e. (r2c2+r5c5) - (r4c4+r7c7) = 8.

Or, of course, one could compare sums in the NE half of the puzzle, and reach the same conclusion. (The vertical stick-outs are now horizontal stick-outs, and vice versa.)

Whew!

Bill Smythe

[saul]

It helped when I noticed that the main diagonal r2c2-r4c4-r5c5-r7c7 forms a sum-difference quadrupularity. By comparing horizontal and vertical sums in the SW half of the puzzle, one concludes that the vertical stick-outs (r2c2 and r5c5) exceed the horizontal stick-outs (r4c4 and r7c7) by 8, i.e. (r2c2+r5c5) - (r4c4+r7c7) = 8.

Good catch! I'll try it again and see if this helps.

[Smythe Dakota]

.... Good catch! I'll try it again and see if this helps.

I should warn you that, for me, this quadrupularity was neither an early nor a late step in the process. I struggled quite a bit with various ad hoc techniques, both before and after I tackled the quadrupularity. In fact, I think I had 1 or 2 of those four cells already solved, or solved within two neighboring possibilities (like 8 and 9), before I used the quadrupularity.

Bill Smythe

[saul]

.... Good catch! I'll try it again and see if this helps.

I should warn you that, for me, this quadrupularity was neither an early nor a late step in the process. I struggled quite a bit with various ad hoc techniques, both before and after I tackled the quadrupularity. In fact, I think I had 1 or 2 of those four cells already solved, or solved within two neighboring possibilities (like 8 and 9), before I used the quadrupularity.

Bill Smythe

I got to this point before I used the surface sum. As far as i can recall, it's same place I got to the first time, when I couldn't figure out what more to do:

Now, if you apply the surface sum at this point, all 4 cells in the cut are uniquely determined, and solving the remainder of the puzzle is easy.
So, it didn't take all that long to solve -- perhaps 30 or 40 minutes, but then I didn't have to spend any time searching for the surface sum .
It still amazes me that atk can rate this "medium." I'd love to know how they arrive at their ratings.

[Smythe Dakota]

.... I got to this point before I used the surface sum. ....

This is also exactly where I got before things got difficult. Unfortunately, at this point I hadn't yet discovered the quadrupularity. I struggled for a while, and solved two or three more cells somewhere, somehow, before I looked for any
-ularities.

.... Now, if you apply the surface sum at this point, all 4 cells in the cut are uniquely determined ....

Yikes -- that's true, isn't it?! I never checked back to find the point at which the quadrupularity had become solvable.

.... and solving the remainder of the puzzle is easy. ....

Hmm. I didn't find the rest all that easy, but then again it was 4 a.m.

If the rest really is that easy, then I actually agree with ATK's medium rating. After all, with that solving method, it's (1) find a few easy ones, then (2) solve the quadrupularity, then (3) do the rest (which you say is easy).

Maybe even the medium rating is overstated. (Of course, I wouldn't have said that 24 hours ago.)

Bill Smythe

[saul]

If the rest really is that easy, then I actually agree with ATK's medium rating. After all, with that solving method, it's (1) find a few easy ones, then (2) solve the quadrupularity, then (3) do the rest (which you say is easy).

Maybe even the medium rating is overstated. (Of course, I wouldn't have said that 24 hours ago.)

Bill Smythe

I know what you mean, but it isn't an easy surface sum to find. When I was stuck, I didn't find it, probably because the puzzle is so dense I didn't expect there to be any cuts.

[denis_berthier]

It still amazes me that atk can rate this "medium." I'd love to know how they arrive at their ratings.

I think, after trivial propagation of constraints, they use a linear programming solver. It'd explain why it's not consistent with human idea of difficulty.

[saul]

I think, after trivial propagation of constraints, they use a linear programming solver. It'd explain why it's not consistent with human idea of difficulty.

That would explain the strange difficulty ratings, but can a linear programming solver show uniqueness of the solution? Somehow they're ensuring that the puzzles are properly constructed.

[Smythe Dakota]

.... but can a linear programming solver show uniqueness of the solution? Somehow they're ensuring that the puzzles are properly constructed.

I was actually worried about that, when I started this one. Of course, I was confident ATK would not let a dual-solution puzzle through, but with only four interior black cells. and only a handful of easily solved cells, I began to have doubts. Usually, when a "puzzle" lends itself to only a few solved cells at the outset, and has a high ratio of white to black, it's because it's an invalid puzzle with multiple solutions. I've been through that with two sites, kakuropuzzle.com and kakuro.net, that are infamous for invalid puzzles. I'm happy this one turned out to be legitimate after all.

As for finding the quadrupularity, I just looked for the closest thing I could find. r2c2 and r7c7 were the most obvious candidates. Then I noticed that, after removing them, only two cells were left holding the thing together, r4c4 and r5c5, and voila! A solution is born.

Bill Smythe

[denis_berthier]

but can a linear programming solver show uniqueness of the solution? Somehow they're ensuring that the puzzles are properly constructed.

Rating and generating puzzles are different problems.
For checking uniqueness, the fastest method in Sudoku is depth-first search with direct constraints propagation; it's very likely the same is true of Kakuro.

[saul]

Have a look at ATK's M84472. It seems to be another example of a ridiculously difficult medium puzzle. I've worked at it for close to two hours and still have cells with 6, 7, or even 8 candidates!