TYPED-CHAINS in KAKURO

For fans of Kakuro

TYPED-CHAINS in KAKURO

Postby denis_berthier » Mon Jun 15, 2020 6:05 am


TYPED-CHAINS in KAKURO


In another thread (http://forum.enjoysudoku.com/typed-chains-2d-chains-t37823.html), I defined various kinds of typed-chains (typed-bivalue-chains, typed-z-chains, typed-t-whips and typed-whips), that are special cases of the long established untyped versions.

All the examples I gave there are for Sudoku. Indeed, Sudoku is the more natural case for typed-chains, as there are 4 kinds of CSP-Variables, corresponding to the 4 2D-spaces introduced as early as 2007 in "The Hidden Logic of Sudoku".

However, there are many ways the CSP-Variables of a puzzle can be typed. In Kakuro as I modelled it, there are three natural kinds of CSP-Variables:
    - rc, representing the white cells
    - hrc, representing the combinations allowed for a horizontal sector (and attached to a black cell)
    - vrc, representing the combinations allowed for a vertical sector (and attached to a black cell)
Unfortunately, if these 3 "natural" kinds were taken as 3 types, the resulting typed-chains would be of little interest.

A more interesting typing system would allow to restrict chains to sectors*. And that's what I've just done for Kakuro:
For each horizontal sector, represented by it's controller (black) cell (ri, cj) and named correspondingly hricj, the following three kinds of CSP-Variables are assigned the hricj type
    - hricj (the variable representing the allowed combinations for this horizontal sector)
    - ri'cj' for any white rc-cell (ri' cj') in the sector
    - ri'nk' for any rn-cell (ri' nk') in the sector

Similarly, for each vertical sector, represented by it's controller (black) cell (ri, cj) and named correspondingly vricj, 3 similar kinds of CSP-Variables are assigned type vricj

Remark: CSP-Variables corresponding to (white) rc-cells have two types, which is not a problem in CSP-Rules ("type" is not a function but a predicate). I didn't have to make any change to the generic typed-chain rules for making them work with these definitions.

(*) The first time I met the idea of solving a puzzle using only patterns in a single sector at a time was in an example by Mathimagic (http://forum.enjoysudoku.com/24-x-14-kakuro-challenge-t37104.html). I don't know how usual it is to make such a distinction. But that clearly makes a puzzle much simpler to solve. The only interaction between sectors is via assertions and eliminations in the white cells.

Remark: few puzzles are solvable by chain rules limited to a sector at a time.
I have to leave now, but I'll give an example in my next post.
denis_berthier
2010 Supporter
 
Posts: 1540
Joined: 19 June 2007
Location: Paris

TYPED-CHAINS in KAKURO - Example

Postby denis_berthier » Mon Jun 15, 2020 11:41 am

This 10x10 example is puzzle M42942 from http://www.atksolutions.com/games/kakuro.html

The calling function from CSP-Rules is:
Code: Select all
(solve 10
   ;;; horizontal data
   28 . . . . . . 12 . . /
   39 . . . . . . 9 . . /
   B B 17 . . 11 . . . . /
   31 . . . . . 23 . . . /
   16 . . 19 . . . 14 . . /
   22 . . . 15 . . . . . /
   19 . . . . 11 . . B B /
   5 . . 32 . . . . . . /
   9 . . 38 . . . . . . //

   ;;; vertical data
   7 . . 39 . . . . . . /
   16 . . 23 . . . . . . /
   30 . . . . 13 . . B B /
   33 . . . . . 18 . . . /
   6 . . 15 . . . 13 . . /
   20 . . . 27 . . . . . /
   B B 11 . . 27 . . . . /
   23 . . . . . . 5 . . /
  38 . . . . . . 6 . . //
)

It has a solution in W3 (I have kept both typed and untyped chains in the solution, in order to show how they easily live together):
Hidden Text: Show
naked-pairs-in-verti-sector: c10{r4 r7}{n3 n5} ==> r6c10 ≠ 5, r3c10 ≠ 5, r3c10 ≠ 3, r2c10 ≠ 5, r2c10 ≠ 3
biv-chain-vr1c6[2]: vr1c6{n15 n24} - r3c6{n5 n4} ==> r2c6 ≠ 4
biv-chain-vr1c6[2]: vr1c6{n24 n15} - r3c6{n4 n5} ==> r2c6 ≠ 5
biv-chain-vr1c9[2]: vr1c9{n123458 n123467} - r5c9{n8 n6} ==> r3c9 ≠ 6, r6c9 ≠ 6
singles
z-chain-hr8c1[2]: r8c3{n3 n2} - hr8c1{n3457 .} ==> r8c5 ≠ 3
whip-hr8c1[2]: r8c3{n2 n3} - hr8c1{n2458 .} ==> r8c5 ≠ 2
naked-single ==> vr7c5 = 567
whip-vr4c6[2]: r7c6{n2 n1} - vr4c6{n249 .} ==> r6c6 ≠ 2, r5c6 ≠ 2
whip-hr8c6[2]: hr8c6{n56 n29} - r8c8{n6 .} ==> r8c7 ≠ 9
whip-hr8c6[2]: hr8c6{n56 n38} - r8c8{n6 .} ==> r8c7 ≠ 8
whip-hr8c6[2]: hr8c6{n38 n56} - r8c8{n8 .} ==> r8c7 ≠ 6
z-chain-vr5c7[2]: r8c7{n5 n2} - r7c7{n2 .} ==> vr5c7 ≠ 24678
whip-hr8c1[2]: hr8c1{n3457 n2467} - r8c2{n5 .} ==> r8c5 ≠ 6
naked-pairs-in-verti-sector: c5{r8 r9}{n5 n7} ==> r10c5 ≠ 7
naked-single ==> r10c5 = 6
singles
biv-chain-hr5c1[2]: r5c3{n4 n3} - hr5c1{n45679 n35689} ==> r5c5 ≠ 4
biv-chain-hr5c1[2]: hr5c1{n45679 n35689} - r5c3{n4 n3} ==> r5c5 ≠ 3
whip-hr6c4[2]: hr6c4{n469 n478} - r6c6{n6 .} ==> r6c5 ≠ 8
whip-vr4c6[2]: vr4c6{n168 n159} - r6c6{n6 .} ==> r5c6 ≠ 9
x-wing-in-horiz-sectors: n9{r4 r5}{c4 c5} ==> r6c5 ≠ 9, r3c5 ≠ 9, r3c4 ≠ 9, r2c5 ≠ 9, r2c4 ≠ 9
biv-chain-hr6c4[2]: hr6c4{n478 n469} - r6c5{n7 n6} ==> r6c6 ≠ 6
biv-chain-vr4c6[2]: vr4c6{n159 n168} - r6c6{n9 n8} ==> r5c6 ≠ 8
naked-pairs-in-horiz-sector: r5{c2 c6}{n5 n6} ==> r5c5 ≠ 6, r5c5 ≠ 5, r5c4 ≠ 6
whip-vr1c2[2]: vr1c2{n34 n16} - r3c2{n4 .} ==> r2c2 ≠ 6
whip-vr1c2[2]: vr1c2{n34 n25} - r3c2{n4 .} ==> r2c2 ≠ 5
whip-vr1c2[2]: vr1c2{n25 n34} - r3c2{n5 .} ==> r2c2 ≠ 4
biv-chain[3]: vr1c7{n569 n578} - r3n9{c7 c3} - r2c3{n9 n7} ==> r2c7 ≠ 7
whip-vr1c7[2]: vr1c7{n569 n578} - r2c7{n9 .} ==> r3c7 ≠ 8
x-wing-in-horiz-sectors: n8{r3 r4}{c4 c5} ==> r5c5 ≠ 8, r5c4 ≠ 8, r2c5 ≠ 8, r2c4 ≠ 8
singles
hidden-pairs-in-horiz-sector: r3{n7 n9}{c3 c7} ==> r3c7 ≠ 6
stte


If we use only typed-chains, it requires typed-whips of length 5:
Hidden Text: Show
singles
naked-pairs-in-verti-sector: c10{r4 r7}{n3 n5} ==> r6c10 ≠ 5, r3c10 ≠ 5, r3c10 ≠ 3, r2c10 ≠ 5, r2c10 ≠ 3
biv-chain-vr1c6[2]: vr1c6{n15 n24} - r3c6{n5 n4} ==> r2c6 ≠ 4
biv-chain-vr1c6[2]: vr1c6{n24 n15} - r3c6{n4 n5} ==> r2c6 ≠ 5
biv-chain-vr1c9[2]: vr1c9{n123458 n123467} - r5c9{n8 n6} ==> r3c9 ≠ 6, r6c9 ≠ 6
z-chain-hr8c1[2]: r8c3{n3 n2} - hr8c1{n3457 .} ==> r8c5 ≠ 3
whip-hr8c1[2]: r8c3{n2 n3} - hr8c1{n2458 .} ==> r8c5 ≠ 2
naked-single ==> vr7c5 = 567
whip-vr4c6[2]: r7c6{n2 n1} - vr4c6{n249 .} ==> r6c6 ≠ 2, r5c6 ≠ 2
whip-hr8c6[2]: hr8c6{n56 n29} - r8c8{n6 .} ==> r8c7 ≠ 9
whip-hr8c6[2]: hr8c6{n56 n38} - r8c8{n6 .} ==> r8c7 ≠ 8
whip-hr8c6[2]: hr8c6{n38 n56} - r8c8{n8 .} ==> r8c7 ≠ 6
z-chain-vr5c7[2]: r8c7{n5 n2} - r7c7{n2 .} ==> vr5c7 ≠ 24678
whip-hr8c1[2]: hr8c1{n3457 n2467} - r8c2{n5 .} ==> r8c5 ≠ 6
naked-pairs-in-verti-sector: c5{r8 r9}{n5 n7} ==> r10c5 ≠ 7
singles
biv-chain-hr5c1[2]: r5c3{n4 n3} - hr5c1{n45679 n35689} ==> r5c5 ≠ 4
biv-chain-hr5c1[2]: hr5c1{n45679 n35689} - r5c3{n4 n3} ==> r5c5 ≠ 3
whip-hr6c4[2]: hr6c4{n469 n478} - r6c6{n6 .} ==> r6c5 ≠ 8
whip-vr4c6[2]: vr4c6{n168 n159} - r6c6{n6 .} ==> r5c6 ≠ 9
x-wing-in-horiz-sectors: n9{r4 r5}{c4 c5} ==> r6c5 ≠ 9, r3c5 ≠ 9, r3c4 ≠ 9, r2c5 ≠ 9, r2c4 ≠ 9
biv-chain-hr6c4[2]: hr6c4{n478 n469} - r6c5{n7 n6} ==> r6c6 ≠ 6
biv-chain-vr4c6[2]: vr4c6{n159 n168} - r6c6{n9 n8} ==> r5c6 ≠ 8
naked-pairs-in-horiz-sector: r5{c2 c6}{n5 n6} ==> r5c5 ≠ 6, r5c5 ≠ 5, r5c4 ≠ 6
whip-vr1c2[2]: vr1c2{n34 n16} - r3c2{n4 .} ==> r2c2 ≠ 6
whip-vr1c2[2]: vr1c2{n34 n25} - r3c2{n4 .} ==> r2c2 ≠ 5
whip-vr1c2[2]: vr1c2{n25 n34} - r3c2{n5 .} ==> r2c2 ≠ 4
z-chain-hr2c1[3]: r2c3{n7 n9} - r2c7{n9 n8} - r2c4{n8 .} ==> hr2c1 ≠ 123589
z-chain-hr2c1[3]: r2c3{n7 n9} - r2c7{n9 n6} - r2c4{n6 .} ==> hr2c1 ≠ 134569
whip-hr2c1[3]: r2c3{n9 n7} - r2c4{n7 n8} - r2c7{n8 .} ==> hr2c1 ≠ 134578
whip-hr2c1[3]: r2c4{n8 n7} - r2c3{n7 n9} - r2c7{n9 .} ==> hr2c1 ≠ 124579
whip-hr2c1[4]: r2c3{n7 n9} - hr2c1{n124678 n123679} - r2c4{n8 n6} - r2c7{n6 .} ==> r2c5 ≠ 7
whip-hr2c1[4]: hr2c1{n123679 n124678} - r2c3{n9 n7} - r2c4{n7 n6} - r2c7{n6 .} ==> r2c5 ≠ 8
whip-vr1c5[2]: vr1c5{n36789 n45789} - r2c5{n6 .} ==> r3c5 ≠ 4
whip-hr2c1[5]: hr2c1{n124678 n123679} - r2c5{n4 n6} - r2c4{n6 n7} - r2c3{n7 n9} - r2c7{n9 .} ==> r2c2 ≠ 3
stte
Last edited by denis_berthier on Fri Jun 19, 2020 5:06 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1540
Joined: 19 June 2007
Location: Paris

Re: TYPED-CHAINS in KAKURO

Postby denis_berthier » Mon Jun 15, 2020 12:00 pm

This second example is M13101 from the same website.


Code: Select all
(solve 10
   ;;; horizontal data
   B B B 11 . . . . B B /
   B B 34 . . . . . . . /
   16 . . . B B 22 . . . /
   10 . . B 15 . . . B B /
   B 37 . . . . . . . B /
   B 22 . . . . B 7 . . /
   14 . . B B B 13 . . . /
   33 . . . . . .  . B B /
   B B 27 . . . . B B B //

   ;;; vertical data
   B B 17 . . B 17 . . B /
   B B 31 . . . . . .  B /
   B 3 . . 6 . . 15 . . /
   10 . . B 4 . . 13 . . /
   7 . . 22 . . . 9 . . /
   3 . . 16 . . B 4 . . /
   18 . . . . . 16 . . B /
   B 13 . . 17 . . . B B /
   B 17 . . B 3 . . B B //
)

It is in both W3 and TyW3. Here is the solution with typed-chains:
Hidden Text: Show
singles
naked-pairs-in-horiz-sector: r3{c4 c7}{n1 n2} ==> r3c8 ≠ 2, r3c8 ≠ 1, r3c6 ≠ 2, r3c6 ≠ 1, r3c5 ≠ 2, r3c5 ≠ 1
biv-chain-vr8c4[2]: vr8c4{n69 n78} - r10c4{n9 n8} ==> r9c4 ≠ 8
biv-chain-vr8c4[2]: vr8c4{n78 n69} - r10c4{n8 n9} ==> r9c4 ≠ 9
biv-chain-vr8c5[2]: vr8c5{n49 n58} - r10c5{n9 n8} ==> r9c5 ≠ 8
biv-chain-vr8c5[2]: vr8c5{n58 n49} - r10c5{n8 n9} ==> r9c5 ≠ 9
biv-chain-hr5c1[2]: hr5c1{n19 n28} - r5c2{n9 n8} ==> r5c3 ≠ 8
biv-chain-hr5c1[2]: hr5c1{n28 n19} - r5c2{n8 n9} ==> r5c3 ≠ 9
biv-chain-hr7c8[2]: hr7c8{n16 n25} - r7c10{n1 n2} ==> r7c9 ≠ 2
biv-chain-hr7c8[2]: hr7c8{n25 n16} - r7c10{n2 n1} ==> r7c9 ≠ 1
biv-chain-hr8c1[2]: hr8c1{n59 n68} - r8c2{n9 n8} ==> r8c3 ≠ 8
biv-chain-hr8c1[2]: hr8c1{n68 n59} - r8c2{n8 n9} ==> r8c3 ≠ 9
biv-chain-hr3c3[2]: r3c4{n2 n1} - r3c7{n1 n2} ==> hr3c3 ≠ 1345678
z-chain-hr8c7[2]: r8c10{n2 n1} - hr8c7{n247 .} ==> r8c9 ≠ 2
z-chain-hr8c7[2]: r8c8{n9 n7} - hr8c7{n139 .} ==> r8c9 ≠ 9
whip-hr8c7[2]: r8c8{n7 n9} - hr8c7{n157 .} ==> r8c9 ≠ 7
whip-hr7c2[2]: r7c5{n1 n3} - hr7c2{n1489 .} ==> r7c4 ≠ 1, r7c3 ≠ 1
cell-to-horiz-ctr ==> hr7c2 ≠ 1678
whip-hr7c2[2]: hr7c2{n3568 n2389} - r7c4{n4 .} ==> r7c3 ≠ 2
whip-hr7c2[2]: r7c5{n3 n1} - hr7c2{n2389 .} ==> r7c3 ≠ 3
whip-hr5c5[2]: r5c7{n7 n9} - hr5c5{n267 .} ==> r5c8 ≠ 7, r5c6 ≠ 7
whip-hr5c5[2]: r5c7{n9 n7} - hr5c5{n159 .} ==> r5c6 ≠ 9
biv-chain-vr4c6[2]: r5c6{n6 n5} - vr4c6{n679 n589} ==> r6c6 ≠ 6, r7c6 ≠ 6
biv-chain-vr4c6[2]: vr4c6{n679 n589} - r5c6{n6 n5} ==> r6c6 ≠ 5, r7c6 ≠ 5
z-chain-hr5c5[2]: hr5c5{n357 n267} - r5c6{n5 .} ==> r5c8 ≠ 6
whip-hr5c5[2]: r5c6{n5 n6} - hr5c5{n159 .} ==> r5c8 ≠ 5
whip-hr4c1[2]: r4c4{n2 n1} - hr4c1{n259 .} ==> r4c3 ≠ 2
whip-hr4c1[2]: r4c4{n1 n2} - hr4c1{n169 .} ==> r4c3 ≠ 1
whip-hr4c1[2]: r4c2{n9 n8} - hr4c1{n169 .} ==> r4c3 ≠ 9
whip-hr4c1[2]: r4c2{n8 n9} - hr4c1{n178 .} ==> r4c3 ≠ 8
z-chain-vr3c3[2]: r4c3{n7 n6} - r8c3{n6 .} ==> vr3c3 ≠ 134689
z-chain-vr3c3[2]: r4c3{n7 n5} - r8c3{n5 .} ==> vr3c3 ≠ 234589
whip-vr5c9[2]: r7c9{n5 n6} - vr5c9{n359 .} ==> r8c9 ≠ 5, r6c9 ≠ 5
whip-vr5c9[2]: r8c9{n4 n3} - vr5c9{n458 .} ==> r6c9 ≠ 4
whip-vr5c9[2]: r8c9{n3 n4} - vr5c9{n359 .} ==> r6c9 ≠ 3
whip-vr5c9[2]: r7c9{n6 n5} - vr5c9{n368 .} ==> r6c9 ≠ 6
whip-vr1c8[2]: vr1c8{n12456 n12348} - r4c8{n5 .} ==> r6c8 ≠ 8, r3c8 ≠ 8
whip-vr5c4[2]: vr5c4{n24 n15} - r7c4{n2 .} ==> r6c4 ≠ 5
whip-vr2c9[2]: vr2c9{n67 n49} - r4c9{n5 .} ==> r3c9 ≠ 9
whip-vr1c6[2]: vr1c6{n25 n34} - r2c6{n1 .} ==> r3c6 ≠ 3
whip-vr1c5[2]: vr1c5{n28 n37} - r2c5{n1 .} ==> r3c5 ≠ 3
whip-vr1c6[2]: vr1c6{n34 n25} - r3c6{n4 .} ==> r2c6 ≠ 5
singles
hidden-pairs-in-verti-sector: c8{n1 n2}{r5 r6} ==> r6c8 ≠ 7, r6c8 ≠ 6, r6c8 ≠ 4, r6c8 ≠ 3, r5c8 ≠ 3
biv-chain-vr1c8[2]: vr1c8{n12456 n12357} - r4c8{n6 n7} ==> r3c8 ≠ 7
biv-chain-vr1c8[2]: r4c8{n6 n7} - vr1c8{n12456 n12357} ==> r3c8 ≠ 6
biv-chain-hr3c3[2]: hr3c3{n1235689 n1234789} - r3c9{n6 n7} ==> r3c5 ≠ 7
singles
naked-triplets-in-horiz-sector: r6{c6 c7 c9}{n8 n9 n7} ==> r6c3 ≠ 9, r6c3 ≠ 8, r6c3 ≠ 7
z-chain-hr6c2[3]: r6c8{n1 n2} - hr6c2{n1345789 n1246789} - r6c5{n3 .} ==> r6c4 ≠ 1
cell-to-verti-ctr ==> vr5c4 ≠ 15
naked-single ==> vr5c4 = 24
whip-hr7c2[2]: r7c4{n4 n2} - hr7c2{n1489 .} ==> r7c3 ≠ 4
z-chain-hr6c2[3]: r6c8{n1 n2} - hr6c2{n1345789 n1246789} - r6c5{n3 .} ==> r6c3 ≠ 1
z-chain-hr9c1[3]: r9c2{n9 n8} - hr9c1{n1235679 n1234689} - r9c8{n7 .} ==> r9c3 ≠ 9
t-whip-hr9c1[3]: r9c8{n7 n9} - r9c2{n9 n8} - hr9c1{n1235679 .} ==> r9c3 ≠ 7, r9c4 ≠ 7
singles
biv-chain-hr9c1[2]: hr9c1{n1245678 n1235679} - r9c2{n8 n9} ==> r9c8 ≠ 9
stte
Last edited by denis_berthier on Fri Jun 19, 2020 5:08 am, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1540
Joined: 19 June 2007
Location: Paris

Re: TYPED-CHAINS in KAKURO

Postby Mathimagics » Tue Jun 16, 2020 7:13 am

Hi Denis,

Do you think that these additional methods might make a difference when applied to computationally difficult puzzles? (such as these)

Cheers
MM
User avatar
Mathimagics
2017 Supporter
 
Posts: 1532
Joined: 27 May 2015
Location: Canberra

Re: TYPED-CHAINS in KAKURO

Postby denis_berthier » Tue Jun 16, 2020 9:07 am

Mathimagics wrote:Hi Denis,
Do you think that these additional methods might make a difference when applied to computationally difficult puzzles? (such as these)

Hi Mathimagics
Definitely not. Typed-chains are special cases of the corresponding non-typed ones. They add no resolution power.
But, on the contrary, in the present case of Kakuro and with the present definition of types related to sectors, they may help isolate easy puzzles that do not require complex considerations involving several sectors at a time.

Two other points related to the referenced link:
1) CSP-Rules (and any of the included applications) is absolutely not targeted at fast solving. I fear it would be considered terribly slow compared to any really fast solver. The purpose is not only to get a solution but to get a resolution path with the simplest hardest step, a problem exponentially harder.
Just to give you an idea, the puzzle in the last example (M13101) takes :
- 2.23s when only whips and Subsets are activated
- 3.28s when only Subsets and all the typed chains are activated
- 3.73s when Subsets and all the typed+untyped chains are activated.
Every additional pattern that has to be tested during resolution has its cost.

2) CSP-Rules is not targeted at the hardest of the hardest puzzles. It is targeted at puzzles solvable by a human solver (and it goes indeed much beyond). In practice, considering my universal T&E-depth classification, this means that CSP-Rules will give:
- a full resolution path for puzzles in T&E(1) or gT&E(1)
- only a classification in some BpB for puzzles in T&E(2)
- nothing beyond
denis_berthier
2010 Supporter
 
