FORTH GO

I’m still going through the list of Maths Challenges. They’re generally getting harder, but I thought I would catch a break on #96, “Devise an algorithm for solving Su Doku puzzles“. You have to solve a set of 50 sudoku puzzles, and I figured I would just hook it up to my Sudokit program and be done.

It almost worked, but there was one puzzle my solver couldn’t handle. My program uses techniques a human solver would use, so there’s nothing too complicated. I found a good list of solving techniques and implemented “X-Wing” and generalizations of it, and that was enough to solve the final puzzle (which was #7 of 50 if anyone cares to try it manually).

The image shows the place where my program first got stuck, with the highlighted cells showing where X-Wing can be applied. It can be seen that within rows 1 and 9, 6 can only appear in the highlighted cells. Since the cells are also confined to two columns, there must be one of the 6’s in each column. And that means we can eliminate 6 from the possible values of the remaining cells of those two columns. In particular a 6 can’t be in the cell at row 7 column 9, so that cell must be a 9. We still don’t know where the 6s go, just a few more places where they can’t go.

Looking at the problem discussion forum, it looks like most solvers reported that a brute force recursive search turned out to be fast enough. I guess you don’t have to recurse too deep before you get a dead-end.

Søren Berg Glasius has created a JDBC Providers project on BerliOS, which is something like SourceForge. We’re working on making it easier to run the providers on different databases. It already supported MySQL, and he’s adding Sybase. The idea is to put all the SQL code in an external properties file. There is still some code/DB dependencies, which I’m not sure how to get rid of, such as a dependence on the rough DB schema.

Living in town with a sporting dog makes me get out to some local hiking trail two to three times a week, especially since Willow has never taken to walking in the neighborhood. We usually go to nearby Duke Forest which has a good variety of trails, some along New Hope Creek, but whatever the trail, I’ve discovered that winter is actually the best time for walking in the woods.

Pests, like ticks and snakes, are less common. The creeks have more water. Underbrush has died back, improving visibility and opening up otherwise overgrown trails. No crowded parking lots or trails, except on New Years Day.

And as demontrated by the ferns in this photo from the Eno Rivier, there is plenty of green around.

For the past few weeks, I’ve been addicted to the math programming problems at mathschallenge.net. You have to answer a math question that usually requires writing a little program to solve, such as “What is the sum of the digits of the number 2^1000?” The problems seek to require less that a minute of CPU time with a moderately efficient algorithm. Many require less that a minute on even a dumb brute force algorithm.

When you solve a problem, you get access to a little forum for discussing that problem where people share algorithms and code samples. That’s useful for seeing the same problem coded in different languages. You can choose how clever you want to be, as illustrated by the following forum exchange:

[Person A] I found the solution by paper-and-pencil analysis. No coding required!

[Person B] I found the solution with a dumb brute-force program. No thinking required!

I’ve been using Java, but C++ seems to be the most popular implementation language, followed by Python and Java.

We should have been suspicious when art director Emil Kang suggested that we let the performance wash over us in his (long-winded, as usual) introduction. Carl Hancock Rux’s Mycenaean started out with lots of interest, but then slowed down terribly for the last half and lost me. I’m sure the slow down was intentional and relating to the subject matter of sleep and dreams, but the actors’ murmurings weren’t intelligible enough to keep my attention.

Mycenaean included several video screens and actors playing various roles or dancing or singing to produce a single conglomerate performance. Part of the video was live from a camera held by one of the actors. The segments that had dialog were very well done with parts requiring precise timing from the actors as they interrupted one another and sometimes spoke over one another.

Carl Hancock Rux had a relatively minor part, playing a Mycenaean soldier appearing in dreams of contemporary characters. I didn’t know what to expect coming in, but he had a very rich voice, and I think some attendees were fans of his music and were disappointed that he didn’t sing more.