Now I thought it would be more interesting to write a solver than to actually do the puzzles, so I gave it a shot, thinking it would be no harder than writing a sudoku solver. You probably guessed it -- I was wrong. Well, at least it's harder for me. If I had started with an easier example I might be feeling cocky right now, but instead I started with this one... which my solver (so far) has left a bunch of blanks in:
A B C D E F G H I J K L M N +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 0|XXXXX|XXXXX|XXXXX|17\ |15\ |XXXXX|XXXXX| 5\ |17\ |XXXXX| 9\ | 8\ |XXXXX|XXXXX| +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 1|XXXXX|XXXXX| \10| ___ | ___ |XXXXX|15\11| ___ | ___ | \14| 8 | 6 |12\ |XXXXX| +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 2|XXXXX|XXXXX| \15| ___ | ___ |18\14| ___ | ___ | ___ | \ 6| 1 | 2 | 3 |10\ | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 3|XXXXX| 9\ |16\ | \11| ___ | ___ | ___ |XXXXX|XXXXX|XXXXX| 6\ |14\ 4| 1 | 3 | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 4| \10| ___ | ___ |15\ | \ 9| ___ | ___ |27\ |XXXXX|16\29| 5 | 9 | 8 | 7 | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 5| \11| ___ | ___ | ___ | 9\18| ___ | ___ | ___ |10\ 8| 2 | 1 | 5 |15\ | 4\ | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 6|XXXXX|10\17| ___ | ___ | ___ | 6\ | 8\11| ___ | ___ | ___ | 9\ | \ 5| 4 | 1 | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 7| \12| ___ | ___ | \36| ___ | ___ | ___ | ___ | ___ | ___ | 2 |11\ 4| 1 | 3 | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 8| \ 8| ___ | ___ |16\ |15\10| ___ | ___ | ___ |13\ | 6\21| 7 | 9 | 5 |17\ | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 9|XXXXX|16\ |17\18| 9 | 7 | 2 | \18| 8 | 7 | 3 | \13| 2 | 3 | 8 | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 10| \30| 9 | 6 | 7 | 8 |XXXXX|XXXXX| \ 4| 3 | 1 |22\ | \11| 2 | 9 | +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 11| \ 9| 7 | 2 |15\ | 8\ |XXXXX|17\ | 4\ 9| 1 | 2 | 6 | 9\ |XXXXX|XXXXX| +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 12|XXXXX| \24| 9 | 8 | 7 | \12| 9 | 1 | 2 | \ 8| 7 | 1 |XXXXX|XXXXX| +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+ 13|XXXXX|XXXXX| \ 8| 7 | 1 | \11| 8 | 3 |XXXXX| \17| 9 | 8 |XXXXX|XXXXX| +-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+
Basically what my solver does is calculate all possible combinations of cells that can add up to the prescribed totals. This gives an easy start -- if you look in the lower right-hand corner you see that cells 13K and 13L must add up to 17. The only legal way for this to happen is for 13K to be 9 and 13L to be 8. The reverse might be possible except that because of cell 11L, we see that 12L+13L must add up to 9. If 13L were 9, then 12L would have to be zero, which isn't allowed.
That simple strategy didn't get me all that far; I then went to the rather sophisticated (I thought) step of saying, "If all combinations adding up to the prescribed total require that at least one '5' be present, and only one cell could possibly be '5', then that cell must be '5'." This allowed me to decide that 8M=5.
But beyond that, you see there are still a bunch of blanks in the puzzle above. I have an idea for a next step, but I'm not sure that'll be enough. Well, that's enough fun for today; time for sleep.
7 comments:
How did you organize the search?
Also,
This puzzle doesn't seem to be solvable...
D1 is restricted to 8 or 9 through D0.
The 9 branch dead ends with E2=E3=7, verifying D2=9,E1=2,E2=6,E3=7
I1 is restricted to 8 or 9. The 9 branch dead ends with H2=G2=3, leaving I2=9,H1=3,H2=2,G2=3
D3, E3, and G2 constrain F3 and G3 to 1 and 3, respectively.
The four possibilities for F4 through F2 and F3 (6, 7, 8, 9) narrow down to 7, as that's the only value that yields a valid G4 in light of G2 and G3.
F5=8, G5=9, H5=1 come through E5 and F and G columns.
This leaves H6, H7, and H8 to add up to 26 (as per H4), an impossibility.
Have I missed something?
h9 is 8, so h6/h7/h8 sum to 18, not 26.
more later
oh, whoops
OK, about how I organized the search, it was very simple-minded. I have a list of possible values (initially 1-9) on all empty cells. Then given the totals (either across or down), I zap the set of possible values so it includes only those that appear in a combination. So for example if two cells must add up to 4, then at most the list of possibles will contain [1,3]. If going crosswise one of them is part of a two-cell combo that sums to 6, then that cell would be forced to 1. Once that cell is determined to be 1, no other cell in the same set can have that value. Similarly, any combination that doesn't contain 1 is possible. And so on.
Uh, "...combination that doesn't contain 1 is impossible"
Do you intend to work further on this?
Yep. I had an idea on the way home, but I was driving my car, so I didn't write any code.
The idea I had was... maybe after going as far as you can go with the sorta naive approach of combinations, to switch to enumerating the permutations adding up to each sum. So rather than saying only that you need 7,8,9 to do 24 in three squares (wherein the first cell can't be 9 and the second cell can't be 8), I'd say that the values must be (7,9,8) or (8,7,9) or (8,9,7); this might save me some computation (I'm not quite sure if this obviates the "box" technique as mentioned in the wikipedia article on kakuro).
But probably not tonight.
Post a Comment