New Kakuro Generator/Site

For fans of Kakuro

New Kakuro Generator/Site

Postby Authority » Mon Dec 09, 2013 5:46 pm

I've just made live my new Kakuro site http://www.kakuro-online.com. It's got a timed daily puzzle contest and a solver for registered users, but the generator is available for everyone. It can generate puzzles up to 20x20, and it runs entirely in the browser in javascript, so there's no applet or anything to load. The difficulty settings are a little flimsy, but in general a hard puzzle will be more difficult than an easy puzzle. The easies have a tighter grid and simpler logic deductions, while the mediums have a slightly more sparse grid and tougher deductions, and the hards have the most wide open grid while keeping the deductions the same as medium. In general my generator's puzzles are a fair bit easier than an ATK puzzle of the same difficulty. It doesn't use surface sums at all right now, which is the main thing that I could add to make puzzles harder.

The generator used for the daily puzzles can be set to produce much harder puzzles, but they can take a long time to generate, and it's a Java program, so it's not available to the public. I also want to keep the daily puzzles' difficulty reasonable, since I personally don't find a ton of enjoyment in incredibly hard puzzles without obvious deductions. Although maybe that's just me being bad at kakuros. 8-)

Anyway, I'd love to hear some feedback. I'd also love to hear a good algorithm for detecting naked triples! :lol:
Authority
 
Posts: 11
Joined: 09 December 2013

Re: New Kakuro Generator/Site

Postby denis_berthier » Wed Dec 11, 2013 12:49 am

Hi Authority,

Welcome on this forum.

Authority wrote:In general my generator's puzzles are a fair bit easier than an ATK puzzle of the same difficulty.

I've tried a few (6) of your "hard" puzzles. I may have been unlucky with the random generation process, but all of them were not only easier than the atk medium ones, they were terribly easy.

Authority wrote:It doesn't use surface sums at all right now, which is the main thing that I could add to make puzzles harder.

As most of your puzzles have obvious surface sums, it's strange that you don't use them. That'd certainly be an interesting step to add them.
BTW, how does your generation process work? Do you first generate a grid of back cells and then try to find sums fitting them?

Authority wrote:The generator used for the daily puzzles can be set to produce much harder puzzles, but they can take a long time to generate, and it's a Java program, so it's not available to the public. I also want to keep the daily puzzles' difficulty reasonable,

I think you could have a database of already generated puzzles (like atk),with a classification corresponding to the result of generation (and not to a max allowed during the generation process - a max that, most of the time, cannot be effectively reached by the result, for statistical reasons). It'd also be nice to have the puzzles named some way, so that we can refer to them without having to post them.

Authority wrote:I'd also love to hear a good algorithm for detecting naked triples! :lol:

There are lots of sudoku solvers including triplets with available source code; you can easily adapt the code to Kakuro.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: New Kakuro Generator/Site

Postby Authority » Thu Dec 12, 2013 4:17 pm

Thanks for the detailed response, Denis. I really appreciate it.

denis_berthier wrote:I've tried a few (6) of your "hard" puzzles. I may have been unlucky with the random generation process, but all of them were not only easier than the atk medium ones, they were terribly easy.


You weren't unlucky; even I find the hard puzzles readily solvable, and I am not the worlds greatest Kakuro solver. The generator is still very much a WIP, so we'll see if I can't crank up the difficulty a bit.

denis_berthier wrote:BTW, how does your generation process work? Do you first generate a grid of back cells and then try to find sums fitting them?


The first step is to generate the grid. My first instinct for the next step was to put in randomly generated sums and then try solving. That didn't yield very good results so instead I fill the grid with a valid solved state, calculate the sums from that, and try solving. I liked the idea of every solve iteration having at least one solution, so it wouldn't waste its time with totally unsolvable puzzles. The solver is coded so that if a puzzle has multiple solutions it will fail to find any of them.

For each iteration it keeps the solved numbers from the previous iteration and generates new numbers to go around them, until it comes up with a valid grid. This often ends up making the solutions for the puzzles radiate out from a few certain points. I think this process is somewhat akin to what Conceptis uses for their kakuro books, at least, their puzzles and mine have lots of similar attributes. Including the fact their hards and my hards aren't very hard for a seasoned solver.

denis_berthier wrote:I think you could have a database of already generated puzzles (like atk),with a classification corresponding to the result of generation (and not to a max allowed during the generation process - a max that, most of the time, cannot be effectively reached by the result, for statistical reasons). It'd also be nice to have the puzzles named some way, so that we can refer to them without having to post them.

