Occassionally, people write to me about Kakuro.
(Deleted characters are replaced by a hash (#) mark in square brackets like so [####].)
Thank You
A letter like this makes it all worth while...
From [##### #####] <######@######.###>
To: [#######@#######]
Subject: Thank You AG7Y
Date: Thu, 11 May 2006 19:01:47 -0700
Thank you for making your puzzles available on your website.
I am recovering from cancer and find that my ability to concentrate and
focus has been drastically reduced due to the chemo. In an attempt to
"train" my mind to focus, I decided I would try some kind of math
puzzles. I had never attempted any kind of puzzles before, so I started
looking around the internet. I found your Kakuro puzzles and now I am
hooked.
I really enjoy the challenge of your larger puzzles. It is very
satisfying to finish one of these.
Again, thank you for making these available to the public.
[##### ######]
Can I help with some course work???
I don't like to give some people an unfair advantage over others on a university course so here is my reply. I have included the image mentioned so that you can see what it is on about (around half way down).
From [#####] Wed Jun 7 16:12:27 2006
To: [#######] <######@######.###>
Subject: Re: AG7Y question about kakuro generation
Date: Wed, 7 Jun 2006 16:12:27 +0100
On Tuesday 06 June 2006 11:24, you wrote:
> hello I am a [####] student (so I apologies for my poor english :) )
> doing a placement in Ireland. For that placement I have to create a
> kakuro generator using Constraint programing in java. Is it possible to
> have the source code of your program ? even if a dont know perl at all,
> I'm am very interested of finding new ways of generating kakuro. What
> kind of technique did you use to generate them ?
The first thing you have to do is think about how you solve the Kakuro
problems - the different methods you use - look at the tutorial at...
http://www.grosse.is-a-geek.com/kaktut.html
...and you will have a good idea of the algorithms you will need to write
although at this stage, you'll just want to make some general notes.
Next, you want to think about how you will represent that in a way that the
computer can understand. I chose to have an array with the mask in it (just
0s and 1s) and then another array with the numbers 1-9 in it where an empty
cell is indicated by the mask array. Should you use a linear array or a 2D
array? I found that the number of times when a linear one was a disadvantage
was matched by the number of times that it was an advantage so do what you
want. I chose a linear array (remember to use 0 as the first element).
In addition, there are two associative arrays (in Perl, they are called
'hashes') where the index is the cell number and the value is the sum. One
set is for across sums (the index is the cell number for where the sum
starts) and the value is the sum itself. The other is for down sums. If you
haven't got access to associative arrays, you can use two arrays together but
a hash is a lot easier.
After this, you can test it out by putting a grid from an existing puzzle into
the array, its sums into the hashes and test out your solver (once you've
written it - remember that you can't write it until you know how you are
going to tell it what you need to solve).
For http://www.grosse.is-a-geek.com/robopics/kakbits/kak3x3.png
you will have two arrays that look like:
0 1 1 1 1 1 1 1 0;
0 123456789 123456789 123456789 123456789 123456789 123456789 123456789 0;
and two hashes that look like (across first):
1 -> 17, 3 -> 17, 6 -> 8;
1 -> 23, 2 -> 16, 3 -> 3;
for the 3x3 array (remember that the array index starts at 0 and not 1).
Your solver should chuck out 0 8 9 1 9 7 2 6 0 as the result.
Now that you have a solver that works, next, you need to be able to fill the
grid in order to generate your own puzzles. You could just fill in any set of
numbers but this type of brute force attack doesn't work very well (see the
trivia page at...
http://www.grosse.is-a-geek.com/kaktriv.html#bf
... for a more detailed description of the problem and some solutions). You
need to use unique number sets, elimination sets and then, failing that, any
old number - this bit is NP complete.
You'll need to write a program that produces the complete set of sets (save it
in a hash so that your keys look like '23s3' and your values look like
'689'), then, from that, the unique sets and the elimination sets (which are
easy to derive from the complete set simlpy because you used a hash). You
will also need to be able to calculate the elimination sum values that leave
unique results but without using unique numbers (so, say a combination of two
numbers (say a 23 in 3 and a 13 in 4) which leaves a unique number at their
intersection but they themselves don't have to be unique (13 in 4 has 3
outcomes but where it intersects with a 23 in 3, the only value that can go
there is a 6)).
Now, your program should be able to generate Kakuros on grids that already
exist.
> And how do you create
> the empty grid ?
Now for another NP-complete bit. You need to be able to produce a mask. The
rules are:
1 no longer than 9 cells;
2 no shorter than 2 cells;
3 must be contiguous;
4 must go to all 4 sides; and,
5 if you want it to look good, it must be rotationally symmertrical.
On this last point, it is amazing how ugly a non-symmetrical Kakuro is and yet
rotational symmetry is exceptionally easy to produce using a program. If you
see one that is not rotationally symmetrical, then probably, the person who
wrote the generator hasn't managed to figure out how to produce masks using a
computer program.
This is a lot simpler to say than it is in practice to write such a program.
You need to have a subroutine that puts at least some cells in at the edges
(4) (if you are making it rotationally symmetrical (5), you only need to do
two edges as the others will be looked after by the program). You will also
need to join them up whilst keeping to the rules (1 and 2). Once you have an
array, you can check it for contiguity (3). If you find that, say, rule 1 has
been violated, you can have a routine that checks to see if it can break that
violation up somehow without violating rule 2 (if you design it so that rule
2 is never broken, you can forget about checking for it). You can check rule
3 using a standard flood fill.
Next, you need some sort of output so either produce a graphic (say, a png
file) or write some PostScript (that is nicer and being a stack-based
langauge (like reverse Polish notation), it lends itself to output from
programs).
So, now that you have all of the bits, you can get them to work together.
1 Choose a mask;
2 fill it;
3 solve it;
4 solved? if 'no' and less than fifth time around, go to 2, else go to 1;
5 print it out.
By using a logic-based solver, you are guaranteeing that there is one solution
to the Kakuro. There are many multiple-outcome puzzles but we want a unique
one.
You will find that your mask generator will produce masks that are easy to
fill (take only a few goes with the fill routine) and some masks that are
difficult(/impossible???) to fill. You can tune your filler so that it makes
them easier to fill therefore using less processor time.
BTW, my puzzles are done on a 600MHz PC using an interpretted langauge.
> hoping not to have bothered you to much,
> thank you very much,
>
> [########]
--
Regards,
Paul Grosse
Home Pages
http://www.grosse.is-a-geek.com/
Project Pitcher Plant
http://www.fresh.files2.serveftp.net/
Water Rockets, Mah Jong, SIRDS, Make your own UFO...
http://ourworld.compuserve.com/homepages/pagrosse/
==============================================================
Je me demande quel goût il aurait dans une sauce au vin rouge.
(I wonder what it would taste like in a red wine sauce.)
==============================================================
Copyright (c) 2006 Paul Grosse. All rights reserved.
