Can You Solve This Without Trial and Error?

For fans of Kakuro

Re: Can You Solve This Without Trial and Error?

Postby Smythe Dakota » Tue Apr 30, 2013 9:29 am

denis_berthier wrote: .... I think that the graphical aspect of a puzzle plays a major role in its success. .... in games of this kind, some form of regular grid is necessary ....

I agree. I would never be interested in actually trying to solve one of the theoretical monstrosities I've been proposing. My point was to observe that the black cells don't really exist mathematically -- they're just convenient places to write the sums.

.... but not necessarily a square in a plane, it can be hexagonal or it can lie on a torus or a Klein bottle ....

Yes, Tarek has quite a few Moebius strips, tori, Klein bottles, and projective planes in the Sudoku Variants topic. Those are interesting too.

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

Re: Can You Solve This Without Trial and Error?

Postby saul » Tue Apr 30, 2013 1:08 pm

denis_berthier wrote:I think, in games of this kind, some form of regular grid is necessary - but not necessarily a square in a plane, it can be hexagonal or it can lie on a torus or a Klein bottle (although I can hardly imagine people solving their puzzles on a tyre or using this bottle to carry their water).

A torus would be practical, because it's easy to visualize the rows and columns wrapping around, but I don't think it would ever get popular. A hexagonal grid is attractive, though. Perhaps a variant of kenken? What would play the roles of rows and columns?
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby saul » Tue Apr 30, 2013 1:17 pm

Smythe Dakota wrote:
saul wrote: .... This may seem a bit anal, but I was a math student in a prior life.

Me too. What's purple and commutative?
Bill Smythe

An abelian grape. Old jokes never die, it seems. As nearly as I can recall, I first heard this joke in 1965. My favorite of this genre is, "What do you get when you cross an elephant with a blueberry?" which I heard a year or two earlier.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby Smythe Dakota » Wed May 01, 2013 12:07 pm

I don't know, but here are two more:

What's green and very far away?

What's yellow and equivalent to the Axiom of Choice?

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

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Mon May 06, 2013 5:09 am

Smythe Dakota wrote:An even bigger generalization could be along the following lines: There is no diagram. You are given a list of cell names, each name perhaps consisting of two letters, like AX, GT, etc. You are then given a list of words, each word consisting of at least 2 and at most 9 cells. For each word the sum is given. You are to assign to each cell a value 1-9, no duplicates within any word, so that all the sums are correct.

It seems there's an (obvious) aspect we have overlooked and it drastically reduces the possibilities.
Let's call free a cell that appears in only one sector/word.
In a well posed puzzle (i.e. with a unique solution), there can be at most one free cell per word.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby Smythe Dakota » Tue May 07, 2013 1:37 am

I don't think free cells should be allowed at all. Kind of defeats the name "cross-sums", wouldn't you think?

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

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Tue May 07, 2013 7:23 am

Smythe Dakota wrote:I don't think free cells should be allowed at all. Kind of defeats the name "cross-sums", wouldn't you think?

Free cells give some degree of generality but yes, if you stick to the name, they are somewhat queer.
If you don't allow them and if you also insist on having some graphical planar representation, there may be an interesting problem in topology. What kinds of coverings of domains in the plane can we get?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby saul » Tue May 07, 2013 5:40 pm

Back to our earlier discussion of what is trial and error, or "legitimate" trial and error.
Look at this puzzle:
Image
When I got to this point, I couldn't see any pattern, except that I already knew, from a surface sum, that r2c8+r4c8 = 8, with my usual way of indexing rows and columns.

Now, I say if r2c4 = 2, then r2c8 = 3, so r4c8 = 5. Also, r5c4 = 4, and since any combination making 30 in 6 must have a 1 or a 2, r5c6 = 1. That gives a 1457 in row 5,so the remaining 2 cells in the row add to 13. One of the cells is 8 or 9, and the 4 and 5 are already used. Therefore, r2c4 must be 4, and the rest is straightforward.

My feeling is that this is trial and error, although since I did it all in my head, I have no qualms about it. Still, I'm wondering why I think of this as trial and error. After all, I often exclude candidates by reasoning something like, "This can't be a 6 because then the total would come to more than 14 (or whatever)." I guess the difference is that, in the latter case, since I'm working in a single unit, I know that my reasoning can be replaced by a formula, or a list of possible combinations, and in the former case, it can't be.

I must admit that I'd rather have a formula in the second case, too, although I'm not sure I can explain why, even to myself.

Reactions?
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby Smythe Dakota » Wed May 08, 2013 2:07 am

Image

Um, don't r3c4 and r3c5 have to be 2 and 6, respectively, in order to add up to 8?

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

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Wed May 08, 2013 4:39 am