This is a good idea. I do maintain a database of every puzzle generated (until I hit the max table size that my web host allows). It would be easy enough to allow access to an individual puzzle.
Authority
 
Posts: 11
Joined: 09 December 2013

Re: New Kakuro Generator/Site

Postby Mathimagics » Wed May 27, 2015 5:25 pm

Authority wrote: ... to what Conceptis uses for their kakuro books, at least, their puzzles and mine have lots of similar attributes. Including the fact their hards and my hards aren't very hard for a seasoned solver.


That's interesting. I am also trying to develop Kakuro generating software, and am also familiar with Conceptis puzzles.

My current benchmark standard is Conceptis's "Absolutely Nasty Kakuro - Level 4". These take me from 1 to 4 hours to solve. Would you rate them as hard too?

PS: You must have also noticed, as I have, how very little information about puzzle-generation there is available in the public domain. Unlike Sudoku.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: New Kakuro Generator/Site

Postby denis_berthier » Sat May 30, 2015 4:26 am

Mathimagics wrote:My current benchmark standard is Conceptis's "Absolutely Nasty Kakuro - Level 4". These take me from 1 to 4 hours to solve. Would you rate them as hard too?

Hi Mathimagics,
I wanted to try the commercial website you mention, but only a few "easy" or "very easy" puzzles are available unless you register.
Could you post one of those you consider as typical of "Absolutely Nasty Kakuro - Level 4"?

Mathimagics wrote:PS: You must have also noticed, as I have, how very little information about puzzle-generation there is available in the public domain. Unlike Sudoku.

