Solving Sudokus as CSP with Forward Checking

When you think about it, a Sudoku is a perfect example of a Constraint Satisfaction Problem, and so it made good sense that the final programming assignment in the IAIP course I'm taking was to solve a Sudoku as a CSP, using forward checking.

The basic idea is to define the problem as a set of variables (in this case 9*9=81 variables), where each has a finite domain of potential values (by default values 1-9 in this Sudoku example) and then there's a number of constraints connecting the variables. For the Sudoku these constraints ensure that the numbers 1-9 are distinct in every horizontal and vertical line, as well as in the same 3x3 square.

Once the problem is defined as a CSP there's several approaches to solving it. The assignment this time was to implement Forward Checking. The basic idea with forward checking is to make a backtracking depth-first search in the solution space, but every time a variable is assigned, the domains of all the affected variables (due to constraints) will be modified. If a domain becomes totally empty, we backtrack. It all sounds terribly complicated but it's really a straightforward approach, assigning the variables one at a time and whenever something is assigned revise the possible values for the rest of the affected variables.

As usual we were supplied with a nice codebase to extend to (in fact all we had to do was more or less to implement the Forward Checking part), but also as usual the entire codebase was in Java. This time it made the most sense to simply port it to C# and it didn't take much more than an hour to port the main solver class and even refactor a little.

The report can be seen here.
The project files can be found here.