24 x 14 Kakuro Challenge

For fans of Kakuro

Re: 24 x 14 Kakuro Challenge

Postby creint » Mon Jan 27, 2020 4:44 pm

For each calculation constraint I get the eliminations, and apply them all at once. In my solver I can see from which constraint they came.
It combines only 1 calculation constraint and the underlying alldifferent and allsame constraint.
Calculations have a single operator and single comparator.

Do you have a better name for the strategy?
creint
 
Posts: 171
Joined: 20 January 2018

Re: 24 x 14 Kakuro Challenge

Postby denis_berthier » Tue Jan 28, 2020 12:54 am

creint wrote:For each calculation constraint I get the eliminations, and apply them all at once. In my solver I can see from which constraint they came.
It combines only 1 calculation constraint and the underlying alldifferent and allsame constraint.
Calculations have a single operator and single comparator.
Do you have a better name for the strategy?

It's not a matter of name.

Let me take your first eliminations for the left upper part, step by step:
creint wrote:[horizontal] Sum 17 in 2 cells then only 8 and 9 are possible in a cell. 8+9 or 9+8
[horizontal] Sum 14 in 2 cell then only 5689 are possible in a cell. 5+9, 6+8, 8+6, 9+5

Until now, (almost) same as me

creint wrote:[vertical]Sum 14 in 2 cells digits 569, 56 then only 9+5 is possible.

Which "calculation constraint" inside the vertical sector allows you to conclude that only 9+5 is possible?
denis_berthier
2010 Supporter
 
Posts: 1540
Joined: 19 June 2007
Location: Paris

Re: 24 x 14 Kakuro Challenge

Postby creint » Tue Jan 28, 2020 5:57 pm

In this puzzle this does not happen, it was just an example on how the logic works.

5+5 invalid because of all-different
5+6 invalid because 11 instead of 14
6+5 invalid because 11 instead of 14
6+6 invalid because of all-different
9+5 valid because of 14
9+6 invalid because 15 instead of 14

You could debug this if you have my solver, how do you want to receive it?
creint
 
Posts: 171
Joined: 20 January 2018

Re: 24 x 14 Kakuro Challenge

Postby denis_berthier » Tue Jan 28, 2020 10:42 pm

creint wrote:In this puzzle this does not happen, it was just an example on how the logic works.

5+5 invalid because of all-different
5+6 invalid because 11 instead of 14
6+5 invalid because 11 instead of 14
6+6 invalid because of all-different
9+5 valid because of 14
9+6 invalid because 15 instead of 14

Maybe we are not clear about what we're talking about.
We're speaking of your third line: "Sum 14 in 2 cells digits 569, 56 then only 9+5 is possible". Nothing at this point, but 14 in 2 cells, vertically restricts the content of these two cells. i.e. they can only be 5+9, 6+8, 8+6 or 9+5. My question is, how do you conclude that only 9+5 is possible? Or is there anything else before this 3rd line?

[Edit] About possible bugs in your solver. I don't think it's the point. Logic puzzles like Kakuro or Sudoku are so constrained that if your solver can solve properly 10 of them, the likelihood it makes illegitimate eliminations is very small.
denis_berthier
2010 Supporter
 
Posts: 1540
Joined: 19 June 2007
Location: Paris

Re: 24 x 14 Kakuro Challenge

Postby creint » Wed Jan 29, 2020 4:34 pm

creint wrote:Sum 14 in 2 cells digits 569, 56 then only 9+5 is possible.

So cell 1 contains digits 569 and cell 2 contains digits 56.
I gave the contents of the example cells as extra restriction to my example.

No there is no bug in my solver, but maybe it can be useful if you want to debug your solver.
Your solver did use other methods like x-wing that are not needed.
creint
 
Posts: 171
Joined: 20 January 2018

Re: 24 x 14 Kakuro Challenge

Postby denis_berthier » Wed Jan 29, 2020 10:05 pm

creint wrote:
creint wrote:Sum 14 in 2 cells digits 569, 56 then only 9+5 is possible.

So cell 1 contains digits 569 and cell 2 contains digits 56.
I gave the contents of the example cells as extra restriction to my example.

No there is no bug in my solver, but maybe it can be useful if you want to debug your solver.
Your solver did use other methods like x-wing that are not needed.


The rules used for this puzzle have solved millions of puzzles. Very unlikely they have a bug.
But you don't answer my question about your 3rd elimination. My point is, apart from the vertical constraint 14-in-2, it must use other constraints. And what you call "calculations" must indeed combine constraints.
denis_berthier
2010 Supporter
 
Posts: 1540
Joined: 19 June 2007
Location: Paris

Re: 24 x 14 Kakuro Challenge

Postby Mathimagics » Thu Jan 30, 2020 6:58 am

A reminder of this puzzle's properties - it is solvable by means of simple eliminations, where each unsolved cell is considered in the context of both local contraints - the horizontal and vertical sectors.