I've noted also.
However, based on the way top-down Sudoku generators work, I imagine all the generators start by choosing grid size, then pattern of black/white cells (often making it nice looking in some sense and/or with some symmetries), then (more or less randomly) fill the white grid, then compute the sums in the black cells, and then delete sums one by one as long as unicity is preserved. (I'm not sure they make systematic checks of minimality.)
Can you say anything about the general workings of yours?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: New Kakuro Generator/Site

Postby Mathimagics » Sun May 31, 2015 9:38 am

I'm sorry if I was unclear, I was referring to a Conceptis Book publication, not an online puzzle. I never do puzzles online, for much the same reason that I don't read e-books. Even more so, since I can't use a pencil and eraser on my PC. 8-)

The books are good value, 128 puzzles at about 20c each ($25).

However I have encoded one example from that book (which I've been using to test my solver), so I can display it here in text form. This is the format used by a free solver that I obtained (from here) .

This example is puzzle #103:


Code: Select all
 24 rows
 14 cols
  0\0   0\0  30\0  45\0  35\0  37\0   6\0  21\0  24\0   0\0  35\0  17\0  42\0  28\0
  0\0  16\42   -     -     -     -     -     -     -    0\29   -     -     -     - 
  0\36   -     -     -     -     -     -     -     -    4\19   -     -     -     - 
  0\35   -     -     -     -     -   30\20   -     -     -     -   35\15   -     - 
  0\28   -     -     -     -     -     -     -   17\26   -     -     -     -     - 
  0\0  17\0  29\39   -     -     -     -     -     -   37\21   -     -     -     - 
  0\19   -     -     -   11\22   -     -     -     -     -   19\9    -     -     - 
  0\32   -     -     -     -     -     -   45\33   -     -     -     -     -     - 
  0\0  27\23   -     -     -     -   16\16   -     -     -     -     -    4\0  11\0
  0\29   -     -     -     -    7\29   -     -     -     -     -   30\3    -     - 
  0\14   -     -   13\0   0\7    -     -     -   15\30   -     -     -     -     - 
  0\20   -     -     -    0\33   -     -     -     -     -     -     -   29\0  30\0
  0\8    -     -     -   17\0  24\7    -     -     -    4\0   0\21   -     -     - 
  0\0   3\0  11\42   -     -     -     -     -     -     -    0\23   -     -     - 
  0\18   -     -     -     -     -   21\7    -     -     -   11\0  45\13   -     - 
  0\4    -     -   35\16   -     -     -     -     -   44\27   -     -     -     - 
  0\0  29\0  41\27   -     -     -     -     -   10\23   -     -     -     -    6\0
  0\39   -     -     -     -     -     -   39\21   -     -     -     -     -     - 
  0\11   -     -     -   32\24   -     -     -     -     -   35\10   -     -     - 
  0\30   -     -     -     -   15\33   -     -     -     -     -     -   22\0  10\0
  0\34   -     -     -     -     -   22\28   -     -     -     -     -     -     - 
  0\3    -     -   17\22   -     -     -     -   15\33   -     -     -     -     - 
  0\28   -     -     -     -    0\36   -     -     -     -     -     -     -     - 
  0\22   -     -     -     -    0\31   -     -     -     -     -     -     -    0\0


Hmm, that's probably not much use, right? Fortunately I have progressed my software to the point where it can produce puzzle images, so I will attach one in the next post.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: New Kakuro Generator/Site

Postby Mathimagics » Sun May 31, 2015 10:06 am

Yes, Conceptis started out as a free website, then introduced charging as they built the site up. They do produce pretty good stuff, I should point out.

denid_berthier wrote:However, based on the way top-down Sudoku generators work, I imagine all the generators start by choosing grid size, then pattern of black/white cells ... then (more or less randomly) fill the white grid, then compute the sums in the black cells, and then delete sums one by one as long as unicity is preserved.


Ahh, if only it were that easy! 8-)

I use just that method for generating Skyscraper puzzles, which was my first venture into puzzle-creating software. I should point out that I'm a programmer/computational scientist (retired) by trade, who happens to get a kick out of doing puzzles.

The problem with Kakuro is the potentially gi-normous solution space involved. It's several orders of magnitude greater than simple Latin Square cases such as Sudoku/Skyscraper. The chances of any random grid producing a well-formed puzzle (ie. one with a unique solution) are infinitesmal for any decent grid size.

For example, just with a small grid of 10x10, I ran the naive-model random generator for several hours without even coming close to unqueness!

So it's obviously necessary to force the grid value to have certain properties, eg. at least 40% of blocks need to be unique sums. While not sufficient in itself, it does at least reduce the solution set, so it's a start. I have produced a puzzle with just 3676 solutions!

I'll report on any further progress!
Last edited by Mathimagics on Sun May 31, 2015 2:28 pm, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: New Kakuro Generator/Site

Postby Mathimagics » Sun May 31, 2015 10:29 am

Here attached you will hopefully find the Conceptis "Absolutely Nasty - Level 4" example I mentioned, in printable image form.
Attachments
Kakuro103_solution.gif
Kakuro103_solution.gif (52.58 KiB) Viewed 1610 times
Kakuro103.jpg
Kakuro103.jpg (166.33 KiB) Viewed 1610 times
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: New Kakuro Generator/Site

Postby denis_berthier » Sun May 31, 2015 3:15 pm

Mathimagics wrote:
denis_berthier wrote:However, based on the way top-down Sudoku generators work, I imagine all the generators start by choosing grid size, then pattern of black/white cells ... then (more or less randomly) fill the white grid, then compute the sums in the black cells, and then delete sums one by one as long as unicity is preserved.

Ahh, if only it were that easy! 8-)
[...]
The problem with Kakuro is the potentially gi-normous solution space involved. It's several orders of magnitude greater than simple Latin Square cases such as Sudoku/Skyscraper. The chances of any random grid producing a well-formed puzzle (ie. one with a unique solution) are infinitesmal for any decent grid size.
For example, just with a small grid of 10x10, I ran the naive-model random generator for several hours without even coming close to unqueness!

You can have very difficult puzzles with a "small" 10x10 grid. Large grid size does not guarantee high difficulty in solving.
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 ?
(To be clear: I've never tried to generate a Kakuro puzzle.)
In Sudoku, we can delete about ⅔ of the complete grid (in the mean). 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)?

Mathimagics wrote:So it's obviously necessary to force the grid value to have certain properties, eg. at least 40% of blocks need to be unique sums.

I've - errr, my solver has - solved hundreds of difficult puzzles from the atksolutions website: the number of "magic" sectors (blocks) is far below 40% in general. So, there must be other conditions as well. They always use patterns with rotational symmetries; I don't know if it changes the generation problem.
Last edited by denis_berthier on Sun May 31, 2015 3:24 pm, edited 1 time in total.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: New Kakuro Generator/Site

Postby denis_berthier » Sun May 31, 2015 3:23 pm

Mathimagics wrote:Here attached you will hopefully find the Conceptis "Absolutely Nasty - Level 4" example I mentioned, in printable image form.

