The New Sudoku Players' Forum

[Mathimagics]

The atk puzzle interface is the display of black cells for me is horrible, and not exactly printer friendly! Makes me wonder whether atk has shares in a laser cartridge company!

Is there some way I can get the display mode to change?

[Mathimagics]

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.

Are you sure? Have you been there lately?

If you have "database" check flag set, it looks for "puzzle id" in the database.

If you have "database" unchecked, it definitely looks like its running a generator, one that appears from the progress bar to be a progressive generation with backtracking. It takes some time for large hard puzzles to generate (but impressively, not that long!)

[denis_berthier]

I did some analysis of the probability P(N,D) of getting a grid of NxN cells using D symbols, and that system being unique.

The conditions of the experiment are not quite clear. For fixed N and D, you have a "file of hsum/vsum keys", for the outer black cells and for some inner ones, I guess. But how are the latter chosen? And how are the keys chosen?

[denis_berthier]

The atk puzzle interface is the display of black cells for me is horrible, and not exactly printer friendly! Makes me wonder whether atk has shares in a laser cartridge company!
Is there some way I can get the display mode to change?

Not any that I'm aware of

[denis_berthier]

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.

Are you sure? Have you been there lately?
If you have "database" check flag set, it looks for "puzzle id" in the database.
If you have "database" unchecked, it definitely looks like its running a generator, one that appears from the progress bar to be a progressive generation with backtracking. It takes some time for large hard puzzles to generate (but impressively, not that long!)

I've been using it for years. I just tried again. But I can't find any "database check flag" (I'm on Safari on a Mac). Where exactly do you find this flag?
What I see in the new features (last line of the Kakuro page) is:
"New v2.24: To randomly choose a puzzle from say the hard level 8 series... simply click on the "select puzzle" icon and enter H8... a random puzzle will call up from H8 like for example H82342. you can type in the level E, M, H followed by the series number... this will work on all levels ... a few examples: E8, E1, E4, M2, M9, H8, H5 ... etc..."

[Mathimagics]

Aaagh! I'm such an idiot, I somehow got hooked up to the site linked at the top of this thread!

A thousand pardons, I should have twigged. But it does look like he is definitely doing generation, as I described ...

Sadly he has not come back to share his algorithm!

Sorry also for making myself clear about my experiment! It was very very late at night ....

You remember that the original idea was to demonstrate the unlikelihood of getting a useful Kakuro puzzle out of a random generator, ie. by generating a valid grid at random and then calculating the block sums, hoping to stumble across one that is well-formed, ie unique for those blocksums

The only way I could easily do that was to take an NxN grid, all cells being white, with "vsums" being the sum of each column, and "hsum" the sum of each row. I generate all the valid squares, write them to a file and then sort them by the row/column sums. I then load the sorted file and only then can I tell which sum combinations are unique, and thus get a reasonable estimate of the probability of a random square being a unique combination, by counting the number of sum combinations that were unique.


I was forced to introduce digit range restrictions because of the impossibly huge numbers of records I would have to create. The D value is simply the maximum value allowed in the grid. Ideally we'd like to use 9, but you can see from the first table how impractical that is.

The priniciple is still the same, imagine a Kakuro grid that just used 1 to 8, or 1 to 7.

[denis_berthier]

I somehow got hooked up to the site linked at the top of this thread! [...]But it does look like he is definitely doing generation, as I described ...

I agree that kakuro-online does online generation. I'ven't tried many of their puzzles but all the "hard" ones I tried were terribly easy and boring.

You remember that the original idea was to demonstrate the unlikelihood of getting a useful Kakuro puzzle out of a random generator, ie. by generating a valid grid at random and then calculating the block sums, hoping to stumble across one that is well-formed, ie unique for those blocksums
The only way I could easily do that was to take an NxN grid, all cells being white, with "vsums" being the sum of each column, and "hsum" the sum of each row. I generate all the valid squares, write them to a file and then sort them by the row/column sums. I then load the sorted file and only then can I tell which sum combinations are unique, and thus get a reasonable estimate of the probability of a random square being a unique combination, by counting the number of sum combinations that were unique.

OK, now I understand. But I don't know if it allows any conclusion about real Kakuros with inner black cells.

Sticking to my idea of density of black cells as a main parameter for the probability of having a 1-sol puzzle, and considering the propagation bar in the Kakuro-online generator, I suppose what they are doing for their "random" generator is the following:
1) choose size
2) choose some pattern of inner black cells (necessary for large size), maybe from a fixed database of patterns
3) fill in a complete Kakuro grid with this pattern
OR: 2+3) choose some complete Kakuro grid from a fixed database
4) compute the sums
5) delete the white givens one by one until just before multi-sol (maybe with some backtracking in order to delete more givens)
6) for each remaining white given, add an inner black cell (replacing this given), modify and complete the sums accordingly - this would be when you see the bar fluctuating, near the end of generation; the real process may be different, but black cells are somehow added, unless they start the whole thing with only high density patterns
7) if it doesn't work (i.e. can't delete all the white givens without loosing uniqueness), restart from 5

