Solving Puzzles

My sudoku solving agent is setup as a constraint satisfaction problem where each cell on a sudoku grid are the variables and the variables’ domains are the integers 1-9 inclusive. Each variable is constrained by a set of three alldiff constraints: row alldiff, column alldiff, and 3x3 box alldiff. This problem is pretty well defined in the book we used in this class (Artificial Intelligence: A Modern Approach Fourth Edition by Russell Norvig) as an example of something, in its simplest case, that can be solved by reducing all of the variables’ domains down to one value. However, in the more complex cases, some of the variables’ domains have limits to how far their domains can be reduced by domain propagation.

The first step in my process is to generate a list of constraints by expanding the alldiff constraints into binary constraints. Take a variable X, get the all of the cells in its three units, and for each cell Y in its units, create a constraint in the form X != Y as well as the reverse Y != X. After this process, I get 1944 binary constraints added to a queue.

Next, we need to propagate the initial constraints. Sudoku puzzles are created with a small fraction of the cells filled in with a starting number in order to get the ball rolling when solving them. Each puzzle has different numbers filled in at different places which is what makes solving them a unique challenge for every puzzle. When my Sudoku class is initialized, a list of these starting numbers and their positions is passed to the constructor. The domains of the variables that have an initial number is set to contain only that number, but the value of the variable remains set to None until after constraint propagation.

To propagate the constraints, we run AC3 which ensures arc-consistency for all variables. Arc-consistency is a fancy way of saying that all of the binary constraints for the variables in the problem are satisfied. In this case it means that there isn’t a variable Y whose domain contains a number that variable X must be set to. For example, if X has a domain of only the number 5 and Y is a member of X’s binary constraints, then Y must not have 5 in its domain. Otherwise, the puzzle is invalid and we stop solving.

Sometimes arc-consistency is enough. In the simplest cases, ensuring arc-consistency for all variables reduces all domains down to one valid number. In that case, we can just go through the variables, grab the only value in their domains, and set their values to that number. After this process, if there are no variables with their value set to None, we can return the solved puzzle and print it in all of its glory for all to see. Unfortunately, this is actually a pretty rare case so we have to add another step to our solver that will allow it to solve any valid puzzle passed to it.

To solve more complicated puzzles where domains of some variables are reduced, but not down to one value, we need to implement a recursive backtracking search. Backtracking works as follows: First we pick an unassigned variable using some kind of heuristic, for every value in the domain of that variable (ordered by some heuristic), ensure the value is a valid assignment and call the backtrack method again. If for some reason the value is not a valid assignment or the consecutive calls to backtrack return that the current value did not work further down the line, we can try the next value in the variable’s domain and call backtrack again.

To select variables, I used the most constrained variable heuristic. This heuristic picks the variable with the smallest domain under the assumption that that variable is the closest to having its domain reduced to nothing and failing, making the backtracking search more expensive if that variable were found later rather than sooner.

When ordering the values in a variable’s domain, I used a heuristic that orders the values by the number of constraints they are involved in. The values that are involved in the least amount of constraints are put at the beginning of the domain while the values that are involved in the most amount of constraints are put at the back of the domain.

A video of a puzzle being solved by only constraint propagation is shown below. The first display is the length of variables’ domains as they are being reduced while the second display is the solution.

A video of a puzzle being solved using backtracking is shown below. The first display is the length of the variables’ domains as they are being reduced, the second display is backtracking in action, and the third display is the solved puzzle.

Generating Puzzles

Another interesting concept is generating solvable sudoku puzzles. My approach is a randomized approach that generates solvable puzzles, but doesn’t take into account some important aspects of what makes a good sudoku puzzle that is enjoyable to solve by hand. I found a Stack Exchange post that goes into detail about this that I encourage you to read. It can be found at the following link: https://gamedev.stackexchange.com/a/76170

For my approach, I start by appending every variable to an array of unassigned variables and then I pick one at random. I then pick a value to assign the variable to at random and allow the solving agent to generate a solution.

With a solution in hand, I start unassigning variables at random in a modified backtracking algorithm. If a particular unassignment does not work, we can backtrack it and try another variable. After unassigning, I check if the new puzzle has a valid and unique solution and backtrack if it does not. This process goes on until we get down to 20 variables that are still assigned.

Below is a video of the puzzle generator in action.

Conclusion

I had a lot of fun putting this project together. While not the most difficult problem in artificial intelligence, it gave me a better understanding of constraint satisfaction problems. I chose this project because it was a programming project that was quite a bit different from the path-finding projects that our class labs covered. I think I now have a better understanding of how to solve more artificial intelligence problems in practice and I appreciated the opportunity to expand my new knowledge beyond theory.

The code for this project can be found at the following link: https://github.com/WillHensel/sudoku-solver