Can You Solve This Without Trial and Error?

For fans of Kakuro

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Fri Apr 26, 2013 3:58 pm

saul wrote:I wonder if they [atk] expect you to sometimes do some limited trial and error at the end. I agree with Bill in that doing a moderate bit of trial and error doesn't reduce my pleasure in the puzzles. My rule is, "As long as I can do it in my head, it's okay." Even when I get my program written, I expect there will be times when the program has no hints to offer.

My own rule for Sudoku, Kakuro and any other puzzles:
- for players: do it as you like it and accept no restrictions anyone else would try to impose on you (which doesn't prevent you from learning new ways if you like)
- for theoretical studies: be consistent with yourself and accept no unjustified restrictions anyone else would try to impose on you
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 26, 2013 4:47 pm

denis_berthier wrote:- for players: do it as you like it and accept no restrictions anyone else would try to impose on you (which doesn't prevent you from learning new ways if you like)

Oh, of course; my rule is meant only for me. I just offer as a suggestion in the sense, "This is what I've found pleasurable. Maybe it will work for someone else, too."

I can't stand it when people try to dictate what is "cheating" in doing a puzzle. It's like talking about cheating in knitting (which come to think of it, I'm sure some people do.)
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Fri Apr 26, 2013 5:05 pm

saul wrote:Oh, of course; my rule is meant only for me. I just offer as a suggestion in the sense, "This is what I've found pleasurable. Maybe it will work for someone else, too."

That's how I had understood it. Same for mine !

saul wrote:I can't stand it when people try to dictate what is "cheating" in doing a puzzle. It's like talking about cheating in knitting (which come to think of it, I'm sure some people do.)

Not sure I could safely say to my gf she's cheating in knitting. :lol:
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 Apr 27, 2013 2:48 am

saul wrote: .... What I do [ when a guess turns out to be correct ] is to go back and try the other possibilities to verify that they lead to contradictions. Then I know I've proved uniqueness.

Yes, that's about the only satisfying way to handle guesses that turn out right.

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

Re: Can You Solve This Without Trial and Error?

Postby Smythe Dakota » Sat Apr 27, 2013 2:56 am

saul wrote: .... It's too bad there aren't more online kakuro forums that discuss advanced solving rules, trial and error, and related issues. ....

I think this is the best forum, right here. Maybe it's the only one. The three of us are having a nice private conversation. I wonder if there are any lurkers?

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

Re: Can You Solve This Without Trial and Error?

Postby Smythe Dakota » Sat Apr 27, 2013 3:08 am

A few posts back we were talking about whether the Mepham puzzles (for example) are 9x9 or 10x10. My position was that the top "row" and left "column" aren't really there, they are just convenient places to write the sums.

What if, instead of writing the sums at the top or left of each word, they are written (in small print) inside the topmost or leftmost cell in the word? For vertical words the sum could be written just inside the top edge of the topmost cell, and for horizontal words, just inside the left edge of the leftmost cell.

What if, furthermore, it was not required to have a black cell between two horizontal words in the same row, or between two vertical words in the same column? Instead, the two words could be separated with a thick line, as opposed to the thin lines separating each digit from the next within the same word.

You could have an entire Kakuro puzzle without any black cells at all! We could call it Generalized Kakuro. "Regular" Kakuro would just be a special case of Generalized Kakuro.

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

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Sat Apr 27, 2013 5:32 am

Smythe Dakota wrote:A few posts back we were talking about whether the Mepham puzzles (for example) are 9x9 or 10x10. My position was that the top "row" and left "column" aren't really there, they are just convenient places to write the sums.

For lack of a norm, I counted them in my book, mainly because it was convenient, but I have no dogma (as you know, I can now choose both conventions in my solver).

Smythe Dakota wrote:What if, instead of writing the sums at the top or left of each word, they are written (in small print) inside the topmost or leftmost cell in the word?
For vertical words the sum could be written just inside the top edge of the topmost cell, and for horizontal words, just inside the left edge of the leftmost cell.

You mean as in crosswords? But in Kakuro (as in Sudoku), people can use the white cells to write the candidates and there'd be some interference.


Smythe Dakota wrote:What if, furthermore, it was not required to have a black cell between two horizontal words in the same row, or between two vertical words in the same column? Instead, the two words could be separated with a thick line, as opposed to the thin lines separating each digit from the next within the same word.
You could have an entire Kakuro puzzle without any black cells at all! We could call it Generalized Kakuro. "Regular" Kakuro would just be a special case of Generalized Kakuro.


But then, you'd have to put 2 sums in the same white cell (sometimes) and you'd get still more interference with the candidates.

From a theoretical POV, I don't know if it'd be a real generalisation (or conversely a specialisation). I didn't spend much time on it, but I see no obvious answer. Actually, I see no obvious systematic mapping from one type of grid to the other. Maybe a more abstract angle of attack would provide a way of studying this question (maybe via the kind of matrices in a LP translation as in e.g. http://forum.enjoysudoku.com/can-you-solve-this-without-trial-and-error-t30960-12.html).
From a player's POV, I think it's a good point for Kakuro that sectors are separated in a very obvious way.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Sat Apr 27, 2013 5:34 am

Smythe Dakota wrote:
saul wrote: .... It's too bad there aren't more online kakuro forums that discuss advanced solving rules, trial and error, and related issues. ....

I think this is the best forum, right here. Maybe it's the only one. The three of us are having a nice private conversation. I wonder if there are any lurkers?

I've searched the web for other Kakuro forums, but I've been unable to find any in English, French or Spanish.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Sat Apr 27, 2013 5:41 am

Smythe Dakota wrote:
saul wrote: .... What I do [ when a guess turns out to be correct ] is to go back and try the other possibilities to verify that they lead to contradictions. Then I know I've proved uniqueness.

Yes, that's about the only satisfying way to handle guesses that turn out right.

But that can be unboundedly complex (in Sudoku for sure, but probably also in Kakuro).
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Can You Solve This Without Trial and Error?

Postby saul » Sat Apr 27, 2013 4:26 pm

denis_berthier wrote:
Smythe Dakota wrote:
saul wrote: .... What I do [ when a guess turns out to be correct ] is to go back and try the other possibilities to verify that they lead to contradictions. Then I know I've proved uniqueness.

Yes, that's about the only satisfying way to handle guesses that turn out right.

But that can be unboundedly complex (in Sudoku for sure, but probably also in Kakuro).

Yes, but I wouldn't be resorting to trial and error in such a situation. I usually use trial and error only near the end of the puzzle or when there's an isolated sub-puzzle that I can't work out. Then, I look for a cell with a minimal number of candidates. So, if one candidate solves the (sub)puzzle, I check that the other leads to a contradiction. I'd never try to do exhaustive search by hand. When I first started doing kakuro puzzles, back in the 1980's, they were called "cross sums" and they appeared in some of the old Dell puzzle magazines in the U.S. I think they also appeared in some of the Penny Press magazines as well. Compared to the Japanese kakuro puzzles, these were very easy, and I don't recall that trial and error was necessary, at least not very often.

When I first started doing the Japanese kakuro puzzles on line recently, I used trial and error a lot. Sometimes I would try a candidate that didn't lead to a contradiction very quickly, and then I would abandon it and try another. Since the atk website only allows you to back up five moves, I'd have to save the game when I started the trial and error, and restore it when I came to my conclusion.

I hate that they only let you back up 5 moves. This seems to be a way of restricting trial and error. I admit that it's their site and they have the right to do whatever they like on it, but it seems that having posted these wonderful puzzles, for which I'm very grateful, they shouldn't try to dictate how people go about solving them. The amount of storage involved is too trivial for anyone to seriously worry about. This seems to be a case of preventing people from cheating at knitting.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby Smythe Dakota » Sun Apr 28, 2013 8:37 am

I wrote: .... What if, instead of writing the sums at the top or left of each word, they are written (in small print) inside the topmost or leftmost cell in the word? ....
In response, denis_berthier wrote: .... But .... people can use the white cells to write the candidates and there'd be some interference. ....

True. It wouldn't be pretty, but it might be an interesting theoretical possibility.

Then I wrote: .... What if, furthermore, it was not required to have a black cell between two .... words? .... Instead, the two words could be separated with a thick line .... You could have an entire Kakuro puzzle without any black cells at all! We could call it Generalized Kakuro. ....
To which denis_berthier wrote: .... But then, you'd have to put 2 sums in the same white cell (sometimes) and you'd get still more interference with the candidates. ....

True again. It would really get messy now.

From a theoretical POV, I don't know if it'd be a real generalisation (or conversely a specialisation). ....

If black cells were disallowed, I'm sure it would be neither a generalization nor a specialization. But if black cells are optional, it would seem to be a generalization.

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.

You could even have some fun with the cell names and words:

Word 1, sum 21: AR YU MY BF
Word 2, sum 40: NO IM NT UR BF GO AW AY

Et cetera. A typical Mepham-sized puzzle would have about 64 cells and about 36 words.

Of course, in a proper puzzle each cell would have to be in at least two words (otherwise the "cross" in "cross sums" would be lacking). But one cell could be in 3 or more words, making the puzzle n-dimensional. Furthermore, two different words might as well be allowed to have more than one cell in common.

How's that for Generalized Kakuro? You'd really have to pound those computers now.

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

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Sun Apr 28, 2013 11:40 am

Smythe Dakota wrote:
From a theoretical POV, I don't know if it'd be a real generalisation (or conversely a specialisation). ....

If black cells were disallowed, I'm sure it would be neither a generalization nor a specialization. But if black cells are optional, it would seem to be a generalization.

Sure, but a really ugly way of presenting the same type of constraints in two different forms.


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.

Yes, big generalisation. But will you believe it? I could use my Kakuro solver with almost no change. (Of course, I would have to adapt my input-output functions.) The only difference is, instead of horizontal and vertical sectors (and the associated hrc and vrc CSP variables), I would introduce only sectors (or words as you call them).
I could use exactly the same rules as in the above examples, including Subsets (Naked, Hidden and Super-Hidden) although there's no grid structure.


There's one aspect you don't mention: do you want a graphical representation of the solution? I think it is important in all the logic puzzles of this kind.
If so, you'll get two totally independent problems:
- your Generalised Kakuro stricto sensu
- and a graph presentation problem (a planar graph if you add the constraint that words cannot cross one another but at the predefined cells and if you provide only puzzles that can satisfy it).
The player can choose to solve them in any order, but it seems natural to solve first the graph problem and only then to take advantage of the visual presentation for solving the Kakuro problem.


Smythe Dakota wrote:But one cell could be in 3 or more words, making the puzzle n-dimensional.

Not automatically. You can have planar graphs with vertices of any degree (only the average degree must be < 6).

Smythe Dakota wrote:Furthermore, two different words might as well be allowed to have more than one cell in common

This wouldn't change what I said above.
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 28, 2013 5:12 pm

Obviously, a kakuro puzzle could be presented like a crossword puzzle, with the numbers in the diagram indicating which clue it is, and a separate list of across and down clues. Then, it's clear you can have diagramless kakuro puzzles, just like diagramless crossword puzzles (another form of puzzle I'm very fond of, but ithey're hard to find, at least in English.)

This doesn't seem to be either a generalization or a specialization of Bill's suggestion. The clues are listed in sequence, which gives a lot of information Bill's puzzle wouldn't, but there is no information given about row and column numbers.
saul
 
Posts: 105
Joined: 01 February 2013
Location: Kansas City

Re: Can You Solve This Without Trial and Error?

Postby Smythe Dakota » Mon Apr 29, 2013 5:01 am

I wrote: .... If black cells were disallowed, I'm sure it would be neither a generalization nor a specialization. But if black cells are optional, it would seem to be a generalization.
In response, denis_berthier wrote: .... Sure, but a really ugly way of presenting the same type of constraints in two different forms. ....

Actually, I was thinking that the sums could always appear within the topmost or leftmost cell, regardless whether there was a black cell immediately above or to the left. That way, we're back to being only moderately ugly. :)

.... There's one aspect you don't mention: do you want a graphical representation of the solution? ....

Ideally, yes, but I'm pretty sure this wouldn't be practical in the most generalized cases.

I wrote:But one cell could be in 3 or more words, making the puzzle n-dimensional.
.... Not automatically. You can have planar graphs with vertices of any degree ....

Hmm, you're right. For example, if you use a Chinese Checkers (hexagonal) grid, you could easily have horizontal, NNW-SSE, and NNE-SSW words intersecting in a single cell.

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

Re: Can You Solve This Without Trial and Error?

Postby denis_berthier » Tue Apr 30, 2013 5:59 am

Smythe Dakota wrote:
.... There's one aspect you don't mention: do you want a graphical representation of the solution? ....

Ideally, yes, but I'm pretty sure this wouldn't be practical in the most generalized cases.

My point was more about defining a successful puzzle - a special case of yours.
I think that the graphical aspect of a puzzle plays a major role in its success.
In Sudoku, all the constraints are immediately visible and most of the basic techniques rely on the existence of the grid (even if they can be generalised).
It is only partly true in Kakuro (the allowed combinations do not appear directly on the grid - if you want to track them, you have to write them beside).
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).
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

PreviousNext

Return to Kakuro