Project 2 Solution

Description

Sudoku is a number placement puzzle. In this puzzle you are given an N x N grid of cells. The grid itself is composed of M x K sub-grids. You can place a number, drawn from 1 to N, in any cell. Initially the grid will have some of its cells partially filled. The objective of the puzzle is to complete the grid so that:

1. Every cell contains a number.

2. No number appears twice in any row, column of the N x N grid or in any row, column of any of the M x K sub-grid.

Figure 1 (a) below is a 12 x 12 Sudoku puzzle made up of 3 x 4 sub-grids and Figure 1 (b) is the solution to this puzzle.

Figure 1(a) Figure 1(b)

Your assignment is to write a program to solve the general Sudoku puzzle using finite domain CSP methods discussed in the class.

The input to your program will be a text file formatted as follows:

1. The first line will have three integers that fix the values for N, M and K in that order.

2. The next N lines describe the board configuration – one per row. An empty cell will be denoted by _.

So N, M, K and the rows in Figure 1(a) will be represented like this:

12, 3, 4

_,11,_,_,_,_,_,_,_,4,_,_

7,_,_,2,6,_,_,3,5,_,11,_

. (Input format)

.

_,_,3_,_,_,_,_,_,_,12,_

You should implement

1. Backtracking + MRV heuristic

2. Backtracking + MRV + Forward Checking

3. Backtracking + MRV + Constraint Propagation

Given an input instance you will generate an output for each of the 3 implementations. Each output will have the solution to the puzzle and the statistics about the solution. The first N lines generated by the output should describe the solved puzzle with the format introduced before. The last line should be the number of consistency checks done to arrive at the solution for each implementation.

You can find random sudoku examples from the web to test your program. Based on your test file analyze the pros and cons of these 3 implementations and write your findings in a report. Make sure that your input file follows the input format.

Notes:

1. Your program should be written in Python3

2. There are numerous sources on the Web for the Sudoku puzzle. You are encouraged to consult them to gain a good understanding of the puzzle.

Submission:

Submit by 11:59 pm on due date via Black Board. Put all the documents in a folder and zip it.

The file name should be LastName_FirstName_HW2.zip.

• Source code with good documentation. Make sure it compiles.

• A trace of the execution for each strategy

• A report with the required statistics generated and any findings you discovered.