Posts: 1540
Joined: 19 June 2007
Location: Paris

Re: TYPED-CHAINS in KAKURO

Postby Mathimagics » Tue Jun 16, 2020 9:48 am

Ok, I get it, thanks! 8-)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1532
Joined: 27 May 2015
Location: Canberra

Re: TYPED-CHAINS in KAKURO

Postby denis_berthier » Thu Jun 18, 2020 10:25 am

Hi Mathimagics,
Somewhere, you said you had a Kakuro generator able to find some puzzles solvable in each sector separately (and you gave this http://forum.enjoysudoku.com/24-x-14-kakuro-challenge-t37104.html as an example.
It's unclear to me what exactly you do in each sector, but whips restricted to fixed sectors are not enough for this puzzle.
If it doesn't take too much time, could you generate a few of such puzzles in some readable format, so that I can test them with my new typed-chains?
denis_berthier
2010 Supporter
 
Posts: 1540
Joined: 19 June 2007
Location: Paris

Re: TYPED-CHAINS in KAKURO

Postby Mathimagics » Thu Jun 18, 2020 1:25 pm

Hi Denis,

Just to be clear, I classify a puzzle as "linearly solvable" if it can be solved by (sector-based) cell candidate eliminations.

These eliminations are obtained solely by the process of testing, for each candidate value (D) in a cell (R, C), whether or not setting cell (R, C) = D allows the horizontal and vertical sectors that intersect at this cell to be completed to the applicable sum.

The linear solver simply makes multiple passes over the grid, removing candidates, applying forced moves (singles) until either the grid is complete or no more eliminations can be performed. I believe that nearly all puzzles intended for human consumption (ie P&P solving) are linearly solvable.

The simplest format for exchanging Kakuro puzzles is the solution grid. For example here is ATK "M13101", which you mention above, and which is linearly solvable:

Code: Select all
...1325..
..2941378
871...769
91..591..
.6418729.
.8239..52
95....931
8465217..
..9873...


I have many, many 24x14 puzzles with this property, and here are a few ...

Example 1: Show
Code: Select all
94.9864.26.41
7564321.45293
.8954321.31..
97861..249561
8643215.57983
.21..4396875.
79.938.834627
63942.8712436
5123.8432.315
..35142.87.79
916.2769.49..
8679.613.5398
..15.9562.146
31.86.97542..
732.4978.8769
9854763.79845
846312.417.28
.5463721..41.
19782.9265783
678593..13692
..97.6312485.
52316.1538972
31.29.6849.31

Example 2: Show
Code: Select all
..573124.824.
25684379.9687
56897.6825471
132659874.123
.89.271534.62
82431..312654
9417.97.68795
31.24631.13..
..213.6539874
976524831.451
451.75462193.
26.586.795.47
.93167284.421
142.925463718
2847593.512..
..69.84976.24
32516.17.2695
631298..65879
51.576829.48.
984.432187569
7634859.25134
8421.14938256
.913.217593..

Example 3: Show
Code: Select all
896.14253.19.
152643789.289
.214356789.16
973.21564893.
61.35789.1523
..496.3215.79
9862.24196358
431.7613.21..
512347.487659
7654892.64528
32.268194.217
..2135.6394..
679.134257.79
21345.7428956
527894.514237
..49.6789.123
89526147.2798
96.3821.215..
6231.32418.13
.79685324.132
48.798513264.
239.798351264
.15.67958.321


Cheers
MM
User avatar
Mathimagics
2017 Supporter
 
Posts: 1532
Joined: 27 May 2015
Location: Canberra

Re: TYPED-CHAINS in KAKURO

Postby denis_berthier » Thu Jun 18, 2020 3:23 pm

Mathimagics wrote:Hi Denis,
Just to be clear, I classify a puzzle as "linearly solvable" if it can be solved by (sector-based) cell candidate eliminations.
These eliminations are obtained solely by the process of testing, for each candidate value (D) in a cell (R, C), whether or not setting cell (R, C) = D allows the horizontal and vertical sectors that intersect at this cell to be completed to the applicable sum.
The linear solver simply makes multiple passes over the grid, removing candidates, applying forced moves (singles) until either the grid is complete or no more eliminations can be performed.

I see. That defines a higher level of difficulty than my current typed-chains, though still in the easy to medium range. I think I could define a second way of typing the chains that could cover (most of) this. When I have time, I'll code it in KakuRules (I have no problem in keeping two different typing systems and leaving the choice to the user).

Mathimagics wrote:I believe that nearly all puzzles intended for human consumption (ie P&P solving) are linearly solvable.

You may be right if you consider extra large puzzles as the 3 you mentioned. But not for normal sized puzzles.

Mathimagics wrote:The simplest format for exchanging Kakuro puzzles is the solution grid.

This format is ambiguous, unless you mean that all the horizontal and vertical sums must be given (which is very restrictive).
For a more general format, I suggest something along the lines of mine (in the examples above), inspired by crosswords (separate definitions for rows and columns).
denis_berthier
2010 Supporter
 
Posts: 1540
Joined: 19 June 2007
Location: Paris

Re: TYPED-CHAINS in KAKURO

Postby Mathimagics » Fri Jun 19, 2020 9:42 am

For puzzles where sums may be omitted, or for any reason the solution grid itself is not appropriate, I use this format:

Code: Select all
XXXXXX..XXXX
XXXXXXX.XXXX
XX.XX.XX.XXX
XXX.XXXXX.XX
.XX.XXXXXXXX
..XXXXX.XXXX
XXXX.XXXXX..
XXXXXXXX.XX.
XX.XXXXX.XXX
XXX.XX.XX.XX
XXXX.XXXXXXX
XXXX..XXXXXX

HS = 35 28 29 12 13 3 16 17 14 15 6 10 44 29 30 30 15 42 8 17 16 12 17 16 12 8 13 41 28 38
VS = 11 38 28 27 17 34 21 8 28 12 25 19 7 38 40 17 22 29 14 14 9 9 34 10 24 18 37 24


This is (or was at some point) ATK's "H54261".
User avatar
Mathimagics
2017 Supporter
 
Posts: 1532
Joined: 27 May 2015
Location: Canberra


Return to Kakuro