PDA

View Full Version : Kakuro



unmarkedhelicopter
08-10-2007, 03:52 AM
Following Ken Puls's Comments about Kakuro (see Kakuro.com, it's like Sudoku but with sums)
I found it to be quite satisfying (over Sudoku) and as I (like most people) had done a Sudoku Solver I thought I'd do a similar exercise for Kakuro.
Unlike my Sudoku Solver though I was not able to construct a Kakuro Generator.
The Soduko Solver can do puzzels of 6,8,9,10,12,16 and 20 characters, implement 'guessing' and backtracking, it can also do overlapping and 3D Soduko and character removal to get 'minimum solvable sets'.
I've hit a wall however with Kakuro and have posted this with the following aims :
1. That someone find a way to submit a solvable puzzle that THIS can't solve.
2. Someone come up with a better way of entering the puzzles
3. That people use this as an idea for their own project
4. That someone come up with an idea for a generator

The code here was knocked up over a weekend with some tweaks to fix a problem I found, so the code is poor (that's why I locked it) but it works Those who unlock it please forgive some of the kludges used. Though improvement suggestions would be appreciated anyway

For those wishing to implement their own solutions, the puzzle on sheet9 gives some interesting challenges ;)

Kakuro is supposed to have ONLY 1 solution per puzzle which is why I have not implemented guessing on this

I will also post this on JMT and link the two http://www.puremis.net/excel/cgi-bin/yabb/YaBB.pl?num=1186742851

mvidas
08-15-2007, 07:59 AM
Hi UMH,

I like it, though I have to say that you may want to put some kind of version checking into it, as the line "Application.ErrorCheckingOptions.NumberAsText = False" in KClear caused it not to work until I commented it out.

I did find a puzzle it couldnt solve, the bigger one from kakuropuzzle.com today (http://www.kakuropuzzle.com/challenge/13035-22276.gif)

Also, I have to disagree that all puzzles can have only one right answer. I found one the other day that had multiple correct answers.. let me see if i can find it
http://www.kakuropuzzle.com/challenge/12957-24286.gif
The 4 blocks in the top-right of the puzzle (under the 8 and 6) could be
7 4
1 2

or

6 5
2 1

But thats neither here nor there.
I'd love to help make your solver better, however I can't solve some of these manually! much less program the logic for them

I did come up with my own way of entering the puzzles, creating them with VBA. I wrote a bunch of functions to create them, and then just write a sub like this to actually have it created:Sub CreateTough2()
Dim vX, vB: vX = V("X"): vB = V()
BuildKakuroBoard 11, 10
AddKakuroRow 1, vX, vX, V(24), V(9), V(14), V(18), V(32), vX, V(20), V(17)
AddKakuroRow 2, vX, V(10, 26), vB, vB, vB, vB, vB, V(, 8), vB, vB
AddKakuroRow 3, V(, 28), vB, vB, vB, vB, vB, vB, V(, 11), vB, vB
AddKakuroRow 4, V(, 10), vB, vB, V(16), V(, 9), vB, vB, V(17, 4), vB, vB
AddKakuroRow 5, V(, 14), vB, vB, vB, V(21, 30), vB, vB, vB, vB, vB
AddKakuroRow 6, vX, V(, 10), vB, vB, vB, V(, 13), vB, vB, V(29), vX
AddKakuroRow 7, vX, V(24), V(17, 8), vB, vB, V(18, 15), vB, vB, vB, V(13)
AddKakuroRow 8, V(, 22), vB, vB, vB, vB, vB, V(, 9), vB, vB, vB
AddKakuroRow 9, V(, 7), vB, vB, V(, 11), vB, vB, V(6), V(15, 11), vB, vB
AddKakuroRow 10, V(, 9), vB, vB, V(, 29), vB, vB, vB, vB, vB, vB
AddKakuroRow 11, V(, 10), vB, vB, V(, 26), vB, vB, vB, vB, vB, vX
End SubvB being a blank block, vX being a 'dead' block, and v(y,x) being the clues. Not really a great solution for creating them, but makes for easier distribution to a couple other friends who play :)

unmarkedhelicopter
08-16-2007, 03:02 AM
What can I say .... I'm blown away .... Thanks ! (I think ???)
I appreciate the feedback in it's entirety.
1. Version Checking - You are right, will put a check in for that line (but I also use ReverseStr() and Replace() a couple of times also (problems with Excel 97 I believe) I could write dedicated replacement functions for these but I can't seem to work up the enthusiasm for that !)
2a. Not only, could it not solve it, it couldn't even find a single number ! Okay that means I'm gonna have to implement pattern matching (huge code effort :( )
2b. The puzzles at www.kakuropuzzle.com (http://www.kakuropuzzle.com) are quite a bit different aren't they, hmm ! my board maxed out at 35x30 will have to expand to 40x40 to be able to take a crack at the impossipuzzles !!!
3. Multiple solutions : hmm ! I take your point, in a small closed area like this with only a single external reference it is possible to have 2 solutions (in each area like this). I'm not sure if it's worth coding for though as the solver will just show the possibles (will rewrite final write routine to accomodate :) )
4. Sorry, by "generate" I meant create new puzzles without human intervention.
5. I did like your routine CreateTough2() though, I'm a bit unclear on what
V("X") actually does.
6. Would you also care to include your routines for "BuildKakuroBoard" and "AddKakuroRow" (Thanks in advance) though to make it easier to read I would (probably) have written
AddKakuroRow 7, vX, V(24), V(17, 8), vB, vB, V(18, 15), vB, vB, vB, V(13) as
AddKakuroRow 7, D, "24 ", "17 8", "", "", "18 15", "", "", "", "13 " - but that's just a guess without having seen your routines.

Thanks again, if only for pointing out another resource and where my code fails :rotlaugh:

mvidas
08-16-2007, 06:13 AM
It probably would have worked out just the same. My "V" function asks for 2 optional arguments and returns an Array(arg1, arg2) type of thing--nothing fancy

Keep in mind that I had not actually heard of kakuro until monday when I read your thread. I think I remember Ken saying something about it in the sudoku thread but I didnt look into it further then due to time constraints, and forgot about it after. Always go with what you know, my setup wouldn't be great for programming since it involves (ick) merged cells. But if you want to see it I'll attach the module code (so as not to clutter this or take away from your solver). It was more designed for looks than solving :) The way you wrote the AddKakuroRow would be fine, I originally had it with Array() statements throughout the whole thing and decided to shorten it to just a single letter function (since it was only gonna be for my use)

Having it check for version isn't really necessary, unless you're going to lock the project like you did :) I only checked kakuropuzzle.com since I'm not allowed at other kakuro sites at work, though I will say I found it kinda redeeming that your code could not solve some of those.

kakuro is quite fun though :)