– 2010-03-21

A B C D E F +-----+-----+-----+-----+-----+-----+... 0|XXXXX|XXXXX|XXXXX|17\ |15\ |XXXXX| +-----+-----+-----+-----+-----+-----+ 1|XXXXX|XXXXX| \10| ___ | ___ |XXXXX| +-----+-----+-----+-----+-----+-----+ 2|XXXXX|XXXXX| \15| ___ | ___ |18\... +-----+-----+-----+-----+-----+-----+-----+ ... 3|XXXXX| 9\ |16\ | \11| ___ | ___ | ___ | ... +-----+-----+-----+-----+-----+-----+-----+ | ... | ... | ... |The earlier version did this:

- For each blank cell, create a list of possible values. This is initially [1,2,3,4,5,6,7,8,9].
- Given the number of cells that must add up to a given total (e.g., 1D+1E=10 because of 1C
across), figure out all possible combinations of values (e.g., 1+9, 2+8, 3+7, 4+6; can't do 5+5 because that would repeat). Remove from the cells any possible value that isn't in this list of combinations (so that 1D and 1E would have at most [1,2,3,4,6,7,8,9]).
Do this for all totals. (In the above example, 1D+2D=17 because of 0D, hence 1D and 2D can be at most [8,9]. Similarly, 1E can be at most [1,2,8,9]. More on this below.)

- If the number of possible values becomes 1 for any cell, then that cell's value is
**decided**. No other cell that's part of the same total (whether an*across*total or a*down*total) can have that value, so eliminate that value from the list-of-possibles for those cells. This may cause another cell's list-of-possibles to have only one value, so this other cell is now decided, and so on. Repeat until no more cells are getting decided. - Another way a call's value can be decided is this: Suppose that all combinations require a certain value (if you have to produce 22 in 3 cells, for example, this can be 9+8+5 or 9+7+6; in any case you need a 9), and suppose only one of your cells could possibly have that value (because of other decided cells/combinations), then that cell must have that value, so it's also
**decided**. Repeat the loop of step#3 until cells stop getting decided. - For all totals, eliminate any combination that's impossible by virtue of step #2 (for example, the combinations possible for 1C are now reduced to 1+9 and 2+8, since 3+7 and 4+6 require values that 1D cannot have)
- Repeat #2-#5 until they don't modify anything in the puzzle

- Handle 2x2 boxes with a tail on them. (The "box technique" is described concisely in the Wikipedia article.) In the above example, 1C says 1D+1E=10, and 2C says 2D+2E=15. Hence 1D+2D+1E+2E=25. Similarly 0D and 0E dictate that 1D+2D+1E+2E+3E=17+15=32; combining we see that 3E=7. This is another way a cell's value can be decided. Repeat the loop of step#3 above until no more cells are decided. This filled in a dozen cells, leaving 29 undecided.
- Make steps #2,#5 more effective by using ordered lists of numbers rather than
unordered lists. In the example of step#2, we determined that 1E has possible values
[1,2,8,9]; this is because 1C's list of possible combinations was reduced to 1+9 or 2+8;
that code didn't take cell ordering into account. Yes, I know it was dumb, but I code
the easy cases first! If we keep track of permutations (ordered lists) of possible cell
values rather than merely combinations, the program will know that 1E can't be 8 or 9;
it can only be 1 or 2, since 1D can be 9 or 8. With this logic added, the program
solves all kakuro puzzles I tried, including today's from the Examiner.
It seems like we have a sort of belt-and-suspenders thing going here; the "box" logic described in the previous bullet might overlap with what step#4 does, and the step of using permutations rather than combinations might have been adequate by itself. But I'm not sure and I'm not motivitated to work more on it now.

Why not just start with the permutations in the first place? Well, if you have 9 cells (45 in nine), then how many permutations is that? Right, 9!=362880. Well, that's possible on most well-equipped modern computers, but it seemed rather much to me.

## 3 comments:

:) Congratulations!

Ah, but there are some harder ones it can't do. I tried http://www.menneske.no/kakuro/eng/random.html?diff=100 and got puzzle#345943 which the solver absolutely chokes on.

This apparently will show you that exact puzzle:

http://www.menneske.no/kakuro/eng/utskrift.html?number=345943

Post a Comment