The New Sudoku Players' Forum

[saul]

I've just gotten hooked on kakuro recently. I've been working the medium difficulty puzzles at atksolutions.com, but this one's got me stumped. I'm sure it's correct up to here, but I don't see what to do next. All of the puzzles that I've done on this site so far have been solvable without trial and error. Do you see a way to proceed from here?

https://dl.dropbox.com/u/24746182/kakuro.png

Thanks for any help you can give me.

Saul

[denis_berthier]

I've just gotten hooked on kakuro recently. I've been working the medium difficulty puzzles at atksolutions.com, but this one's got me stumped. I'm sure it's correct up to here, but I don't see what to do next. All of the puzzles that I've done on this site so far have been solvable without trial and error. Do you see a way to proceed from here?
https://dl.dropbox.com/u/24746182/kakuro.png

Hi Saul,

I've been away from any Internet access for some time and I just saw your post.
This puzzle is an easy one in the atk galaxy. It can be solved by whips of maximum length 3.
Below is the full solution given by CSP-Rules according to the theory developed in my last book "Pattern-Based Constraint Satisfaction and Logic Puzzles".
I let you find the eliminations missing in yours.

Definitions and notations (sketch):
Rows and columns are numbered from 1 to 12 (including the first totally black one).
CSP-variables hrc and vrc represent the combinations allowed in the horizontal (resp. vertical) sectors. As you know, there is a permanent interplay between the standard rc CSP-variables and the remaining allowed combinations in each sector (which are naturally represented in my approach by the hrc and vrc additional CSP-variables).
vr1c4 = 14 means that the vertical sector starting after black cell r1c4 can only contain digits 1 or 4. "14" is a shorthand for the set {1, 4}.
"cell-to-horiz-ctr" and other such rules express part of this interplay. In an advanced level puzzle, these should normally be considered as obvious and should not be displayed.
But this interplay also appears in the combined presence of both types of variables in whips.

***** KakuRules 1.2 based on CSP-Rules 1.2, config: W *****
horizontal magic sector 34-in-5, starting in r2c2, unique combination: 46789
horizontal pseudo magic sector 13-in-4, starting in r3c8, for digits: (1)
horizontal magic sector 4-in-2, starting in r4c1, unique combination: 13
horizontal pseudo magic sector 25-in-6, starting in r4c4, for digits: (1 2)
horizontal magic sector 22-in-6, starting in r6c1, unique combination: 123457
horizontal magic sector 30-in-4, starting in r7c2, unique combination: 6789
horizontal magic sector 11-in-4, starting in r7c7, unique combination: 1235
horizontal magic sector 23-in-3, starting in r9c1, unique combination: 689
horizontal magic sector 21-in-6, starting in r10c3, unique combination: 123456
horizontal magic sector 11-in-4, starting in r11c1, unique combination: 1235
horizontal magic sector 34-in-5, starting in r11c6, unique combination: 46789
horizontal magic sector 30-in-4, starting in r12c1, unique combination: 6789
horizontal magic sector 35-in-5, starting in r12c6, unique combination: 56789
vertical magic sector 17-in-2, starting in r7c2, unique combination: 89
vertical magic sector 42-in-8, starting in r1c3, unique combination: 12456789
vertical magic sector 37-in-8, starting in r4c4, unique combination: 12345679
vertical pseudo magic sector 38-in-7, starting in r1c5, for digits: (7 8 9)
vertical magic sector 24-in-3, starting in r1c6, unique combination: 789
vertical magic sector 16-in-5, starting in r1c7, unique combination: 12346
vertical magic sector 28-in-7, starting in r5c9, unique combination: 1234567
vertical magic sector 43-in-8, starting in r1c10, unique combination: 13456789
vertical magic sector 17-in-2, starting in r10c10, unique combination: 89
vertical magic sector 44-in-8, starting in r4c11, unique combination: 23456789
vertical magic sector 7-in-3, starting in r7c12, unique combination: 124

