FORTH GO

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.





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.