Thanks for this example. The image is easier for me to use.

This puzzle is hard (in my classification, it is in W8); but it is easier than many much smaller atk "hard" ones.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: New Kakuro Generator/Site

Postby Mathimagics » Sun May 31, 2015 4:56 pm

denis_berthier wrote:You can have very difficult puzzles with a "small" 10x10 grid. Large grid size does not guarantee high difficulty in solving.

Agreed, but the larger the grid size the more valid grids there are. A valid grid is simply one whose horizontal and vertical blocks conatin mutually distinct digits. A well-formed grid is one that is valid, and whose block sums (the hints) allow no other solution.

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!

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.

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: New Kakuro Generator/Site

Postby denis_berthier » Mon Jun 01, 2015 6:07 am

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.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Kakuro Solution Space

Postby Mathimagics » Mon Jun 01, 2015 8:55 am

denis_berthier wrote: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 ?


First off, a little revision, on the properties and number of Latin Squares.

If we have a latin square of size N x N, then there are two factors that determine the value of NLS(N), where NLS is the
the number of distinct layouts (completed grids).

The first is NRF, which is the number of reduced forms. An RF is a complete grid in which the values in row 1 and column 1 are in ascending order (also known as normal form, or canonical).

All other layouts are simply some row/col permutation of an RF (ie: can be obtained by performing some sequence of row swaps and column swaps).

This is multiplied by the number of row/col permutations possible, and so NLS(N) = NRF(N) x N! x (N - 1)!

Sadly there is no formula for NRF. We have to enumerate them all and count them.

If we consider an N x N square as a simple Kakuro puzzle (ie. all the cells are "white"), then this has all the properties of a Latin square but of course we can use any values from 1 to 9. This greatly increases the allowable layouts. A reduced form has row 1 and col 1 in ascending order. Note that the Latin square properties tell us that all row/col permutations of a given RF will produce the same row and column sums, in some order.

Some numbers I have obtained are given here. I give values for different ND, being the number of different values available. Thus N = D corresponds to "pure" Latin squares. When N < D, I can't find any refence in the literature to squares of this type, so I'll call them Mexican squares. Like Latin, but spicier.


Table of NRF for various N, D: NP is the permutation factor.

Code: Select all
N     NP   D= 2    3     4      5         6                7              8               9
---------------------------------------------------------------------------------------------
2      2      1    8    34    100         235            476            868           1,464
3     12           1    76   1806      19,748        132,503        642,156       2,460,108
4    144                 4   3584     759,516     46,278,146  1,256,495,512  19,686,788,064
5   2880                       56   1,335,552  3,795,826,632     
6  86400                                9,408    603,507,763


Thus, for a simple 3x3 square, there are 12 x 2,460,108 = 29,521,296 ways to place digits 1-9 so that all rows/cols contain different values.

For a 4x4 square, the number is 144 x 19,686,788,064 = 2,834,897,481,216, which is nearly 3 trillion arrangements.

Next I will investigate the distribution of row,col sums.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: New Kakuro Generator/Site

Postby Mathimagics » Mon Jun 01, 2015 9:12 am

Hey Denis, just spotted your post when I filed mine.

I realise you probably know as much about Latin Squares as me, but I find these forums a useful way of recording information which I would otherwise lose on scraps of paper. Sometimes that fails too - I lost a whole swag of research material (on Gerechte designs, ie non-standard Sudoku/Skyscraper regions) when the Sudoku Programmer's Forum died.

Also I believe in public domain knowledge - privatisation of knowledge is a curse!

I will digest your post henceforth (and forthwith) ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: New Kakuro Generator/Site

Postby Mathimagics » Mon Jun 01, 2015 9:49 am

I take your point on black cell density - that makes sense.

My rather flippant comment was based on my desire to get a tough puzzle generator, so the less black cells the better.

Meanwhile, 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.

Table of P(unique soln) for various N, D

Code: Select all
N   D =  5    6      7      8     9
-----------------------------------
3            44%   20%      9%    4%
4       28%  24%    5%      *     *


* indicates couldn't get any further.

I couldn't run any more because the files of hsum/vsum keys would be prohibitively large, and
they need to be sorted. The trend is fairly evident though. From P(N = D) = 0, you then get maximal uniqueness with 1 free value, then progressively less as the number of possible patterns goes through the roof.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Next

Return to Kakuro