Solving Sudoku as a Constraint Satisfaction Problem using Constraint Propagation with Arc-Consistency Checking and then Backtracking with Minimum Remaining Value Heuristic and Forward Checking in Python

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.

im1.png

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:

im2.png

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):

im3.png

Outputs

The following figures and animations show how a few instances of sudoku puzzles were solved using the above algorithms.

Example 1:

 ex1_0.png

This is a simple puzzle that can be solved by running the AC-3 algorithm alone. Here is the  output obtained.

ex1_1.png

Example 2:

 ex_2_0.png

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.

ex_2_1

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).

sol2_456.gif

The following figure shows the partial backtracking tree for the above example puzzle:
ex_2_btt0

The following figure shows the full backtracking tree for the above example puzzle (the tree is huge, zoom in to see it properly):

ex_2_btt

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.

ex_3_0.png

After AC-3:

ex_3_1

After BT:

sol.gif

The partial solutions with partial backtracking trees for this example puzzle are shown below:

board100.gv

fig500

board500.gv

fig1288
board1288.gv
Example 4:

fig000.png

BT Search Soluton

sol.gif

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.

im4.png

im5.png
The below figure shows the distribution of time taken only for the AC-3 algorithm. As expected it consumes very small amount of time.
im6

The next figure shows the distribution of time taken only for the BT search algorithm.
im7.png

Finally let’s have a look at the joint distribution of the time taken by AC-3 (X) and by BT (Y)

im8im9

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s