Hi
Saul,
I'll take your questions in reverse order.
saul wrote:Denis wrote:My experience with hundreds of puzzles (classified as hard in the atk collection)
I've been meaning to ask about this. Do you just go to the website and manually copy the puzzles, or have you found a better way?
Unfortunately, I have no better way than doing it manually. It could have been very frustrating. But, at the time I did it, a few months ago, I had a very good motivation.
As you may know, I first introduced all "my" chain rules (whips, braids, ...) in the context of Sudoku. Later, I showed that these rules (and the associated ratings) were meaningful for any finite CSP. Still later (and this was the reason why I started to write "
Pattern-Based Constraint Satisfaction"), I showed that they could be concretely applied to various other CSPs: N-Queens, graph colouring, Futoshiki, Numbrix, Hidato.
Although the constraints are very different in nature in these puzzles, they still have a point in common: they are naturally binary.
In Kakuro, arithmetic constraints are highly non-binary (they can be up to 9-ary - or 8-ary if you consider the 45-in-9 as void).
There's a well known general technique for transforming any non-binary constraint into binary ones; but it is terribly inefficient in practice.
By introducing redundant CSP variables (representing combinations in the sectors), I thought I could solve at least the easy puzzles without doing any arithmetic (except of course the pre-computations replacing the sum constraints by the allowed combinations in the various sectors). As my purpose was only illustrative, I had planned to test this only with a few examples.
However, much to my surprise, the method was much more powerful than I expected and it also applied to hard puzzles. That's how I got very excited about it and I was led to spend on Kakuro much more time than I first expected. I thus tested hundreds of (mainly hard) examples (not all from atk, because I wanted to be sure they had nothing special that made them easier - indeed the atk hard ones are among the hardest I've found on the web, wrt to the W rating).
saul wrote:In the few examples I've looked at, the set of cells in the "surface" is indeed a cut set, but what then?
saul wrote:Denis wrote:The question is, how to use them afterwards.
Sometimes, so far as I can see, the information gained is useless.
Yes, that's why I think the first step should be to state clearly which cases you want to consider (and to assemble a corresponding collection of puzzles).
As for me, for the reasons mentioned in the previous paragraphs, I was interested in a pattern-based, non-arithmetic solution. So I haven't explored all the possibilities of complex surface sums (and I don't mean to do it now, as I don't think they can be very useful). Indeed, in my book, I've considered only 1-cuts. (I've considered surface sums as an example of application-specific rules).
saul wrote:Denis wrote:Detecting them is easy
Do you have a simple proof of this? I'm having trouble even coming up with the statement I want to prove. If the proof isn't simple, perhaps you could at least state the theorem for me.
If you mean a proof of the sum rules themselves, once the surface has been correctly defined, it's only commutativity and associativity of addition (sum of row sums = sum of column sums).
For 1-cuts, there are only two possibilities: there are either one or two sectors crossing the border of the surface at the cut point. The first case is easy; in the second case, you must consider differences.
For 2-cuts, it gets more complex as there are 4 possibilities. I haven't explored such cases, because I doubt they can be very useful. Maybe, if
Bill has some experience of such cases, he could tell us more about them.