It's fairly clear that the sector in question, ie {V(3,3), L=2, S=14} (L = length, S = sum) fixes (3,3) = 9, (3,4) = 5.

This would apply if the solver didn't operate on a cell-by-cell basis, but only on individual sectors. The horizontal sector for (3,4) restricts it to {123457}, so any subsequent check on the vertical sector would reach the same conclusion, ie (3,4) = 5.

There seems to be a bone of contention, but I'm not sure what that bone really is ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1532
Joined: 27 May 2015
Location: Canberra

Re: 24 x 14 Kakuro Challenge

Postby denis_berthier » Thu Jan 30, 2020 7:50 am

Mathimagics wrote:It's fairly clear that the sector in question, ie {V(3,3), L=2, S=14} (L = length, S = sum) fixes (3,3) = 9, (3,4) = 5.
This would apply if the solver didn't operate on a cell-by-cell basis, but only on individual sectors. The horizontal sector for (3,4) restricts it to {123457}, so any subsequent check on the vertical sector would reach the same conclusion, ie (3,4) = 5.

Of course, I agree with this conclusion, considering the horizontal sector 22-in-6 and then the vertical sector 14-in-2. (As you can see in my resolution path, this appears at the beginning, among a lot of similar initial singles.)

Mathimagics wrote:There seems to be a bone of contention, but I'm not sure what that bone really is ...

There was no contention. I tried to make creint provide clearer explanations of what his "calculations" are.

But my point is, the whole puzzle cannot be solved using only information from one sector at a time (and with no T&E). I still have to see a proof of the contrary, with a detailed statement of all the individual steps - if anyone claims the contrary, which I'm not even sure at this point.
denis_berthier
2010 Supporter
 
Posts: 1540
Joined: 19 June 2007
Location: Paris

Re: 24 x 14 Kakuro Challenge

Postby Mathimagics » Thu Jan 30, 2020 3:41 pm

denis_berthier wrote:But my point is, the whole puzzle cannot be solved using only information from one sector at a time (and with no T&E).

For Sudoku T&E generally means setting a cell to a candidate value and then testing the resulting grid. "Can (R, C) be D?" is the question. Can the puzzle be completed, or is there some contradiction found that enables the candidate's removal from the cell's domain (candidate list). So for me, T&E solving involves some form of DFS, ie "look-ahead".

For Kakuro, however, the same question "Can cell (R, C) be D?" can be asked in two different ways :

  • can this puzzle be completed with (R, C) = D? (DFS/look-ahead)
  • can this sector be completed with (R, C) = D? (simple arithmetic)

If we have a sector of length 3, with sum = 16, and the current candidates for the 3 cells are {1, 4}, {3, 5, 7}, and {6, 7, 9}, then the question "can the second cell be 7?" has answer "no", because you can't make a sum of 9 out of the first and third cells.

These are single-sector context tests, and don't involve any look-ahead, so for me this particular type of test is not the same as T&E. And the puzzle is solvable using information from one sector at a time.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1532
Joined: 27 May 2015
Location: Canberra

Re: 24 x 14 Kakuro Challenge

Postby denis_berthier » Thu Jan 30, 2020 10:41 pm

Mathimagics wrote:For Kakuro, however, the same question "Can cell (R, C) be D?" can be asked in two different ways :
  • can this puzzle be completed with (R, C) = D? (DFS/look-ahead)
  • can this sector be completed with (R, C) = D? (simple arithmetic)
If we have a sector of length 3, with sum = 16, and the current candidates for the 3 cells are {1, 4}, {3, 5, 7}, and {6, 7, 9}, then the question "can the second cell be 7?" has answer "no", because you can't make a sum of 9 out of the first and third cells.
These are single-sector context tests, and don't involve any look-ahead, so for me this particular type of test is not the same as T&E.

I guess this could be debated, but it's a matter of names (I'd call this local T&E or maybe local DFS if you indeed have to make more than one assumption at a time). It's sure that T&E in a single sector is much simpler than in the whole grid. However, if you need 2 levels of assumptions (do you?), it becomes more complicated to compare with a single level on the whole grid.

Mathimagics wrote:And the puzzle is solvable using information from one sector at a time.

I've checked my resolution path and I see that almost all the bivalue-chains, whips and g-whips appearing in it are in a single sector. They take care for this kind of local T&E.
Some of the chains use several sectors, but this doesn't allow any conclusion, because KakuRules arbitrarily choses one of the shortest chains available, whether they span one sector or several.
I could probably write specific rules with these chains restricted to a single sector (they would be particular cases of the general definition - in the same way as Subsets are restricted to sectors), but I don't have much motivation for it at this point.
denis_berthier
2010 Supporter
 
Posts: 1540
Joined: 19 June 2007
Location: Paris

Previous

Return to Kakuro