naked singles: r11c2 = 5, r10c6 = 6, r9c12 = 4, r10c12 = 2, r8c12 = 1, r8c2 = 8, r9c2 = 9, r9c4 = 6, r9c3 = 8, r7c8 = 5, r7c6 = 6, r4c3 = 1, r4c2 = 3, r2c4 = 4, r2c7 = 6, vr1c4 = 14, r3c4 = 1, vr5c6 = 16, r6c6 = 1, vr6c8 = 58, r8c8 = 8, hr8c1 = 1238, r8c3 = 2, hr10c10 = 29, r10c11 = 9, hr9c8 = 4689, r9c9 = 6, r9c11 = 8, r9c10 = 9, vr8c6 = 69, r9c6 = 9, hr9c5 = 39
naked-single ==> r9c7 = 3, vr10c2 = 59, r12c2 = 9, r12c4 = 7, r7c4 = 9, r7c3 = 7, r2c3 = 9, r7c5 = 8, r2c5 = 7, r2c6 = 8, r12c5 = 6, r12c3 = 8, vr10c3 = 18, r11c3 = 1, vr9c5 = 136, r11c5 = 3, r11c4 = 2, r10c5 = 1
hidden-single-in-magic-horiz-sector ==> r6c2 = 7
naked-singles ==> vr3c2 = 137, r5c2 = 1
hidden-single-in-magic-verti-sector ==> r8c4 = 1
naked-single ==> r8c5 = 3
cell-to-horiz-ctr ==> hr5c1 <> 1269
cell-to-horiz-ctr ==> hr5c1 <> 1278
ctr-to-horiz-sector ==> r5c5 <> 2
cell-to-horiz-ctr ==> hr4c4 <> 123568
cell-to-horiz-ctr ==> hr3c8 <> 1345
ctr-to-horiz-sector ==> r3c9 <> 5
ctr-to-horiz-sector ==> r3c10 <> 5
ctr-to-horiz-sector ==> r3c12 <> 5
cell-to-verti-ctr ==> vr7c7 <> 13679
horiz-sector-to-ctr ==> hr5c1 <> 1368
horiz-sector-to-ctr ==> hr5c1 <> 1458
horiz-sector-to-ctr ==> hr5c1 <> 1467
naked-singles ==> hr5c1 = 1359, r5c4 = 3, r5c5 = 9, r6c3 = 4, r3c3 = 6, r6c4 = 5, r6c5 = 2, r6c7 = 3, r10c4 = 4, vr1c5 = 2345789
cell-to-horiz-ctr ==> hr3c2 <> 13678
cell-to-horiz-ctr ==> hr5c6 <> 36
ctr-to-horiz-sector ==> r5c8 <> 3
cell-to-horiz-ctr ==> hr3c2 <> 12679
naked-singles ==> hr3c2 = 14569, r3c7 = 4, r3c5 = 5, r4c5 = 4, r3c6 = 9, r4c6 = 7
ctr-to-horiz-sector ==> r4c8 <> 9
cell-to-horiz-ctr ==> hr5c6 <> 45
ctr-to-horiz-sector ==> r5c8 <> 4
ctr-to-horiz-sector ==> r5c8 <> 5
cell-to-verti-ctr ==> vr3c8 <> 39
ctr-to-verti-sector ==> r4c8 <> 3
cell-to-verti-ctr ==> vr9c8 <> 479
ctr-to-verti-sector ==> r11c8 <> 4
horiz-sector-to-ctr ==> hr5c9 <> 289
ctr-to-horiz-sector ==> r5c11 <> 2
ctr-to-horiz-sector ==> r5c12 <> 2
horiz-sector-to-ctr ==> hr5c9 <> 379
ctr-to-horiz-sector ==> r5c10 <> 3
ctr-to-horiz-sector ==> r5c11 <> 3
ctr-to-horiz-sector ==> r5c12 <> 3
horiz-sector-to-ctr ==> hr5c9 <> 469
verti-sector-to-ctr ==> vr3c8 <> 48
naked-singles ==> vr3c8 = 57, r4c8 = 5, r5c8 = 7, hr5c6 = 27, r5c7 = 2, r4c7 = 1, hr4c4 = 124567, r4c10 = 6, r4c9 = 2
ctr-to-verti-sector ==> r2c9 <> 6
ctr-to-verti-sector ==> r3c9 <> 6
ctr-to-verti-sector ==> r2c9 <> 4
ctr-to-verti-sector ==> r3c9 <> 4
verti-sector-to-ctr ==> vr7c7 <> 13589
biv-chain[2]: vr1c11{n69 n78} - r3c11{n6 n7} ==> r2c11 <> 7
biv-chain[2]: hr3c8{n1237 n1246} - r3c11{n7 n6} ==> r3c12 <> 6
biv-chain[2]: r3c11{n6 n7} - vr1c11{n69 n78} ==> r2c11 <> 6
cell-to-horiz-ctr ==> hr2c8 <> 4567
whip[2]: r3c11{n7 n6} - hr3c8{n1237 .} ==> r3c10 <> 7, r3c9 <> 7
biv-chain[2]: r3c9{n1 n3} - vr1c9{n127 n235} ==> r2c9 <> 1
cell-to-horiz-ctr ==> hr2c8 <> 1489
biv-chain[2]: vr1c9{n127 n235} - r3c9{n1 n3} ==> r2c9 <> 3
cell-to-horiz-ctr ==> hr2c8 <> 3469
cell-to-horiz-ctr ==> hr2c8 <> 2389
whip[2]: r2c11{n8 n9} - hr2c8{n3568 .} ==> r2c10 <> 8
whip[2]: r10c8{n5 n3} - vr9c8{n578 .} ==> r12c8 <> 5
whip[2]: r2c10{n7 n5} - r2c9{n5 .} ==> hr2c8 <> 2569
whip[2]: hr5c9{n568 n478} - r5c12{n5 .} ==> r5c11 <> 7, r5c10 <> 7
whip[2]: hr5c9{n568 n478} - r5c11{n5 .} ==> r5c10 <> 4
whip[2]: vr1c12{n16 n25} - r3c12{n1 .} ==> r2c12 <> 2
horiz-sector-to-ctr ==> hr2c8 <> 2578
horiz-sector-to-ctr ==> hr2c8 <> 2479
whip[2]: vr1c12{n25 n16} - r3c12{n2 .} ==> r2c12 <> 1
whip[2]: vr4c12{n17 n26} - r5c12{n5 .} ==> r6c12 <> 6
whip[2]: vr4c12{n17 n35} - r5c12{n6 .} ==> r6c12 <> 5
whip[2]: vr4c12{n26 n17} - r5c12{n5 .} ==> r6c12 <> 7
whip[3]: r2c9{n7 n5} - hr2c8{n1678 n1579} - r2c12{n3 .} ==> r2c10 <> 7
whip[3]: r2c9{n5 n7} - hr2c8{n3568 n1579} - r2c12{n3 .} ==> r2c10 <> 5
naked-triplets-in-a-column c10{r2 r3 r7}{n1 n4 n3} ==> r8c10 <> 4
whip[2]: hr8c6{n124789 n134689} - r8c10{n7 .} ==> r8c11 <> 3, r8c9 <> 3
naked-triplets-in-a-column c10{r2 r3 r7}{n1 n4 n3} ==> r8c10 <> 3
cell-to-horiz-ctr ==> hr8c6 <> 134689
naked-triplets-in-a-column c10{r2 r3 r7}{n1 n4 n3} ==> r6c10 <> 4, r6c10 <> 3, r6c10 <> 1
cell-to-horiz-ctr ==> hr6c8 <> 1346
whip[2]: hr6c8{n1238 n1247} - r6c10{n8 .} ==> r6c9 <> 7, r6c11 <> 7
biv-chain[3]: c11n3{r6 r7} - r7n2{c11 c9} - c9n1{r7 r6} ==> r6c9 <> 3
whip[3]: r3c9{n1 n3} - r3c10{n3 n4} - hr3c8{n1237 .} ==> r3c12 <> 1
cell-to-verti-ctr ==> vr1c12 <> 16
ctr-to-verti-sector ==> r2c12 <> 6
cell-to-horiz-ctr ==> hr2c8 <> 1678
horiz-sector-to-ctr ==> hr2c8 <> 3568
whip[2]: hr2c8{n3478 n1579} - r2c12{n3 .} ==> r2c9 <> 5
naked-singles ==> r2c9 = 7, vr1c9 = 127, r3c9 = 1
biv-chain[2]: r3c10{n3 n4} - hr3c8{n1237 n1246} ==> r3c12 <> 3
biv-chain[2]: vr1c12{n25 n34} - r3c12{n2 n4} ==> r2c12 <> 4
biv-chain[2]: hr2c8{n1579 n3478} - r2c12{n5 n3} ==> r2c10 <> 3
biv-chain[2]: hr3c8{n1237 n1246} - r3c10{n3 n4} ==> r3c12 <> 4
naked-singles ==> r3c12 = 2, vr1c12 = 25, r2c12 = 5, hr2c8 = 1579, r2c10 = 1, r7c10 = 3, r3c10 = 4, r7c11 = 2, r7c9 = 1, r2c11 = 9, vr1c11 = 69, r3c11 = 6, hr3c8 = 1246
hidden-single-in-magic-verti-sector ==> r10c9 = 3
naked-singles ==> r10c8 = 5, r10c7 = 2
hidden-single-in-magic-verti-sector ==> r6c11 = 3
ctr-to-horiz-sector ==> r6c10 <> 7
hidden-single-in-magic-verti-sector ==> r8c10 = 7
cell-to-verti-ctr ==> vr4c12 <> 35
ctr-to-verti-sector ==> r5c12 <> 5
biv-chain[2]: r6c10{n5 n8} - hr6c8{n2345 n1238} ==> r6c9 <> 5
biv-chain[2]: c9n7{r11 r12} - c11n7{r12 r11} ==> r11c8 <> 7, r11c7 <> 7
biv-chain[2]: hr5c9{n478 n568} - r5c12{n7 n6} ==> r5c11 <> 6
biv-chain[2]: hr5c9{n478 n568} - r5c11{n4 n5} ==> r5c10 <> 5
singles to the end
GRID SOLVED. rating-type = W, MOST COMPLEX RULE = Whip[3]

