Sudoku Solver

To run the program:

1. Open a LISP interpreter
2. Load the file sudoku.lisp
3. Call one of the solver functions (smartbfsolver, smartdfsolver, bfsolver, dfsolver) and pass it a 2D array as an argument (two samples are included, sudoku4 and sudoku9)

This was a project in my AI class. The idea was to use LISP to create a Sudoku solver that would include heuristics to make it more efficient. The bfsolver and dfsolver functions use dumb breadth-first and depth-first search algorithms respectively. The "smart" versions of these functions include the heuristics. The two improvements I've implemented are (1) only expanding nodes for allowed numbers (that is if we know there is a 9 column of the current box, we shouldn't try putting a 9 in the box) and (2) expand the node that leaves us with the fewest options (that is try the number that most limits our future choices as a way to prune the state tree). The Sudoku board is represented as a list of lists where each sub-list is a row of the board and a 0 represents an empty square. The program supports any board that is n^2 by n^2 and, of course, larger boards will take longer to solve. Also, if the problem is difficult enough, the "smart" versions may simply give up, but this program appears to work for most Sudoku puzzles classified up to medium difficulty.