Simple, but the result is a very high density of black cells and easy puzzles

[Mathimagics]

One of the problems with not having even a basic generator is that it makes it difficult to investigate the properties of "good" puzzles due to a lack of data. The process of manually transcribing puzzles from the internet, or even from printed form is a pretty tedious one.

I think we can agree that the number of well-formed puzzles for a given empty grid (black cell distribution) is tiny compared to the number of valid grids, ie. white squares all filled in subject to "all different within a block" rule. In fact I think it can be shown to be infinitesmally small.

One wonders whether in the fact all the well-formed cases are nevertheless connected in some way, which makes me think of the research (now lost) I was doing on the (now defunct) Sudoku programmers forum.

There's a method based on Markov chains - you start with a known solution, and then perform some kind of perturbation to take you to another one. While the result of the perturbation is highly likely to an invalid solution, you keep going until you arrive at a new one.

The point is, if the solution space exhibits any combinatorial structure, you can usually find another solution in much less time than a random walk. Several orders of magnitude in fact.

For example, the problem we were considering was how to generate a random "Sudoku regions" layout, ie. a partitioning of the grid into 9 contiguous regions of any shape. (these are called Gerechte designs).

The solution space (any partitioning 81 cells into 9 sets, not necessarily contiguous) there was also huge, but I found a way of defining a perturbation that when applied to a starting grid was able to arrive at another one with relatively few intermediate steps.

Anyway, it might tell us something useful about the properties of those elusive well-defined puzzle layouts.

[Mathimagics]

OK, now I understand. But I don't know if it allows any conclusion about real Kakuros with inner black cells.

Oh I think it does. Remember I started before with a grid (black cell pattern) taken from a real puzzle, then generated random entries, and it ran for days without coming anywhere near a well-formed state. Given the huge number of possible states for even very small square formats, it's clear to me why that was so.

I agree that increasing black cell density eventually leads to a diminishing number of possible states, but that doesn't mean the relationship is linear!

Your description of the way the Kakuro-online generator might be working sounds quite feasible.

[denis_berthier]

I think we can agree that the number of well-formed puzzles for a given empty grid (black cell distribution) is tiny compared to the number of valid grids, ie. white squares all filled in subject to "all different within a block" rule. In fact I think it can be shown to be infinitesmally small.

Not without some hypothesis on the density of black cells (see my previous example: max density, chessboard pattern).

As for the random walk approach you mention, I've used it long ago in totally different contexts, never for puzzle generation. On this forum, people who have used it (for Sudoku) are eleven, blue, champagne, dobrichev (I may be forgetting someone, but I'm not following this topic closely). As it seems they are not interested in Kakuro and are not following this thread, you might contact them directly by mail.

[Mathimagics]

Just printed off my first atk puzzle. Now that's better - a sensible printed version!

[denis_berthier]

I agree that increasing black cell density eventually leads to a diminishing number of possible states, but that doesn't mean the relationship is linear!

We've been cross-posting.
Ok, the relationship is probably not linear. And in any case, it can only be statistical.

[Mathimagics]

Hey denis, I'd be grateful if you could check out atk puzzle H3712 and compare it for difficulty with the Conceptis P103 I gave you.

I need an independent valuation!

[denis_berthier]

Hi Mathemagics,

I've tried H3712.

Short version: harder than P103.

Longer version, based on precise ratings:
P103 : W+ = 8, gW+ = 7
H3712 : W+ = infinity (i.e. not solvable by whips), gW+ = 7
If you look only at the gW+ rating (i.e. if you use g-whips), they seem to be of equal difficulty. But the first can be solved with whips while the second requires g-whips.
As usual, I recall that any such rating is based on a precise set of resolution rules and could be changed if any rule is added.
W+ [resp. gW+] is based on whips [resp. g-whips] and (Naked, Hidden + Super-Hidden) Subsets upto length 4.
In Kakuro, in particular, surface sum rules often allow to split a puzzle into several relatively independent parts. I didn't use such rules here.

In the present comparison also, size is not taken into account: the larger puzzle has a longer resolution path, with more boring eliminations. What my ratings measure is only the hardest step.

I'd say the "small" atk puzzle is much more interesting because, with a more compact design, it has a harder solution.

[Mathimagics]

Excellent!

That was my gut feeling. Trouble is my solver (home grown using classical coding, ie. pretty basic) has far more difficuly with P103, so much that I was convinced I had a bug (or failure to adequately shave my domains).

Thanks, I now know how to go about tracking it down.

You mentioned g-whips .... please don't. Is that another SAT or CSP package?

Every SAT or CSP package I try to install (I'm on Windoze) creates a new set of nightmares for me. MiniSAT, Copris/Scala, and the latest thing I'm trying to decide on is Choco....

Any choice means abandoning what I've done for long enough to learn CSP from the ground up ....

Cheers!