Sudokit Evolving

Sudokit Screenshot

I’ve added some new solving techniques, a small puzzle database, and a rating system (not shown). I’ve also been doing some research, and discovered several other techniques I need to implement, though they are too esoteric to show up in the puzzles you would find in a newspaper. There is only one truly new technique since my last update: Owning Segment. The other new techniques are special-cases of existing ones. Owning Segment finds a 3-cell segment that must own a particular value and then removes that value from competing cells.

I cleaned up the solving code by making the solvers sort of pluggable, though I broke the step-and-highlight mode. I’d like to work on the display if I can get Swing to do what I want (component sizing seems to be tricky).

Sudoku Kit

I’ve started putting together a little app for solving Sudoku puzzles. Sudoku is the logic puzzle game that is supposedly sweeping Japan (though the two people from Japan that I’ve asked had never heard of Sudoku) and is now common is US and UK newspapers. I’m not sure what the appeal is, but some people are really into it. After solving a few myself, it seems that one hook is the aha sensation of discovering a new technique for filling in the puzzle, but how long can that go on?

The goal of the app, “Sudokit”, is to explore different puzzle-solving techniques that a human solver might use. Sudoku puzzles come with difficulty ratings, and, presumably, more difficult puzzles require more advanced techniques. The last resort technique is trial-and-error.

Sudoku Step

In the screenshot shown, the app is in “step” mode, highlighting each cell before it simplifies it, and the yellow cell is about to be converted to a 3 since that’s the only cell in its row that allows a 3. Large black numbers show known cell values, and small gray numbers show possible values for that cell. (I know, it looks ugly now.) The app knows three solving techniques so far.

Find By Value
For a given value, look through each group (a row, column, or 3×3 block) that doesn’t already contain the value and see if there is only one cell that can contain it.
Find By Cell
For a given cell, see if there is only one value that are not already in the combined 3 groups that contain that cell.
Find By Subsets
For each group, look for subsets of N cells whose members are among the same N values. If found, then those values can be eliminated from other cells in the group. For instance, consider the first column of the shown puzzle. Two cells can contain either a 4 or a 6. That’s 2 cells with members among 2 values. So 4 and 6 must each be in one of those cells, and so cannot be in other cells in that column. As a consequence, the cell allowing 4, 6 and 9 is now known to be 9.

Find By Value and Find By Cell are probably common techniques for human solvers since they are very local: you don’t have to keep information about any cells except the one you’re looking at. Find By Subsets is tougher: you need to keep information about an entire group at a time, but not the entire puzzle, so it’s still possible to do it in your head.

I don’t have an automatic source of puzzles, so I hand-entered a few from WebSudoku, with difficulty levels Easy, Medium, Hard, and Evil. Interestingly, the Easy, Medium, and Hard puzzles were solvable by using the Find By Value method only. I guess I need to find a dumber variant if I want to differentiate among those puzzle difficulties. The Evil puzzles did require Find By Subsets to solve.

I also tried a couple puzzles from a book. There, Find By Value was enough to solve the Introductory and Medium puzzles, but not the Difficult ones. And not even adding in Find By Cell and Find By Subset were enough to solve the Difficult puzzles from the book. I need to try more puzzles from more sources before I can compare difficultly levels meaningfully, but it looks like the difficulty ratings are not universal.

And I need to find another solving technique for those Difficult puzzles — I’m trying to avoid adding trial-and-error.

Timestamp vs. Date on compareTo

I made another update to the JSPWiki JDBC Providers after a user was getting errors mixing the JDBC page provider with a different, non-JDBC attachment provider. The weird thing is that I have the same mixing in the wikis I maintain without any of those errors. Something must be different, but the error makes perfect sense, and so I fixed it.

Part of the page provider API includes a page info class with a date field of type java.util.Date. Getting my data from a SQL database, I was working with java.sql.Timestamp values, and since java.sql.Timestamp is derived from java.util.Date, it seemed to work OK just handing my java.sql.Timestamp value to the page info class. The problem occurs when the engine sorts pages by date, invoking compareTo() on the date values from two page info instances.

java.sql.Timestamp.compareTo() throws an exception if the argument is a java.util.Date (or anything other than a java.sql.Timestamp). It sounds reasonable since java.sql.Timestamp has more precision than a normal java.util.Date (nanoseconds vs. milliseconds), but is it really worth the hassle? I’d rather see the compare succeed by assuming 0 values for the missing precision.

The lesson may be to not rely on foreign compareTo() implementations. In this case, millisecond comparisons provide more than enough precision, so just write a compareTo() method for the page info class that converts the dates to milliseconds and returns the comparison of those values.

JDBC Providers Updated

I actually got some feedback from a couple of users of my JDBC Providers contribution to JSPWiki, and I’ve updated the page provider accordingly.

There is some question about the overall design, which I adopted from an earlier database page provider. The page provider keeps two tables. VERSIONS has every version of every page, and PAGES has only the most recent version of every page. PAGES is unnecessary and basically serves as a cache for VERSIONS, and I don’t know how much that helps. Further, if one does find it valuable to keep a separate PAGES table, is it worthwhile to keep all versions in VERSIONS?

It would be possible to store all-but-the-latest version in VERSIONS, but the redunancy has some advantages. It means you only have to look in one table to get the page history. And it makes updating a page a little simpler. Without redundancy, it would be a copy from PAGES to VERSIONS and an update of PAGES. With redundancy, its an insert in VERSIONS and an update of PAGES.

Rather than worry about table layouts, I think the next step is to move all the SQL statements into the properties file so they could be customized for other databases. Eventhough the code is generic JDBC, some of the SQL is not universal and it’s only been tested with MySQL (though one user is using MS SQL Server).

JSPWiki Migration Page Provider

I’ve contributed a migration page provider to JSPWiki. The engine supports a variety of page providers that handle the storage and retrieval of page contents from whatever store you want to use. This provider is really just a proxy for some real provider with the key feature that if the real provider is empty (no pages), the migration provider will populate the real provider with content from yet another provider.

The idea was pulled out of the original JDBC page provider which has a similar feature where it will populate itself from another provider. I made it into a separate provider so I can go the other way if necessary. That is, if my JDBC provider proves to be the source of my local wiki crashes, I can migrate the content to a standard page provider.

There is one main shortcoming: the modification dates get lost due to the design of the page provider API (adding a new page to a provider always gives it the current date).

JDBC Providers for JSPWiki 2.2.8

When I first encountered the creatively named JSPWiki two years ago, I thought it strange that the server relies on the file system for storing its content. JSPWiki is very extensible and I found a simple database page provider plug-in and used it with some modifications to bring it up to the then-current version of JSPWiki.

Later I did a major overhaul of the code and forked it into a generic JDBC Provider. A few folks have contributed comments, but I don’t get the sense of a big demand for SQL-based page stores for JSPWiki.

I’ve just updated the code for the now-current JSPWiki 2.2.8 and provided a jar file for easier installation. I’m hoping it will improve the stability of my local wiki which hangs every few days using the original database provider plug-in.