------------
--94786-7195
--61594-1462
-31-471526--
-1539-27-856
-745213-4532
--7986-5132-
-8213-982741
-986-93-6984
---416253-92
-5123-49786-
-9876-86597-

[saul]

Thanks Denis. I haven't read your books, but I can see I'm going to have to. From what I see on amazon.com, it looks like the last one, "Pattern-Based Constraint Satisfaction and Logic Puzzles" is the best place to start. I really don't know anything about CSP, although I'm familiar with the idea, of course. I have a couple of questions I'd like to ask you, if you don't mind.

First, a rather long-winded introduction.

I'm writing a kakuro client in python, because I find it impossible to do these puzzles with pencil and paper. When I try to record and update the candidates for a cell, I just end up making a mess. I've written the part that allows me to enter a puzzle manually. As part of it I've written a solver that I use just to confirm that the puzzle has been entered correctly. This uses a toy CSP solver written in python that I downloaded from http://labix.org/python-constraint. It works, but it's awfully slow on large puzzles. I've done a little preprocessing to speed it up, but not much, because I thought I'd eventually replace it, for reasons explained in the next papragraph.

I'm pretty far advanced on my player, which allows the user to solve the puzzle interactively. For the next stage, I want to implement hints. I hadn't thought the CSP approach would be useful for this, so I planned to write a custom solver. After looking at your solution, I'm reconsidering this. What I want the program to do is to look at the eliminations the user has entered so far, and to choose the simplest rule that allows a further inference. (I have yet to decide what to do if he's made a mistake already.) Your theory appears to be ready-made for me.

Now for the questions:

1. It looks like your theory will be directly applicable to the hints, but as I haven't read your book, I don't know what you mean by "whips," for example. Am I correct in assuming that all your rules are ones that you expect a human to be able to apply in play?

2. Will I need any background in CSP in order to read your book? If so, can your recommend a source? I am only interested in getting the minimum necessary to proceed with this project.

3. You say, "This puzzle is an easy one in the atk galaxy." Can you estimate how long it would take an experienced solver to to complete it?

Thanks again,
Saul

[denis_berthier]

Hi Saul,

From what I see on amazon.com, it looks like the last one, "Pattern-Based Constraint Satisfaction and Logic Puzzles" is the best place to start.

AFAIK, it's the only book dealing with Kakuro with a theoretical background or with a pattern-based approach. It also includes all the apparently Kakuro-specific rules I could find on the web and it shows how they fit in my approach.

This uses a toy CSP solver written in python that I downloaded from http://labix.org/python-constraint. It works, but it's awfully slow on large puzzles.

What does "large" mean in this sentence: 12, 16, 25 ...?
As grid size increases, the number of candidates in Kakuro increases faster than for Sudoku grids of same size. Therefore, it is natural that the resolution time increases also.
Contrary to a general CSP solver (which is generally based on a combination of structured search and constraint propagation), my own CSP-Rules solver is based on finding a pattern-based solution, implementing the patterns (and only the patterns) defined in my books.
But complexity is inherent in the puzzles and CSP-Rules resolution time increases also with puzzle size. The difference is, I don't mind waiting for a readable "simplest" solution as in my previous post (because the corresponding problem is exponentially harder than just finding a solution), but I wouldn't like to wait for a T&E solution.

What I want the program to do is to look at the eliminations the user has entered so far,

which is readily modeled as the resolution state

