Mathimagics wrote:denis_berthier wrote:But the point I'd like to clarify is about generation: are you saying that, when you create a random complete solution grid, fill in all the sums, and then delete all the givens in the white cells, it has almost always multiple solutions ?

Yes! I believe that I can demonstrate this with a simple experiment. I will report back on later, when I've knocked up some code!

I now understand why some puzzle creators produce puzzles with givens in the white cells. It's easy with the following modified algorithm:

- choose grid size and pattern of black cells

- choose a complete solution grid

- fill in all the sums

- delete one by one the givens in the white cells until you get a minimal puzzle or there remains no white given (as in any top-down generator, backtrack when necessary if you hit a multi-sol puzzle).

At the end, you get a 1-sol puzzle, possibly with white givens (and possibly not minimal, but you can go on and start deleting sums).

Mathimagics wrote:denis_berthier wrote:Probably, an important criteria for Kakuro is the density of black cells. It is obviously related to the mean size of sectors. Interestingly, it seems that having a medium value for this mean size does not reduce the difficulty: sectors with the largest number of possibilities are those with length close to 4 - 5.

Did you check how your "infinitesimal" chances above vary with this density (say for fixed 10x10 grid size)?

No, but I have not really got that far. I suspect, however, that this is much less important.

Then we have very different intuitions about this point. Consider the extreme cases for 10x10 grids and my first naïve algorithm in a previous post:

- least possible density of black cells, i.e. 19% : chances of getting a unique valid Kakuro puzzle = chances of getting a unique valid Latin Square = 0% (the back cells carry no real information, S = 45, every LS is a solution, independently of the complete LS you chose to start the procedure);

- highest possible density of black cells, i.e. about +50% (chessboard pattern + black border): chances of getting a valid Kakuro puzzle = 100% (each black cell fully determines a white one).

Of course, nothing guarantees that the chances vary smoothly with density; on the contrary, I think there are other factors; but what I wanted to hint to is, density must be a major factor.

The second main factor, I think, is the pattern of black cells. Some patterns create almost isolated sub-puzzles, some patterns have large diagonal white bands (making in general the puzzles harder).

Mathimagics wrote:Thanks, by the way, for mentioning atk, I had not come across it before. I really need a source of puzzles that are well-graded, so having that available is very useful.

I consider it as the best Kakuro website (and the best website also for other games: Futoshiki, ...).

One think you need to know about atk is, the puzzles are not generated online but randomly chosen from a predefined database.

Indeed, considering their patterns of black cells, there is almost no chance for their puzzles to be generated fully automatically. Unfortunately for us (or mainly

you, because

I don't plan to write a generator), they don't want give any real information about their generation process.

Second thing you need to know is, their puzzles go by families, related by isomorphisms: modify the last two digits in the puzzle number and you get another member of the family.