Morton Fox (mortonfox) wrote,
Morton Fox
mortonfox

Cuckoo for Kakuro

lilbear-4

I noticed that a new geocache, less than 5 miles from home, had appeared in the listings. So this evening, I went for Little Bear's Episode #1. It's in a wooded area owned by the water utility (according to the posted sign anyway) and accessible from a dead-end road in the adjacent residential area. Very simple, even if the trails were muddy.

After that, I went to find a benchmark near the River Vale library but was unsuccessful. I suspect it was turfed over the last time the town redid the ballfield and I'll leave it for someone else to dig out. Then I went to KFC in Hillsdale to use another of their coupons that I get periodically. Service at this particular KFC is still pretty good, although the manager herself handled my order so I don't know how it is at other times. I noticed that there was an open wi-fi network, although I think it is from next door or further. The signal was weak enough that I had to put the network adapter by the window (one advantage to using an external adapter) in order to connect to the network.

I hadn't done any Kakuro puzzles prior to seeing this puzzle cache. There are some Kakuro solvers on the web, but I wrote my own anyway to see how it goes. I used a generate, test, and backtrack algorithm similar to what I used in solvers for Sudoku and a few other puzzles. Unfortunately, the Perl script is specific to this puzzle because I hardcoded the constraints, but I could always rework that in the next version.

Later, I took a look at some of the Kakuro solvers out there, like this and this. What's really unusual is some programmers go to great lengths to avoid backtracking and consider that approach to not be elegant. Why? Kakuro is NP-complete, so it is possible for some Kakuro puzzles to not be solvable by deduction alone. Once we admit to that possibility, we might as well forget about deduction and just implement backtracking, using the constraints of the puzzle to prune the search tree as much as possible. Typical run times for these solvers are under a second anyway, so it isn't necessary to make the solver any smarter than it needs to be.
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 1 comment