Assignment 2: The Sudoku Puzzle
Sudoku is a logic-based placement puzzle. The aim of the puzzle is to enter a numerical digit from 1 to N in each cell of N × N grid made up of sub-grids (called “regions”), starting with various digits in some cells (the “givens”). Each row, column, and region must contain only one instance of each numeral. Sudoku initially caught on in Japan in 1986 and gained international popularity in 2005. A number of variants of the Sudoku puzzle have been published. These variants differ in the size and configuration of the board, and the constraints enforced on the placement of numbers. To read more about the game, you can go to http://en.wikipedia.org/wiki/Sudoku . To try out the game, you can go to http://www.sudoku.com .
Solving Sudoku puzzles is a good pastime and is recommended by some teachers as an exercise in logical reasoning. However, completing a puzzle requires a lot of patience, logical ability and time! You, as experts of finite domain constraint programming, will write a program to solve a general Sudoku puzzle. You will write a series of increasingly efficient approaches to solve a Sudoku puzzle.
Here is a formal description of the popular Sudoku puzzle. You are given a square grid containing 9x9 cells. The grid is divided into 3x3 regions. Some cells already contain a number. You are supposed to fill the empty cells with numbers from 1 to 9, such that each row, each column and each region contains the numbers 1 to 9 exactly once.
Here is an example Sudoku puzzle:
7 | 4 | 2 | ||||||
9 | 6 | 8 | 5 | 3 | ||||
8 | 2 | 4 | 7 | |||||
4 | 8 | 7 | 2 | 5 | ||||
2 | 9 | 7 | ||||||
6 | 1 | 3 | 9 | 8 | ||||
9 | 3 | 7 | 6 | |||||
8 | 3 | 5 | 1 | 4 | ||||
1 | 7 |
Solution to the example sudoku puzzle:
7 | 1 | 4 | 5 | 6 | 3 | 2 | 9 | 8 |
9 | 2 | 6 | 7 | 8 | 1 | 5 | 4 | 3 |
3 | 8 | 5 | 2 | 9 | 4 | 6 | 7 | 1 |
1 | 4 | 9 | 8 | 7 | 2 | 3 | 5 | 6 |
2 | 3 | 8 | 6 | 4 | 5 | 9 | 1 | 7 |
5 | 6 | 7 | 1 | 3 | 9 | 4 | 8 | 2 |
4 | 9 | 2 | 3 | 1 | 7 | 8 | 6 | 5 |
8 | 7 | 3 | 9 | 5 | 6 | 1 | 2 | 4 |
6 | 5 | 1 | 4 | 2 | 8 | 7 | 3 | 9 |
Solving the Puzzle:
You will develop code in C/ C++ to implement 3 different strategies to solve the puzzle.
1) Backtracking with consistency checking: Implement a backtracking DFS
search algorithm to solve the Sudoku puzzle, taking care that every value
assigned is consistent with the remaining values in the set. Start with the
first variable that has not been assigned a value.
2) Dynamic Variable Ordering: Modify the search step so that instead of picking the first un- instantiated variable, it examines the domains of all un-instantiated variables, and picks the first one with the minimum legal domain size.
3) Some more Constraints: At each step, apply the constraint that if a particular value can be assigned to only one variable in a row, column or a region, then the value should be assigned to that variable.
Reporting your Findings:
Report the number of partial assignments explored (number of times a values
is assigned to any variable) before a solution is reached for 3 example
puzzles, using the 3 criteria indicated above. The puzzles will be posted
shortly. Reporting format is indicated below:
Puzzle A:
Strategy 1:
Strategy 2:
Strategy 3:
Puzzle B:
Strategy 1:
Strategy 2:
Strategy 3:
Puzzle C:
Strategy 1:
Strategy 2:
Strategy 3:
What else should your code provide for:
Your program should also provide a facility for somebody to solve any test puzzle. Ask the user to input the strategy number that the user wants to be followed for solving the puzzle.( Print “ thank you” if the user enters anything other than 1, 2 or 3, and quit the program). Then ask the user to enter the name of the text file containing the puzzle. The input and output formats are indicated below:
Input Format
The input will be a text file containing 9 lines, each line representing one row of the puzzle. Entry for each cell will be followed by a space. For illustration, the sample puzzle indicated above will take the form
7 _ 4 _ _ _ 2 _ _
9 _ 6 _ 8 _ 5 _ 3
_ 8 _ 2 _ 4 _ 7 _
_ 4 _ 8 7 2 _ 5 _
..............
Output Format
You should output the solutions in the same format as the input file.
7 1 4 5 6 3 2 9 8
9 2 6 7 8 1 5 4 3
3 8 5 2 9 4 6 7 1
1 4 9 8 7 2 3 5 6
…………
This should be followed by a line indicating the number of partial assignments explored to reach the solution.
partial assignments needed to reach the solution :…………
Written Document
In addition to your code, submit a brief description of the various algorithms you have used and their implementation. Also comment on the benefits obtained by using various enhancements to the basic backtracking search. This must be submitted in the class on 12/2/2008.
Submission Details : (to be posted shortly)
You are encouraged to try your code on puzzles other than the ones provided by us. The code submitted by you should be written by you, and not copied from any other source.
Documentation
Your code should be properly documented. A README should be submitted with your code which specifies how to compile and run your code. Specifically the file must describe the command line arguments needed to run the code.
Want some extra credits on your assignment? Try to improve the performance of the puzzle solver, using constraint propagation, value ordering or other heuristics that you think would be suitable for the problem. If your strategy produces improved results, output a line indicating this at the beginning of your output file. Call this strategy 4 and indicate the results for puzzles A,B and C as above. Also invite the user to test the new strategy. |