saul wrote:Back to our earlier discussion of what is trial and error, or "legitimate" trial and error.
Look at this puzzle:
Image
When I got to this point, I couldn't see any pattern

If you have cleaned the combinations incompatible with the known digits, you have the following bivalue chain, much simpler than your next elimination:
biv-chain[2]: hr6c4{n359 n458} - r6c6{n3 n4} ==> r6c5 <> 4
The end is done with Singles.

saul wrote:Now, I say if r2c4 = 2, then r2c8 = 3, so r4c8 = 5. Also, r5c4 = 4, and since any combination making 30 in 6 must have a 1 or a 2, r5c6 = 1. That gives a 1457 in row 5,so the remaining 2 cells in the row add to 13. One of the cells is 8 or 9, and the 4 and 5 are already used. Therefore, r2c4 must be 4, and the rest is straightforward.
My feeling is that this is trial and error, although since I did it all in my head, I have no qualms about it.

Don't worry about using T&E. From my experience in Sudoku, it is the most widely used technique (often the only one used) and I can see no rational reason for putting an a priori anathema on it. Very often also, it is a start for finding a simpler elimination (by cutting useless steps).

saul wrote:I must admit that I'd rather have a formula in the second case, too, although I'm not sure I can explain why, even to myself.

Because it would look simpler?
I could probably write one following exactly your reasoning, if you made some steps more explicit, e.g. how you get r4c8=5.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby saul » Wed May 08, 2013 2:46 pm

denis_berthier wrote:biv-chain[2]: hr6c4{n359 n458} - r6c6{n3 n4} ==> r6c5 <> 4

Great! I still haven't had the time to really get into your book, so I don't understand this yet, but it's clearly what I want. I'll be referring back to this post when I've read about bivalue chains.
denis_berthier wrote:
saul wrote:I must admit that I'd rather have a formula in the second case, too, although I'm not sure I can explain why, even to myself.

Because it would look simpler?

Yes, partially because it would look simpler, and somehow seem more penetrating, just as one usually prefers a simpler proof in math. Also, I think there's less chance of making a mistake. As Bourbaki says somewhere, "The first time it's a trick; the third time, it's a method."
denis_berthier wrote:I could probably write one following exactly your reasoning, if you made some steps more explicit, e.g. how you get r4c8=5.

A typo, I'm sorry to say. I meant to say, that I had already determined that r2c8 + r5c8 = 8, so if r2c8 = 3, r2c5 = 5. I just copied my earlier typo. And I thought I had reviewed this so carefully! I must be the world's worst proofreader.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Wed May 08, 2013 3:47 pm

saul wrote:
denis_berthier wrote:I could probably write one following exactly your reasoning, if you made some steps more explicit, e.g. how you get r4c8=5.

A typo, I'm sorry to say. I meant to say, that I had already determined that r2c8 + r5c8 = 8, so if r2c8 = 3, r5c8 = 5 corrected. I just copied my earlier typo. And I thought I had reviewed this so carefully! I must be the world's worst proofreader.



saul wrote:Now, I say if r2c4 = 2, then r2c8 = 3, so r5c8 = 5 corrected.

r2c8 + r5c8 = 8 implies that combination 1346 is impossible. That's how I'll use it to write the start of a braid.
braid[]: r2c8{n2 n3} - vr1c8{1238 2345} - r5c8{n6 n5} .... => r2c4 <> 2
The second part of your reasoning can be written similarly.
But this is much too long.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby saul » Thu May 16, 2013 3:16 pm

Here is an unusual example of surface sums.
Image
In each of the corners, we can use a surface sum to compute the difference between two cells, and use some information about the possible sums to further restrict the values in the two cells. For example, in the upper left-hand corner, the sum of the 3 rows is 34 and the sum of the first 3 columns is 32, r3c4 - r4c3 = 2. Since r3c4 <= 4 ( to make the row sum 10 in 4) we have only the 2 possibilities shown.

I didn't actually start this way, but found the surface sums as I was working the puzzle. Then I went back to see what inferences had been available at the beginning. This much of a start really simplifies the puzzle.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby Smythe Dakota » Fri May 17, 2013 2:45 am

Yeh, those are what I call "difference doubularities". I use them all the time.

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

Re: Can You Solve This Without Trial and Error?

Postby saul » Fri May 17, 2013 4:00 am

Right, I guess I put it badly. I didn't mean that the surface sums themselves were unusual, but that the ensemble of them was.

I've never seen a puzzle that you could separate into 5 parts at the very beginning, using "difference doublarities." As you've pointed out, there are lots of puzzles that break into 5 sub-puzzles at the start using 1-cuts, but this is the first I've ever seen, or at least recognized, like this.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

PreviousNext

Return to Kakuro