The New Sudoku Players' Forum

[fponticelli]

Hello Forum, I am trying to generate nice looking and engaging Kakuro puzzle for an app I am building. I searched this forum and the internet and found some information but not a lot of guidance. What are the best strategies to achieve the goal? I already have a brute force solver that is good enough to find unique solutions and I think I can generate empty schemas quite easily, the problem is how to fill those with sensical digit

Thank you!

[denis_berthier]

Hello Forum, I am trying to generate nice looking and engaging Kakuro puzzle for an app I am building. I searched this forum and the internet and found some information but not a lot of guidance. What are the best strategies to achieve the goal? I already have a brute force solver that is good enough to find unique solutions and I think I can generate empty schemas quite easily, the problem is how to fill those with sensical digit

Hi Ponticelli
Welcome to this forum.

I've never generated kakuros, but I've solved a lot of them. And there's the general top-down procedure in Sudoku that can be applied to generate almost any logic puzzle.
There are several steps you'll need to take:
1) decide the size of the grid; small sizes tend to have trivial solutions (but not always);
2) decide the positions of the blacks cells, in particular whether there will be almost closed regions; such regions allow to trivially cut the puzzle into several almost independent pieces; whether this is desirable or not depends on one's opinion about them; this allows to have arbitrarily large grids that remain easy to solve (but probably boring);
3) once the pattern of black cells is fixed, fill in the white cells with digits respecting the non-repeating conditions in each sector;
4) fill in all the black cells with row and column sums;
5) decide whether you want pure Kakuro (no data in the white cells) or not;
6) depending on your answer to the previous question, erase all or part of the white cell data;
7) check that there's a unique solution; if not, add white cell data or restart from 3 (or 2)
8) progressively erase horizontal or vertical sums until you get a puzzle that fits your criteria for goodness.
.


Notice that minimality of the data is not taken into account because the normal solver doesn't care about it.
But you can easily add it, as in any top-down generator.

As an example of interesting Kakuros, check the ATK website: https://www.atksolutions.com/games/kakuro.html. IMO, they have the best Kakuros.

[fponticelli]

Thank you for taking the time to provide such detailed answer. My problem is definitely with step 3. I tried that and I get in the situation where I have to backtrack too many times accumulating too many 'paths' in the process which generally ends with a non terminating process. Also I will not have an idea of the difficulty if I use a fully random approach.

[denis_berthier]

My problem is definitely with step 3. I tried that and I get in the situation where I have to backtrack too many times accumulating too many 'paths' in the process which generally ends with a non terminating process. Also I will not have an idea of the difficulty if I use a fully random approach.

In Sudoku generation, it's difficult to have an a priori idea of the difficulty of puzzles. Generally, puzzles are filtered for difficulty after being generated.

In Kakuro, there's the same problem. However, there are several factors you can use to partially control it a priori: grid size, sizes of the various sectors, sector sums. The more combinations each sector can have, the harder the puzzle may be (but other factors may play a role, such as black cell positions, e.g. long diagonal bands of white cells tend to make the puzzle harder).
The easiest puzzles use only sectors with magic digits. Next level may use pseudo-magic ones...
See sections 15.1.3 to 15.1.5 of my book [PBCS] for details about these notions and about numbers of combinations.
.

[fponticelli]

I see you published quite a few titles, which one would be the best to learn more?

[fponticelli]

PBCS: "Pattern-Based Constraint Satisfaction and Logic Puzzles", makes sense

[fponticelli]

Book ordered

[denis_berthier]

Yes, [PBCS] (any edition] is now the best place to learn about my approach.
Notice that all my publications are freely available in pdf form:
- on ResearchGate: https://www.researchgate.net/profile/Denis-Berthier
- and in the Publications folder of CSP-Rules on GitHub: https://github.com/denis-berthier/CSP-Rules-V2.1

[PBCS] has a full chapter about Kakuro.
CSP-Rules has a fully developed application for Kakuro: KakuRules. [UMNR] has all the explanations on how to solve Kakuros with it. Incidentally, it can also rate Kakuros according to my standard ratings, e.g. the W or gW ratings, w or w/o Subsets. If you have a look at the Kakuro chapter in [PBCS] or at KakuRules, don't miss the g-whip part. Kakuro provides the most beautiful (and hardest) example of g-candidates and g-whips. Super-Hiden Subsets (Fish) are also interesting.

However, you will not find anything there about the generation of Kakuros.
.