and to choose the simplest rule that allows a further inference. (I have yet to decide what to do if he's made a mistake already.) Your theory appears to be ready-made for me.

Yes, that's exactly what the simplest-first strategy allows.
One more thing you have to decide however is, which levels of difficulty you want to deal with:
- most of the puzzles I've seen on the web can be solved with elementary cell-ctr interaction rules only (equivalent to whips[1]). Of course, this is only number crunching and I guess it becomes boring very soon;
- rules of type "surface sum" may help in some cases, but they somehow correspond to decomposable puzzles and lead to more number crunching; in a first implementation, it may be a good idea to avoid them (and puzzles that require them - most puzzles on atk do not require them);
- Subset rules can be defined in a way similar to those in Sudoku, with some care; as in Sudoku, their resolution power is limited;
- for harder puzzles (as for all the logic puzzles I've ever seen), although bivalue chains have some resolution power, some kinds of non reversible chain rules are necessary; my last book shows that whips and braids (which I have defined in a way meaningful for any CSP) are very powerful in Kakuro also.

1. It looks like your theory will be directly applicable to the hints, but as I haven't read your book, I don't know what you mean by "whips," for example. Am I correct in assuming that all your rules are ones that you expect a human to be able to apply in play?

You can have some idea of my rules (including whips) in the Sudoku context on my Sudoku web pages: http://www.carva.org/denis.berthier/HLS
They have also been discussed at length on this forum.
A version of whips and braids in the general CSP context is available in a conference paper, available in pdf form on my web page http://www.carva.org/denis.berthier
You can also read the introduction and the conclusion of my last book on its web page http://www.carva.org/denis.berthier/PBCS
As for your question, people with different views of solving may have different ideas, but whips can indeed be applied by players (and they have been applied in Sudoku).
What may be harder for a human player is to find the "simplest" whip solution, but "simplest" is an additional requirement.

2. Will I need any background in CSP in order to read your book? If so, can your recommend a source? I am only interested in getting the minimum necessary to proceed with this project.

The classical (but now dated) book on CS is Tsang. For more references on CSP, see Constraint_Satisfaction on Wikipedia.
However, my book is self-contained. It introduces all that is necessary to know about CSP (and mathematical logic) to read it, but it is in no way meant to be a general introduction to all the aspects of CSP solving (i.e. algorithmic, as it is generally understood).
If you decide to read it, I recommend that you do not read from page 1 to page 480. You can skip (or keep for a second reading) the hard proofs (e.g. confluence). You can even skip most of the general theory and start by the chapter on whips.

3. You say, "This puzzle is an easy one in the atk galaxy." Can you estimate how long it would take an experienced solver to to complete it?

Unfortunately, no. Contrary to Sudoku, for which there have been very active forums in the past, I know no Kakuro forum where such topics were discussed.
What I meant is, I have (err... CSP-Rules has) solved puzzles from atk requiring whips[9] (and may be more, I don't remember exactly). As complexity increases exponentially with whip size, I let you conclude.

[saul]

Denis,

Thanks for the prompt and detailed answer. I'll probably start out by reading the online sources you cited and move on to the book later. I've read the introduction to the book online, and the pseudocode given there is precisely what I had in mind. A good thing about this approach is that I can add rules one-by-one.

Denis wrote:

What does "large" mean in this sentence: 12, 16, 25 ...?

It's hard to say. I have an 11-by-11 that took it 6 hours, but it often solves a 13-by-13 in a minute or less. Of course, I've taken a very naive approach. I only have cell variables, and (except for the constraint that they must be integers from 1 to 9) the only constraints I have are that they can't be duplicated and must sum to the clues. This was too slow even for 9-by-9 puzzles, so I added some preprocessing. For each unit, I found the set of all numbers that could occur in a possible sum, and for each cell, I constrained its values to the intersection of the row and column sets. I didn't go any further. Once I decided on adding hints, I planned to make my solver classify puzzles as yours does, according to the most "advanced" rule used, and deferred any more work on the solver until I get the hint mechanism working in the client.

Denis wrote:

rules of type "surface sum" may help in some cases, but they somehow correspond to decomposable puzzles and lead to more number crunching; in a first implementation, it may be a good idea to avoid them (and puzzles that require them - most puzzles on atk do not require them)

That's very interesting. I have often had to use surface rules, sometimes of rather complex forms to make progress on the atk puzzles. By complex. I mean for example, the sum of two or three cells, not all in the same line, or the difference of two cells. One reason I decided to add hints to my program is because I found it hard to believe that these kinds of gyrations were really necessary. Still, I'm sure I'll try to implement these at some point, because the programming challenge to identify the patterns efficiently is very attractive.

I'm sure I'll have questions as I go along. I hope you'll allow me to ask you. If so, shall I just post my questions on this forum, or is there an email address you'd prefer me to write to?

Thanks again,
Saul

[denis_berthier]

Denis wrote:

What does "large" mean in this sentence: 12, 16, 25 ...?

It's hard to say. I have an 11-by-11 that took it 6 hours, but it often solves a 13-by-13 in a minute or less.

Yep, size is not meaningful at the individual puzzle level. I should have spoken of mean time for given size.
Can you post the 11x11 ?

Denis wrote:

rules of type "surface sum" may help in some cases, but they somehow correspond to decomposable puzzles and lead to more number crunching; in a first implementation, it may be a good idea to avoid them (and puzzles that require them - most puzzles on atk do not require them)

That's very interesting. I have often had to use surface rules, sometimes of rather complex forms to make progress on the atk puzzles. By complex. I mean for example, the sum of two or three cells, not all in the same line, or the difference of two cells. One reason I decided to add hints to my program is because I found it hard to believe that these kinds of gyrations were really necessary. Still, I'm sure I'll try to implement these at some point, because the programming challenge to identify the patterns efficiently is very attractive.

One of my results in PBCS is that, once combinations allowed by the sums have been computed, most Kakuro puzzles can be dealt with as pure logic puzzles, using only the interaction rules (and whips), with no additional arithmetic. Of course, sum rules or other arithmetic operations may occasionally simplify the solution.

I'm sure I'll have questions as I go along. I hope you'll allow me to ask you. If so, shall I just post my questions on this forum, or is there an email address you'd prefer me to write to?

I think the simplest way is to use this forum - for lack of one dedicated to Kakuro. Perhaps other people will get interested in Kakuro.

[saul]

Denis wrote:

Yep, size is not meaningful at the individual puzzle level. I should have spoken of mean time for given size.
Can you post the 11x11 ?

I have so far been just copying published puzzles manually, so I don't have sufficient samples for mean times to be meaningful. Here's is the 11-by-11https://dl.dropbox.com/u/24746182/6hours.pdf

Denis wrote:

One of my results in PBCS is that, once combinations allowed by the sums have been computed, most Kakuro puzzles can be dealt with as pure logic puzzles, using only the interaction rules (and whips), with no additional arithmetic. Of course, sum rules or other arithmetic operations may occasionally simplify the solution.

I'm sure that's so, but it's the interpaly between arithmetic and "pure logic" that attracts me to Karuko, I think. For a while, I was absolutely addicted to KenKen. On the other hand, Sudoku itself has never attracted me. So, I''m planning to implement some arithmetic rules. Just a matter of personal taste, of course.

Cheers,
Saul

[denis_berthier]

Here's is the 11-by-11https://dl.dropbox.com/u/24746182/6hours.pdf

There seems to be many possible applications of the surface rules. But even without these, with CSP-Rules, it is similar to the first one in this thread: it is in W3.

it's the interpaly between arithmetic and "pure logic" that attracts me to Karuko, I think. For a while, I was absolutely addicted to KenKen. On the other hand, Sudoku itself has never attracted me. So, I''m planning to implement some arithmetic rules. Just a matter of personal taste, of course.

When you consider Kakuro from an arithmetic POV, it is a linear programming problem and various surface rules allow to uncouple (at least partly) the variables, leading to a speed up of the linear programming algorithm. As I was mainly interested in the logic approach, I didn't investigate this in detail.
One of the difficult points I found in surface rules (apart from the easy ones), is identifying the relevant surfaces automatically. I'm interested if you have any idea on this point.

[saul]

Denis wrote:

When you consider Kakuro from an arithmetic POV, it is a linear programming problem and various surface rules allow to uncouple (at least partly) the variables, leading to a speed up of the linear programming algorithm. As I was mainly interested in the logic approach, I didn't investigate this in detail.

.
But there's no objective function, is there? Can you have a mathematical programming problem without an objective function? I can imagine that you have a constant objective function, so that it becomes just a matter of satisfying the constraints, but the techniques of LP don't seem applicable. Of course, this is ILP, which I've never studied, so I'm probably way off base.

Denis wrote:

One of the difficult points I found in surface rules (apart from the easy ones), is identifying the relevant surfaces automatically. I'm interested if you have any idea on this point.

No, I have no ideas yet. This is the programming challenge I find intriguing. I won't be thinking about it until after I get my program working. I don't seem to be getting any better at kakuro, and I want a program that will give me hints and help me improve.

[denis_berthier]

When you consider Kakuro from an arithmetic POV, it is a linear programming problem and various surface rules allow to uncouple (at least partly) the variables, leading to a speed up of the linear programming algorithm. As I was mainly interested in the logic approach, I didn't investigate this in detail.

.
But there's no objective function, is there? Can you have a mathematical programming problem without an objective function? I can imagine that you have a constant objective function, so that it becomes just a matter of satisfying the constraints, but the techniques of LP don't seem applicable. Of course, this is ILP, which I've never studied, so I'm probably way off base.

It'd be linear algebra if there was no condition of different values in each sector. If a single solution is assumed, the matrix (containing only 0's and 1's) is invertible.
But, due to these conditions, it is only (integer) linear programming. The objective function can be any function whose minimum ensures that all the values in each sector are different.

[saul]

Hi Denis,

I've been mulling over a couple of things you wrote.

Denis wrote:

It'd be linear algebra if there was no condition of different values in each sector. If a single solution is assumed, the matrix (containing only 0's and 1's) is invertible.
But, due to these conditions, it is only (integer) linear programming. The objective function can be any function whose minimum ensures that all the values in each sector are different.

As I understand this, we have variables x[r][c][k] which are 1 or 0 according as the digit in row r column c is or is not k. What I had been thinking of originally was having inequalities imposing the restriction that no digit can be repeated in a sector, and equations imposing the sum constraints; this left no scope for an objective function. Now, I can see making these equations into inequalities stating that the sum of the relevant x's is <= the clue. Then we can make the objective to maximize the sum of the x's. If the maximum is equal to the number of cells in the puzzle, there's a solution, but we don't know if it's unique. Is this what you have in mind?

I don't see how to do it as you say,

The objective function can be any function whose minimum ensures that all the values in each sector are different.

What I'm thinking of is doing away with the distinctness constraints and going back to equations for the sum. Then the objective function should minimize the number of repeated digits, but I can't come up with a linear function to do this. (As I write this, it occurs to me that I could try having a different function for each possible clue. For example, we would have one function for making 10 in 2, another for making 11 in 4, and so on. Then we would add them up over all sectors to get the objective function. This seems like an awful lot of work, besides being inelegant.) Am I on the wrong track?

Denis wrote,

One of my results in PBCS is that, once combinations allowed by the sums have been computed, most Kakuro puzzles can be dealt with as pure logic puzzles, using only the interaction rules (and whips), with no additional arithmetic.

I've been wondering how to interpret this. Do you mean that, after some preprocessing, the numbers could be replaced by labels without any algebraic structure, like colors, and the puzzle then solved like sudoku? I suppose I should read your book to find out, but I don't have time right now. Here is an example I have in mind:https://dl.dropbox.com/u/24746182/M31961.PNG
I solve this by noting that the sector in the top row doesn't have a 6. If it had no 9 either than the most that be made is 8+7+5+4+3=27, but this is impossible, since the sector must have a 1 or 2. Therefore the last digit in the sector must be 9, and the puzzle is quickly solved. Obviously, this inference wasn't available until I determined that the first digit in the sector immediately below was a 2 (which I did with a surface sum, incidentally.) Do you exclude this kind of reasoning when you speak of "pure logic?"

Thanks,
Saul

[denis_berthier]

I don't see how to do it as you say,

The objective function can be any function whose minimum ensures that all the values in each sector are different.

I had only hinted at the linear programming approach, without investigating it (as it cannot lead to any pattern-based solution, I'm not very interested). Indeed, you're right, it seems difficult to deal with the xi<>xj constraints via a LINEAR objective function. What's obvious is a polynomial one (but this is no longer linear programming):
- for any sector s, define Ps as the product of (xi - xj)^2, for all the xi<>xj in the sector;
- objective O: maximise the product of all the Ps over N.
If the puzzle is well posed, there's only one integer solution, with O <> 0. Therefore, it has to be the maximum of O over the sets of integers satisfying the sum conditions.
However, I don't know if this can be used in practice.

One of my results in PBCS is that, once combinations allowed by the sums have been computed, most Kakuro puzzles can be dealt with as pure logic puzzles, using only the interaction rules (and whips), with no additional arithmetic.

I've been wondering how to interpret this. Do you mean that, after some preprocessing, the numbers could be replaced by labels without any algebraic structure, like colors, and the puzzle then solved like sudoku?

Basically, YES. The "preprocessing" only consists of listing the combinations of digits allowed in each sector. The fundamental and obvious fact is, having the correct sum without repetition is equivalent to having one of the allowed combinations in the sector.

Technically, I introduce additional CSP variables representing these combinations. From what I've seen on the web, many players keep track of the possible combinations and they spend much time updating them.
The additional variables are the formal model for keeping track of the possible combinations. The interaction rules, e.g. "cell-to-horiz-ctr", ensure that the remaining combinations for a sector and the remaining digits for each of its white cells are consistent.

At this point, from a theoretical POV, digits could as well be replaced by colours, but there's no reason for doing so.
This approach is already illustrated in detail in the first solution I posted in this thread.

For the kind of moderately difficult puzzles you have been posting here (and even for significantly harder ones), I've found no example where this was not enough.
However, as I said previously, in some much harder puzzles, using more arithmetic (e.g. surface rules) may simplify the solving job.

Here is an example I have in mind:https://dl.dropbox.com/u/24746182/M31961.PNG
I solve this by noting that the sector in the top row doesn't have a 6. If it had no 9 either than the most that be made is 8+7+5+4+3=27, but this is impossible, since the sector must have a 1 or 2. Therefore the last digit in the sector must be 9, and the puzzle is quickly solved. Obviously, this inference wasn't available until I determined that the first digit in the sector immediately below was a 2 (which I did with a surface sum, incidentally.) Do you exclude this kind of reasoning when you speak of "pure logic?"

If the allowed combinations in each sector are precomputed, then you only have to propagate consistency between sector combinations and cell values (this is what you are doing here in a less systematic way).

BTW, which surface rule did you use to conclude that r3c7 = 2 ?

Here is the solution of this puzzle without using any surface rule. I asked CSP-Rules to print all the details, so that you can follow them, but the interaction rules should normally not be printed (they are obvious).
Notice that the obvious details of initialisation are not displayed. Initialisation ensures that, in each white cell, only the digits compatible with the horizontal and vertical sector sums are present at the start.
(This is the raw CSP-Rules output, with no hand editing at all.)

Hidden Text: Show

***** KakuRules 1.2 based on CSP-Rules 1.2, config: W *****
horizontal pseudo magic sector 36-in-6, starting in r3c6, for digits: (7 8 9)
horizontal magic sector 7-in-3, starting in r4c9, unique combination: 124
horizontal magic sector 3-in-2, starting in r5c1, unique combination: 12
horizontal magic sector 35-in-5, starting in r5c5, unique combination: 56789
horizontal magic sector 7-in-3, starting in r6c6, unique combination: 124
horizontal magic sector 45-in-9, starting in r7c2, unique combination: 123456789
horizontal magic sector 17-in-2, starting in r8c9, unique combination: 89
horizontal pseudo magic sector 33-in-5, starting in r9c3, for digits: (9)
horizontal magic sector 23-in-3, starting in r10c1, unique combination: 689
horizontal pseudo magic sector 23-in-6, starting in r10c6, for digits: (1 2 3 4)
horizontal pseudo magic sector 37-in-6, starting in r11c1, for digits: (7 8 9)
horizontal pseudo magic sector 17-in-5, starting in r12c1, for digits: (1 2 3)
vertical magic sector 24-in-3, starting in r9c3, unique combination: 789
vertical magic sector 7-in-3, starting in r1c4, unique combination: 124
vertical magic sector 17-in-2, starting in r2c5, unique combination: 89
vertical magic sector 7-in-3, starting in r6c6, unique combination: 124
vertical magic sector 45-in-9, starting in r2c7, unique combination: 123456789
vertical magic sector 16-in-2, starting in r9c9, unique combination: 79

horizontal-magic-sector: hr10c1 = 689
horizontal-magic-sector: hr8c9 = 89
horizontal-magic-sector: hr7c2 = 123456789
horizontal-magic-sector: hr6c6 = 124
horizontal-magic-sector: hr5c5 = 56789
horizontal-magic-sector: hr5c1 = 12
horizontal-magic-sector: hr4c9 = 124
vertical-magic-sector: vr9c9 = 79
vertical-magic-sector: vr2c7 = 123456789
vertical-magic-sector: vr6c6 = 124
vertical-magic-sector: vr2c5 = 89
vertical-magic-sector: vr1c4 = 124
vertical-magic-sector: vr9c3 = 789

naked-single ==> r12c3 = 7
naked-single ==> r10c9 = 7
naked-single ==> r11c9 = 9
naked-single ==> r9c6 = 4
naked-single ==> r5c6 = 5
naked-single ==> r5c2 = 2
naked-single ==> r5c3 = 1
naked-single ==> r4c12 = 4
naked-single ==> r4c10 = 2
naked-single ==> r4c11 = 1
naked-single ==> r2c4 = 4
naked-single ==> hr2c2 = 48
naked-single ==> r2c3 = 8
naked-single ==> vr1c10 = 2789
naked-single ==> vr1c12 = 489
naked-single ==> vr3c2 = 29
naked-single ==> r4c2 = 9
naked-single ==> r4c5 = 8
naked-single ==> r3c5 = 9
naked-single ==> hr3c2 = 139
naked-single ==> r3c3 = 3
naked-single ==> r3c4 = 1
naked-single ==> r4c4 = 2
naked-single ==> vr1c3 = 135789
naked-single ==> hr4c1 = 123589
naked-single ==> r4c6 = 1
naked-single ==> r4c3 = 5
naked-single ==> r4c7 = 3
naked-single ==> vr3c6 = 15
naked-single ==> hr9c3 = 45789
naked-single ==> hr11c8 = 139
naked-single ==> hr10c6 = 123467
naked-single ==> r10c8 = 6
naked-single ==> vr8c8 = 69
naked-single ==> r9c8 = 9
naked-single ==> hr12c1 = 12347
naked-single ==> r12c6 = 4
naked-single ==> vr10c6 = 49
naked-single ==> r11c6 = 9
naked-single ==> r11c3 = 8
naked-single ==> r10c3 = 9

ctr-to-verti-sector ==> r2c11 <> 2
ctr-to-verti-sector ==> r3c11 <> 2
ctr-to-verti-sector ==> r2c11 <> 6
ctr-to-verti-sector ==> r3c11 <> 6
cell-to-verti-ctr ==> vr9c2 <> 239
cell-to-verti-ctr ==> vr9c2 <> 149
cell-to-verti-ctr ==> vr8c4 <> 1239
cell-to-verti-ctr ==> vr10c5 <> 19
ctr-to-verti-sector ==> r12c5 <> 1
cell-to-verti-ctr ==> vr10c5 <> 46
ctr-to-verti-sector ==> r11c5 <> 4
ctr-to-verti-sector ==> r11c5 <> 6
cell-to-verti-ctr ==> vr6c5 <> 169
cell-to-verti-ctr ==> vr6c5 <> 349
cell-to-verti-ctr ==> vr9c10 <> 249
cell-to-verti-ctr ==> vr9c10 <> 258
cell-to-verti-ctr ==> vr9c10 <> 267
ctr-to-verti-sector ==> r10c10 <> 2
ctr-to-verti-sector ==> r12c10 <> 2
cell-to-verti-ctr ==> vr9c10 <> 456
cell-to-verti-ctr ==> vr8c4 <> 2346
cell-to-verti-ctr ==> vr4c8 <> 245
ctr-to-verti-sector ==> r7c8 <> 5
cell-to-verti-ctr ==> vr5c4 <> 45
ctr-to-verti-sector ==> r7c4 <> 4
ctr-to-verti-sector ==> r7c4 <> 5
cell-to-verti-ctr ==> vr4c9 <> 359
cell-to-verti-ctr ==> vr4c9 <> 368
ctr-to-verti-sector ==> r7c9 <> 3
cell-to-verti-ctr ==> vr6c10 <> 37
ctr-to-verti-sector ==> r7c10 <> 3
ctr-to-verti-sector ==> r7c10 <> 7
cell-to-verti-ctr ==> vr6c10 <> 46
ctr-to-verti-sector ==> r7c10 <> 4
ctr-to-verti-sector ==> r7c10 <> 6
cell-to-verti-ctr ==> vr8c12 <> 35
ctr-to-verti-sector ==> r10c12 <> 3
cell-to-verti-ctr ==> vr9c2 <> 257
cell-to-verti-ctr ==> vr9c2 <> 347
cell-to-verti-ctr ==> vr8c4 <> 1257
cell-to-verti-ctr ==> vr8c4 <> 1347
ctr-to-verti-sector ==> r11c4 <> 7
ctr-to-verti-sector ==> r9c4 <> 7
verti-sector-to-ctr ==> vr10c5 <> 28
naked-single ==> vr10c5 = 37
naked-single ==> r12c5 = 3
naked-single ==> r11c5 = 7
cell-to-verti-ctr ==> vr9c2 <> 356
ctr-to-verti-sector ==> r11c2 <> 3
verti-sector-to-ctr ==> vr9c2 <> 167
ctr-to-verti-sector ==> r10c2 <> 6

naked-single ==> r10c2 = 8
naked-single ==> r10c4 = 6
naked-single ==> vr8c4 = 1356
naked-single ==> r12c4 = 1
naked-single ==> r12c2 = 2
naked-single ==> r9c4 = 5
naked-single ==> r11c4 = 3
naked-single ==> hr11c1 = 346789
naked-single ==> vr9c2 = 248
naked-single ==> r11c2 = 4
naked-single ==> r11c7 = 6

cell-to-verti-ctr ==> vr6c5 <> 259
ctr-to-verti-sector ==> r7c5 <> 9
verti-sector-to-ctr ==> vr9c10 <> 159
ctr-to-verti-sector ==> r12c10 <> 9
verti-sector-to-ctr ==> vr9c10 <> 357
ctr-to-verti-sector ==> r12c10 <> 7

biv-chain[2]: vr9c10{n168 n348} - r11c10{n1 n3} ==> r12c10 <> 3
cell-to-horiz-ctr ==> hr12c9 <> 37
ctr-to-horiz-sector ==> r12c11 <> 3
ctr-to-horiz-sector ==> r12c11 <> 7
biv-chain[2]: vr9c10{n168 n348} - r11c10{n1 n3} ==> r10c10 <> 3
hidden-single-for-magic-digit-in-horizontal-sector ==> r10c11 = 3
naked-single ==> r11c11 = 1
naked-single ==> r11c10 = 3
naked-single ==> vr9c10 = 348
naked-single ==> r10c10 = 4
naked-single ==> r12c10 = 8
naked-single ==> hr12c9 = 28
naked-single ==> r12c11 = 2
naked-single ==> vr6c11 = 123689
biv-chain[2]: vr6c10{n19 n28} - r8c10{n9 n8} ==> r7c10 <> 8
biv-chain[2]: hr6c2{n69 n78} - r6c3{n9 n7} ==> r6c4 <> 7
cell-to-verti-ctr ==> vr5c4 <> 27
ctr-to-verti-sector ==> r7c4 <> 2
ctr-to-verti-sector ==> r7c4 <> 7
biv-chain[2]: vr5c4{n18 n36} - r6c4{n8 n6} ==> r7c4 <> 6
biv-chain[2]: r9c12{n6 n7} - hr9c10{n69 n78} ==> r9c11 <> 6
naked-pairs-in-a-column c11{r8 r9}{n8 n9} ==> r7c11 <> 9
naked-pairs-in-a-column c11{r8 r9}{n8 n9} ==> r7c11 <> 8
naked-single ==> r7c11 = 6
whip[2]: r6c4{n8 n6} - vr5c4{n18 .} ==> r7c4 <> 8
whip[2]: r8c10{n9 n8} - vr6c10{n19 .} ==> r7c10 <> 9
naked-pairs-in-a-row r7{c6 c10}{n1 n2} ==> r7c9 <> 2
naked-pairs-in-a-row r7{c6 c10}{n1 n2} ==> r7c9 <> 1
naked-pairs-in-a-row r7{c6 c10}{n1 n2} ==> r7c8 <> 2
naked-pairs-in-a-row r7{c6 c10}{n1 n2} ==> r7c8 <> 1
naked-pairs-in-a-row r7{c6 c10}{n1 n2} ==> r7c7 <> 2
naked-pairs-in-a-row r7{c6 c10}{n1 n2} ==> r7c7 <> 1
naked-pairs-in-a-row r7{c6 c10}{n1 n2} ==> r7c5 <> 2
naked-pairs-in-a-row r7{c6 c10}{n1 n2} ==> r7c5 <> 1
naked-pairs-in-a-row r7{c6 c10}{n1 n2} ==> r7c4 <> 1
naked-single ==> r7c4 = 3
naked-single ==> vr5c4 = 36
naked-single ==> r6c4 = 6
naked-single ==> hr6c2 = 69
naked-single ==> r6c3 = 9
naked-single ==> r7c3 = 7
cell-to-verti-ctr ==> vr6c5 <> 367
cell-to-verti-ctr ==> vr4c8 <> 137
ctr-to-verti-sector ==> r5c8 <> 7
cell-to-verti-ctr ==> vr4c8 <> 236
biv-chain[2]: vr4c8{n128 n146} - r7c8{n8 n4} ==> r6c8 <> 4
biv-chain[2]: r5c8{n6 n8} - r7c8{n8 n4} ==> vr4c8 <> 128
naked-single ==> vr4c8 = 146
naked-single ==> r6c8 = 1
naked-single ==> r5c8 = 6
naked-single ==> r7c8 = 4
cell-to-verti-ctr ==> vr4c9 <> 467
cell-to-verti-ctr ==> vr4c9 <> 179
verti-sector-to-ctr ==> vr4c9 <> 269
ctr-to-verti-sector ==> r7c9 <> 9
hidden-single-in-magic-horiz-sector ==> r7c7 = 9
ctr-to-verti-sector ==> r5c9 <> 9
hidden-single-in-magic-horiz-sector ==> r5c10 = 9
cell-to-horiz-ctr ==> hr2c7 <> 34569
naked-pairs-in-a-column c7{r5 r9}{n7 n8} ==> r3c7 <> 8
naked-pairs-in-a-column c7{r5 r9}{n7 n8} ==> r3c7 <> 7
biv-chain[2]: r9c5{n7 n8} - r7c5{n8 n5} ==> vr6c5 <> 268
ctr-to-verti-sector ==> r8c5 <> 6
ctr-to-verti-sector ==> r8c5 <> 2
horiz-sector-to-ctr ==> hr8c4 <> 126
biv-chain[2]: hr8c4{n135 n234} - r8c6{n1 n2} ==> r8c7 <> 2
biv-chain[2]: r8c6{n1 n2} - hr8c4{n135 n234} ==> r8c7 <> 1
biv-chain[2]: r8c6{n1 n2} - hr8c4{n135 n234} ==> r8c5 <> 1
cell-to-verti-ctr ==> vr6c5 <> 178
biv-chain[2]: hr8c4{n135 n234} - r8c6{n1 n2} ==> r8c7 <> 2
biv-chain[2]: r8c6{n1 n2} - hr8c4{n135 n234} ==> r8c7 <> 1
biv-chain[2]: r8c6{n1 n2} - hr8c4{n135 n234} ==> r8c5 <> 1
cell-to-verti-ctr ==> vr6c5 <> 178
biv-chain[2]: hr8c4{n135 n234} - r8c7{n5 n4} ==> r8c5 <> 4
verti-sector-to-ctr ==> vr6c5 <> 457
naked-single ==> vr6c5 = 358
naked-single ==> r9c5 = 8
naked-single ==> r7c5 = 5
naked-single ==> r7c9 = 8
naked-single ==> r5c9 = 7
naked-single ==> r5c7 = 8
naked-single ==> r8c5 = 3
naked-single ==> r9c7 = 7
naked-single ==> vr4c9 = 278
naked-single ==> r6c9 = 2
naked-single ==> r6c7 = 4
naked-single ==> r8c7 = 5
naked-single ==> hr8c4 = 135
naked-single ==> r8c6 = 1
naked-single ==> r7c6 = 2
naked-single ==> r7c10 = 1
naked-single ==> vr6c10 = 19
naked-single ==> r8c10 = 9
naked-single ==> r8c11 = 8
naked-single ==> r9c11 = 9
naked-single ==> hr9c10 = 69
naked-single ==> r9c12 = 6
naked-single ==> vr8c12 = 26
naked-single ==> r10c12 = 2
naked-single ==> r10c7 = 1
naked-single ==> r3c7 = 2
naked-single ==> hr3c6 = 246789
cell-to-verti-ctr ==> vr1c8 <> 35
ctr-to-verti-sector ==> r2c8 <> 3
ctr-to-verti-sector ==> r2c8 <> 5
biv-chain[2]: vr1c8{n17 n26} - r3c8{n7 n6} ==> r2c8 <> 6
whip[2]: r3c8{n7 n6} - vr1c8{n17 .} ==> r2c8 <> 7
cell-to-horiz-ctr ==> hr2c7 <> 34578
whip[2]: vr1c9{n18 n27} - r3c9{n4 .} ==> r2c9 <> 7
whip[2]: vr1c9{n18 n36} - r3c9{n4 .} ==> r2c9 <> 6
horiz-sector-to-ctr ==> hr2c7 <> 24678
horiz-sector-to-ctr ==> hr2c7 <> 23679
horiz-sector-to-ctr ==> hr2c7 <> 15678
horiz-sector-to-ctr ==> hr2c7 <> 14679
horiz-sector-to-ctr ==> hr2c7 <> 13689
whip[2]: vr1c9{n18 n45} - r3c9{n6 .} ==> r2c9 <> 4
whip[2]: vr1c9{n27 n18} - r3c9{n4 .} ==> r2c9 <> 8
whip[2]: vr1c11{n139 n157} - r3c11{n4 .} ==> r2c11 <> 7
whip[2]: vr1c11{n148 n139} - r3c11{n4 .} ==> r2c11 <> 9
entering level S3 with <Fact-60360>
entering level BC3 with <Fact-60362>
entering level W3 with <Fact-60374>
whip[3]: r2c12{n8 n9} - r3n9{c12 c11} - vr1c11{n157 .} ==> r2c11 <> 8
cell-to-horiz-ctr ==> hr2c7 <> 12789
whip[2]: r2c8{n2 n1} - hr2c7{n24579 .} ==> r2c9 <> 2
cell-to-verti-ctr ==> vr1c9 <> 27
ctr-to-verti-sector ==> r3c9 <> 7
whip[2]: r2c10{n8 n7} - hr2c7{n23589 .} ==> r2c12 <> 8
naked-single ==> r2c12 = 9
naked-single ==> r3c12 = 8
naked-single ==> r3c10 = 7
naked-single ==> r3c8 = 6
naked-single ==> r3c9 = 4
naked-single ==> r3c11 = 9
naked-single ==> r2c10 = 8
naked-single ==> vr1c11 = 139
naked-single ==> r2c11 = 3
naked-single ==> hr2c7 = 23589
naked-single ==> r2c8 = 2
naked-single ==> r2c9 = 5
naked-single ==> vr1c9 = 45
naked-single ==> vr1c8 = 26
GRID SOLVED. rating-type = W, MOST COMPLEX RULE = Whip[3]

------------
--84---25839
--319-264798
-952813--214
-21--58679--
--96--412---
--735294816-
----315--98-
---58479--96
-896--167432
-483796-931-
-27134---82-

[saul]

Thanks. I'm not really interested in the linear programming solution to Kakuro either, since it cannot show uniqueness. Besides, I'm primarily interested in this as an amusing puzzle, and linear programming is not relevant to that. (I did find a quadratic objective function. If n[d] is the number of times d occurs in a given sector, then n[d](n[d]-1) will be 0 iff d isn't repeated. Sum over all digits d and over all sectors to get the function to minimize. I don't know anything about quadratic programming, though; in particular, I don't know if there has been any progress on integer quadratic programming. I'm done thinking about this, however.)

Denis wrote:

BTW, which surface rule did you use to conclude that r3c7 = 2 ?

Well, by then I has deduced the values in the sector r4c10 through r4c12, and also the value in r5c10, so there was an easy surface sum available, consisting of the top two sectors on the right-hand side of the board.

[denis_berthier]

I did find a quadratic objective function. If n[d] is the number of times d occurs in a given sector, then n[d](n[d]-1) will be 0 iff d isn't repeated. Sum over all digits d and over all sectors to get the function to minimize.

n(d) is not linear in d.

[saul]

No, it's linear in the x[r][c][k].