MakingSudokuCommitSeppuku

Eric McCann
December 10, 2010

Overview

Sudoku (数独) is a logic-based, combinatorial number-placement puzzle. Seppuku (切腹, "stomach-cutting") is a form of Japanese ritual suicide by disembowelment. (definitions from Wikipedia - http://en.wikipedia.org/wiki/{Sudoku, Seppuku})

"Making Sudoku Commit Seppuku" was intended to be a fast "Sudoku disemboweler", but instead, it simulates the decision process a human would use to solve a Sudoku puzzle.

Screenshot

Concepts Demonstrated

This project uses A* search to decide which number to insert next, and where to put it
The admissible heuristic I used is the number of empty squares (any cell without large black or medium-sized red number in the center is empty). It's admissible, because it's simply the number of empty cells, making it both intuitive and effective.

Innovations

"Making Sudoku Commit Seppuku" models how a human player would solve the puzzle. When it completes the puzzle, that final state can be traced all the way back to the starting state, and the actions taken from the start state to the end state are the same ones that a human player would probably take (or at least I would!)
The visual representation of the puzzle and the possible values for each cell is intuitive, fast, and sufficiently separated from the search logic to allow the searching to occur without throwing around instances of bulky Microsoft GUI class instances.
The A* visual representation, showing the distribution of states in the priority queue, a sliding progress bar that shows where in the queue states are being dequeued from, and showing how close the last state that was dequeued is to the goal.
The structures used to represent the important dimensions of the Sudoku puzzle (rows, columns, and 3x3 sectors) are all "memoized" (OPL WORD!), making all of the bulky expensive operations notably less-so.
Path cost function:
- The path cost function is unlike any I've seen used... It's the difference in the number of possible values (green squares in the screen-shot) between a child and its parent. To encourage adventure and thoroughness, I add a random between -1 and 1, because the "visited" list takes value in to account.
As the number of empty slots decreases, the puzzle's branching factor decreases drastically. On an empty puzzle (worst case for this program), there's so much work being done that only 5 states are expanded per second, resulting in 44,000 states remaining in the queue after 60 seconds. After the puzzle is approximately 3/4 filled in, the program can fly through states at 150 states/second. This is nontrivial, because a state expansion entails:
- Instantiating the successor state copying all of the relevant list items into the umpteen different data structures in the successor.
- Applying the "action" in all of those data structures.
- Computing all of the possible values for every empty cell in the successor's grid (NOR test on 3 9-element lists for each one of the 81 cells)
- Estimating that new state's value in terms of the cost to get to it from the current state, and its distance to the goal.
- Putting it on the priority queue.
Checking to see if a successor had already been visited would eventually bring the search to a crawl (after more than approximately 30,000 states had been visited) when I was simply accumulating the visited states in a 1-dimensional list, so I replaced it with a 120x9x9x9x9x9x9 array of booleans and now it's O(1)... and that's pretty sweet.

Technology Used

Nearly a gallon of 'Monster' Energy Drink... Programs don't speed-hack themselves!
Lots of C# (Windows Presentation Foundation, .NET 4)

General Operation of Search Functionality and UI

Evaluation of Results

It may not quickly spit out a solution, but when/if it finds a solution, it's more than a "valid 9x9 number grid", it's a solution arrived at after following a series of steps, those being the ordered steps a human would probably take to arrive at the solution.
It finishes simple puzzles in between <1 and 5 seconds (depending on random tie breaks), and harder ones that it has actually finished, took 5-10 minutes.

Additional Remarks

Much like humans, this Sudoku solving-process emulator has motivation issues... and by that I mean, much like a human, it will give up on puzzles that are nearly impossible (using up 8 GB of memory would make me quit too).