This problem appeared as a project in the edX course ColumbiaX: CSMM.101x Artificial Intelligence (AI). In this assignment the focus will be on constraint satisfaction problems (CSP). The AC-3 and backtracking (with MRV heuristic) algorithms will be implemented to solve Sudoku puzzles. The objective of the game is just to fill a 9 x 9 grid with numerical digits so that each column, each row, and each of the nine 3 x 3 sub-grids (also called boxes) contains one of all of the digits 1 through 9.
The following description of the problem is taken from the course:
I. Introduction
Let’s consider the Sudoku puzzle as pictured below. There are 81 variables in total, i.e. the tiles to be filled with digits. Each variable is named by its row and its column, and must be assigned a value from 1 to 9, subject to the constraint that no two cells in the same row, column, or box may contain the same value.
II. AC-3 Algorithm
First, the AC-3 (arc-consistency checking) algorithm will be implemented. This algorithm will propagate the constraints and reduce the domain size of the variables by ensuring all possible (future) assignments consistent. As can be seen, very few of the puzzles can be solved by using this algorithm alone, as expected. The following figure describes the algorithm AC-3 (in the context of map-coloring problem) and also shows the pseudocode for the algorithm that will be used for ensuring the arc-consistency:
III. Backtracking Algorithm
Now, the backtracking algorithm will be implemented using the minimum remaining value (MRV) heuristic. The order of values to be attempted for each variable can be arbitrary. When a variable is assigned, forward checking will be applied to further reduce variables domains.The following figure shows the BT search algorithm to be used and also describes the minimum remaining value (MRV) heuristic to improve the BT search and constraint propagation with forward checking (in the context of map-coloring problem):
Outputs
The following figures and animations show how a few instances of sudoku puzzles were solved using the above algorithms.
Example 1:
This is a simple puzzle that can be solved by running the AC-3 algorithm alone. Here is the output obtained.
Example 2:
The above puzzle is an example that can’t be solved using AC-3 algorithm alone, although the domain of the variables could be reduced. The following shows the output from the AC-3 algorithm which shows that no additional variables could be assigned.
Next BT (Backtracking) search with MRV heuristic and forward checking will be applied to solve the puzzle, starting from the reduced domain set of the variables. The following animation shows the BT algorithm steps (it took 254 total steps).
The following figure shows the partial backtracking tree for the above example puzzle:
The following figure shows the full backtracking tree for the above example puzzle (the tree is huge, zoom in to see it properly):
Example 3:
The next puzzle is a more complex one, that takes total 2075 steps to be solved with BT-search equipped with RMV/FC, preceded by AC-3 constraint propagation.
After AC-3:
After BT:
The partial solutions with partial backtracking trees for this example puzzle are shown below:
Example 4:
BT Search Soluton
Summary
The following shows the histogram and the distribution of the total time taken to solve a single Sudoku puzzle, where there were 400 different such puzzles. As can be seen, almost all of the puzzles were solved very fast, typically within 3 secs.
The below figure shows the distribution of time taken only for the AC-3 algorithm. As expected it consumes very small amount of time.
The next figure shows the distribution of time taken only for the BT search algorithm.
Finally let’s have a look at the joint distribution of the time taken by AC-3 (X) and by BT (Y)
