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 ﬁll 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)