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.
Now that you’re done with them try Nurikabe
http://www.puzzle.jp/letsplay/nurikaberule-e.html
There’s an applet version that only checks your online solution.