We have a bunch of really smart FileMaker developers here at The Support Group who can do some clever stuff with FileMaker. To find out just how clever, Julien, our Development Director, ran a contest for the entire technical staff to see who could build the fastest Sudoku puzzle solver using FileMaker.
I imagine for some of you that sounds like a strange thing for a “database” to do. But FileMaker is more than just a database. It’s a whole application development environment. And while it has a powerful database engine at its core, it also has an incredibly rich and sophisticated scripting language that is fast… blazingly fast, as our FileMaker Sudoku Solver demonstrates.
The winner of the contest was Roland Kippenhan who works out of our San Mateo, CA office. The FileMaker Sudoku Solver he built is very cool, so we want to share it with you.
And did I mention fast? It’s very fast.
We decided to put it to the test. I bought a book of really hard Sudoku puzzles (“wicked hard” as we are fond of saying here in Boston) called Mensa Absolutely Nasty Sudoku Level 4. We took one of the puzzles and gave it to 3 human contestants. I tried it, too. Here are the results in terms of how long it took us to solve it:
- Human #1: 44 minutes
- Human #2: 35 minutes
- Human #3 43 minutes
- Me: 34 minutes
Roland’s FileMaker Sudoku Solver did it in 3 seconds. WOW!
It’s also worth noting that we have been unable to stump it. In other words, we cannot find a Sudoku puzzle that it can’t solve. So we’ll throw that challenge out to all of our readers: If you can find a puzzle that Roland’s FileMaker Sudoku Solver won’t solve, please share it with us. We’d love to hear from you!
For those of you who want to know a little of what’s going on inside the application, check out the scripts. And for those of you who want to know what was going on inside of Roland’s head when he set out to build the fastest Sudoku solver he could, here are some of his comments:
The main objective was speed—both in performance, and development.
I considered a number of approaches, and the one I ended up coding was a combination of how I solve puzzles myself with pen and paper, along with using FileMaker to make guesses for me.
When it goes to solve, it does a simple process of elimination along rows, columns, and squares. It also looks for lone values, and couplets (grouped pairs) to remove other values. If that is not enough, then it guesses.
The way it guesses is it duplicates the current record, takes a guess in an unsolved cell, and then uses the above logic again. It continues to do that until it finds that the last guess was no good. In that case, it throws that record away, and makes a new guess.
I know the current solution could be made faster. Just having a single string with the list of unsolved cells could be used to avoid a lot of useless checks. There are others as well. The niceties that I’ve added into the interface also take a small toll on performance.
I spent a fair amount of time thinking about how to do this making use of relationships, where the relationships would be constraints for various things, like one for rows, one for columns, one for squares with further restraints for if a cell is completed or not. But the more I thought about it, and as appealing as it was, the guesser part became more daunting and I was worried it wouldn’t be as fast as the simple approach.
I’d love to see a good Sudoku puzzle generator. I could easily enough write code to generate a random Sudoku puzzle, but I don’t know what the rules are to ensure that it will only have a unique solution, or that it is solvable only with logic.
Open the solution up. Take a look. Have fun!
Roland Kippenhan
| Download Sample File |
