Sudoku Solver for Mac OS X v0.5
The Toronto Star started publishing Sudoku puzzles, so
Brad decided to solve them programatically.
A few weeks back the Toronto Star
started publishing a daily Sudoku puzzle. Being a puzzle fan, I decided to
try my hand at their very first puzzle, to see whether it would be worth doing
it on a regular basis. I was quickly
hooked.
While it hasn't increased my consumption of newspapers (just on weekends at the cottage, where I have no Internet access), right from the start I was thinking about them algorithmically, and my solutions were completely methodical. I quickly started wondering: could I convert these algorithms to code?
I've also been dabbling with Objective-C coding on Mac OS X. At the same time, I've been fiddling around with Xcode 2.1 to see how one gets it configured to create a "universal binary" for the new Intel version of OS X 10.4. I've been looking for a good starter project to do in Objective-C using Apple's fine Cocoa framework (I do most of my coding these days in Java), and this one fit the bill just nicely.
So this past weekend I spent the days swimming in the lake, and the nights coding up my Sudoku Solver. And I thought I'd share it with my faithful readers (assuming, of course, I have any faithful readers ;) ). If you're running Mac OS X, on either PowerPC or Intel-based Macs, give it a try:
Sudoku_Solver_v0.5.dmg Sudoku Solver v0.5 (freeware!)
It currently uses the following heuristics to try to solve a Sudoku puzzle:
1. It determines the possible values for each free cell,
2. It then marks any cell with only a single possible value with that value, solving the cell,
3. It then tries to detect 2-tuple pairs of cells in each row, column, and "box" (i.e.: pairs of cells that have the same two only possible values), removing each value in the pair from every other cell in the group,
4. It then once again marks any cells with only a single possible value with that value, solving the cell,
5. It then looks for any cell which is the only cell in its row/column/box that could possess a specific value, marking that cell with that value, solving the cell.
6. Loop to 0 until all cells are solved.
Using these heuristics, I've found that all of the newspaper Sudoku puzzles I've collected thus far are typically solvable in two passes, in as little as 2/100ths of a second on my PowerBook G4.
A few notes on the application itself:
- It probably won't run on G3s, as I enabled the Altivec code generation system,
- If you mis-enter a puzzles starting values, or if the program encounters a puzzle it cannot solve, it will try to solve the puzzle indefinitely (it doesn't have any heuristic yet to see that it has reached a steady state prior to a solution),
- The GUI is a bit primitive. I haven't delved into Cocoa GUI programming enough to create my own controls, so currently the controls are a 9 by 9 matrix of NSTextFields with equal width and height.
- The program has one puzzle built-in. But if you want to enter your own puzzle from a newspaper, select Edit -> Clear All Cells, type in the numbers in the right squares, and press the "Calculate" button.
One big note: Sudoku Solver will not solve all possible Sudoku Puzzles. It does quite well on the ones typically published in newspapers, however I have tested it against a few exceedingly hard puzzles generated by the Sudoku puzzle generator for Windows that I have found posted in online Sudoku help forums, and have run into several that Sudoku solver can't solve. I believe I need to generalize the 2-tuple pair detection routine to an n-tuple set detection routine, although I'll probably have to sit down and do a few of these puzzles by hand first to determine what heuristic is best for these situations (ignoring the obvious brute-force approach as completely inelegant).
Here's an interesting fact about Sudoku solver: while I have four primary heuristics, the newspaper puzzles I've tested against (including one "hard" one) are all solvable using only the first heuristic and the fourth heuristic. However, in my testing using only these two heuristics typically requires twice as many passes and roughly 5 times more time to solve each puzzle. Using all the heuristics is quite a bit faster.
Feedback is welcome. At some point I will probably make the source code available to anyone who wants to tinker with this themselves. As I'm fairly new to Cocoa, I imagine there are several things I didn't completely do in "The Cocoa Way" (in particular, as I'm using 81 text fields, I'm note sure if my using 81 outlets in the controller class, and then building arrays out of these outlets is the best way of accessing each field, although it's a fair sight better than hand-coding access to 81 separate entities!). I'm going to continue to tinker with it in my spare time in order to beef up its solving capabilities, and later make its GUI more like the printed puzzles, but have no plans on any sort of release schedule. You get what you pay for :).
While it hasn't increased my consumption of newspapers (just on weekends at the cottage, where I have no Internet access), right from the start I was thinking about them algorithmically, and my solutions were completely methodical. I quickly started wondering: could I convert these algorithms to code?
I've also been dabbling with Objective-C coding on Mac OS X. At the same time, I've been fiddling around with Xcode 2.1 to see how one gets it configured to create a "universal binary" for the new Intel version of OS X 10.4. I've been looking for a good starter project to do in Objective-C using Apple's fine Cocoa framework (I do most of my coding these days in Java), and this one fit the bill just nicely.
So this past weekend I spent the days swimming in the lake, and the nights coding up my Sudoku Solver. And I thought I'd share it with my faithful readers (assuming, of course, I have any faithful readers ;) ). If you're running Mac OS X, on either PowerPC or Intel-based Macs, give it a try:
Sudoku_Solver_v0.5.dmg Sudoku Solver v0.5 (freeware!)
It currently uses the following heuristics to try to solve a Sudoku puzzle:
1. It determines the possible values for each free cell,
2. It then marks any cell with only a single possible value with that value, solving the cell,
3. It then tries to detect 2-tuple pairs of cells in each row, column, and "box" (i.e.: pairs of cells that have the same two only possible values), removing each value in the pair from every other cell in the group,
4. It then once again marks any cells with only a single possible value with that value, solving the cell,
5. It then looks for any cell which is the only cell in its row/column/box that could possess a specific value, marking that cell with that value, solving the cell.
6. Loop to 0 until all cells are solved.
Using these heuristics, I've found that all of the newspaper Sudoku puzzles I've collected thus far are typically solvable in two passes, in as little as 2/100ths of a second on my PowerBook G4.
A few notes on the application itself:
- It probably won't run on G3s, as I enabled the Altivec code generation system,
- If you mis-enter a puzzles starting values, or if the program encounters a puzzle it cannot solve, it will try to solve the puzzle indefinitely (it doesn't have any heuristic yet to see that it has reached a steady state prior to a solution),
- The GUI is a bit primitive. I haven't delved into Cocoa GUI programming enough to create my own controls, so currently the controls are a 9 by 9 matrix of NSTextFields with equal width and height.
- The program has one puzzle built-in. But if you want to enter your own puzzle from a newspaper, select Edit -> Clear All Cells, type in the numbers in the right squares, and press the "Calculate" button.
One big note: Sudoku Solver will not solve all possible Sudoku Puzzles. It does quite well on the ones typically published in newspapers, however I have tested it against a few exceedingly hard puzzles generated by the Sudoku puzzle generator for Windows that I have found posted in online Sudoku help forums, and have run into several that Sudoku solver can't solve. I believe I need to generalize the 2-tuple pair detection routine to an n-tuple set detection routine, although I'll probably have to sit down and do a few of these puzzles by hand first to determine what heuristic is best for these situations (ignoring the obvious brute-force approach as completely inelegant).
Here's an interesting fact about Sudoku solver: while I have four primary heuristics, the newspaper puzzles I've tested against (including one "hard" one) are all solvable using only the first heuristic and the fourth heuristic. However, in my testing using only these two heuristics typically requires twice as many passes and roughly 5 times more time to solve each puzzle. Using all the heuristics is quite a bit faster.
Feedback is welcome. At some point I will probably make the source code available to anyone who wants to tinker with this themselves. As I'm fairly new to Cocoa, I imagine there are several things I didn't completely do in "The Cocoa Way" (in particular, as I'm using 81 text fields, I'm note sure if my using 81 outlets in the controller class, and then building arrays out of these outlets is the best way of accessing each field, although it's a fair sight better than hand-coding access to 81 separate entities!). I'm going to continue to tinker with it in my spare time in order to beef up its solving capabilities, and later make its GUI more like the printed puzzles, but have no plans on any sort of release schedule. You get what you pay for :).
Posted: Tuesday - June 14, 2005 at 02:01 AM
Quick Links
Statistics
Total entries in this blog:
Total entries in this category:
Published On: Aug 30, 2007 08:14 PM
Total entries in this category:
Published On: Aug 30, 2007 08:14 PM