Sudoku PuzzleWhat to hand inGeneral InstructionsICS 171Fall 2005Project(due November 10)Sudoku PuzzleFigure 1: Sudoku puzzle Figure 2: SolutionConsider the classic 9-by-9 Sudoku puzzle in Figure 1. The goal is to fill in the empty cells such that every row, every column and every 3-by-3 box contains the digits 1 through 9. The solution to the puzzle is given in Figure 2 and it satisfies the following constraints:- The digits to be entered are 1, 2, 3, 4, 5, 6, 7, 8, 9.- A row is 9 cells wide. A filled-in row must have one of each digit. That means thateach digit appears only once in the row. There are 9 rows in the grid, and the sameapplies to each of them.- A column is 9 cells tall. A filled-in column must have one of each digit. That means that each digit appears only once in the column. There are 9 columns in thegrid, and the same applies to each of them.- A box contains 9 cells in a 3-by-3 layout. A filled-in box must have one of each digit. That means that each digit appears only once in the box. There are 9 boxes in the grid, and the same applies to each of them.You are to write a program for solving the classic 9x9 Sudoku puzzle. Note that every puzzle has only one correct solution (see Figure 2).ICS 171Fall 2005Your program must be based on the search algorithms presented in class (e.g. backtracking, forward-checking etc.). Your algorithm should be guaranteed to find the answer (but could take very long to find it), i.e. it must be optimal. Note that local search algorithms can get stuck in local minima and are typically not guaranteed to find the correct answer (unless you prove otherwise). However, one could imagine that local search is so much faster that is worth it giving it a try and only switch to exhaustive search when it fails. Besides the correct solution, your program must also output the running time (in seconds and milliseconds) it took to solve the puzzle. The programs will compete on some benchmarks to select the fastest solver. Fame will be bestowed upon the winner!What to hand in- Source code must be submitted through CHECKMATE (checkmate.ics.uci.edu).- You will hand in a report containing the description of your method as well as examples demonstrating that your program works correctly. Limit your discussionto 2 pages.We require that you test your program on the puzzle from Figure 1. Additional puzzles will be posted in EEE. We will also organize a competition to determine the fastest puzzlesolver.General Instructions- You may discuss the problem with other people but must develop your program independently.- Your program should have two arguments. The first one is the name of the file containing the Sudoku puzzle. The second argument is the name of the output file and it should contain the solution. We suggest the following format: sudoku puzzle_file solution_file. We want to be able to run your program without changes to your source code.- We recommend the following file format: the puzzle is represented by a 9x9 matrix, where a “0” means that the respective cell is unassigned. For example, theinput file corresponding to the Sudoku puzzle in Figure 1 is given below. The solution file should respect a similar format.0 6 0 1 0 4 0 5 00 0 8 3 0 5 6 0 02 0 0 0 0 0 0 0 18 0 0 4 0 7 0 0 60 0 6 0 0 0 3 0 07 0 0 9 0 1 0 0 45 0 0 0 0 0 0 0 20 0 7 2 0 6 9 0 00 4 0 5 0 8 0 7 0ICS 171Fall 2005- You are required to use C/C++, Java or MATLAB programming languages.- Project descriptions will be discussed in sections. Feel free to contact your TA if you have any uncertainties.- Additional info at:
View Full Document
Unlocking...