# Sudoku

This project aims to solve Sudoku puzzles . This is a console-based Linux program, written in C language, that solves Sudoku puzzles (aka Sudoku, Number Place, etc., see figure 1) using deductive logic. It will only resort to trial-and-error and backtracking approaches upon exhausting its deductive moves. Puzzles must be of the standard 9 x  9 variety using the (ASCII) characters 1 through 9 for the puzzle symbols. Puzzles should be submitted as 81 character strings which, when read left-to-right will fill a 9 x 9 Sudoku grid from left-to-right and top-to-bottom. In the puzzle specification, the characters 1 - 9 represent the puzzle "givens" or clues. Any other non-blank character represents an unsolved cell.

The puzzle solving algorithm is "home grown." I did not borrow any of the usual techniques from the literature, e.g. Donald Knuth’s "Dancing Links." Instead I "rolled my own" from scratch. As such, its performance can only be blamed on yours truly. Still, I feel it is quite fast. On a 333 MHz Pentium II Linux box it solves typical medium force puzzles in approximately 1100 microseconds or about 900 puzzles per second, give or take. On an Athlon 64 4000+ (2.4 GHz San Diego core) it solves about 7,100 puzzles per sec.

Description of Algorithm

The puzzle algorithm initially assumes every unsolved cell can assume every possible value. It then uses the placement of the givens to refine the choices available to each cell. This is the markup phase. After markup completes, the algorithm then looks for singleton cells with values that, due to constraints imposed by the row, column, or 3 x 3 box, may only assume one possible value. Once these cells are assigned values, the algorithm returns to the markup phase to apply these changes to the remaining candidate solutions. The markup/singleton phases alternate until either no more changes occur, or the puzzle is solved. I call the markup/singleton elimination loop the "Simple Solver" because in a majority of cases it solves the puzzle.

If the simple solver portion of the algorithm doesn't produce a solution, then more advanced deductive rules are applied. We have implemented two additional rules as part of the deductive puzzle solver. The first is "naked/hidden" subset elimination wherein a row/column/box is scanned for X number of cells with X number of matching candidate solutions. If such subsets are found in the row, column, or box, then the candidates values from the subset may be eliminated from all other unsolved cells within the row, column, or box, respectively.

The second advanced deductive rule scans boxes looking for candidate values that exclusively align themselves along rows or columns within the boxes, aka chutes. If candidate values are found aligning within a set of N chutes aligned within N boxes, then those candidates may be eliminated from aligned chutes in boxes outside of the set of N boxes.

Note that each of the advanced deductive rules calls all preceding rules, in order, if that advanced rule has effected a change in puzzle markup.

Finally, if no solution is found after iteratively applying all deductive rules, then we begin trial-and-error using recursion for backtracking. A working copy is created from our puzzle, and using this copy the first cell with the smallest number of candidate solutions is chosen. One of the solutions values is assigned to that cell, and the solver algorithm is called using this working copy as its starting point. Eventually, either a solution, or an impasse is reached.

If we reach an impasse, the recursion unwinds and the next trial solution is attempted. If a solution is found (at any point) the values for the solution are added to a list. Again, so long as we are examining all possibilities, the recursion unwinds so that the next trial may be attempted. It is in this manner that we enumerate puzzles with multiple solutions.

Note that it is certainly possible to add to the list of applied deductive rules. The techniques known as "X-Wing" and "Swordfish" come to mind. On the other hand, adding these additional rules will, in all likelihood, slow the solver down by adding to the computational burden while producing very few results.

References

http://www.techfinesse.com/game/sudoku_solver.php

#### Popular Videos

How to improve your Interview, Salary Negotiation, Communication & Presentation Skills.

Got a tip or Question?
Let us know