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.
