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.
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.