The New Sudoku Players' Forum

Website · by **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:

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

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.

Website · by **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

If we use only typed-chains, it requires typed-whips of length 5:

Hidden Text: Show

Website · by **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

by **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

Website · by **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 :
- 1.25s when only whips are activated
- 1.27s when only whips and Subsets are activated
- 1.52s when only Subsets and all the typed chains are activated
- 1.71s 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

by **Mathimagics** » Tue Jun 16, 2020 9:48 am

Ok, I get it, thanks! 8-)

Website · by **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?

by **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

Example 2: Show

Example 3: Show

Cheers
MM

Website · by **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).

by **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".

The New Sudoku Players' Forum

TYPED-CHAINS in KAKURO

TYPED-CHAINS in KAKURO

TYPED-CHAINS in KAKURO - Example

Re: TYPED-CHAINS in KAKURO

Re: TYPED-CHAINS in KAKURO

Re: TYPED-CHAINS in KAKURO

Re: TYPED-CHAINS in KAKURO

Re: TYPED-CHAINS in KAKURO

Re: TYPED-CHAINS in KAKURO

Re: TYPED-CHAINS in KAKURO

Re: TYPED-CHAINS in KAKURO