Description
Please work on EWS for this MP to avoid compilation error on verification script. Introduction Your task this week is to implement a C program that solves the Sudoku puzzle using recursive backtracking. A standard Sudoku puzzle contains 81 cells, in a 9 by 9 grid, and has 9 zones. Each zone is the intersection of 3 rows and 3 columns (e.g. size 3×3). Each cell may contain a number from 1 to 9 and each number can only occur once in each 3×3 zone, row, and column of the grid. At the beginning of the game, several cells begin with numbers, and the goal is to fill in the remaining cells with numbers satisfying the puzzle rule. A Sudoku example is shown below: +———————–+ | 1 2 3 | 4 5 6 | 7 8 9 | | 4 5 6 | 7 8 9 | 1 2 3 | | 7 8 9 | 1 2 3 | 4 5 6 | |——-+——-+——-| | 2 3 4 | 5 6 7 | 8 9 1 | | 5 6 7 | 8 9 1 | 2 3 4 | | 8 9 1 | 2 3 4 | 5 6 7 | |——-+——-+——-| | 3 4 5 | 6 7 8 | 9 1 2 | | 6 7 8 | 9 1 2 | 3 4 5 | | 9 1 2 | 3 4 5 | 6 7 8 | +———————–+ The pseudocode of a typical backtracking algorithm to solve the Sudoku puzzle is given as follows: The Pieces In this MP, you are given a set of files: main.c – The C source file that contains the main function to run the Sudoku solver. sudoku.c – The main source file for your code. Details can be found in the next section. sudoku.h/sudoku_golden.h – The header definition of the program. Details You should put your codes only in sudoku.c and accomplish all field marked by TODO. The functions we provide follow the pseudocode of the backtracking algorithm we gave in the introduction MP7_dist.tar.gz bool solve_sudoku(int sudoku[9][9]) { int i, j; if (all cells are assigned by numbers) { return true; } else { find a non-filled cell (i, j) } for (int num = 1; num <= 9; num++) { if (cell (i, j) can be filled with num) { sudoku[i][j] <- num; if (solve_sudoku(sudoku)) { return true; } sudoku[i][j] <- non-filled; } } return false; } section. You should begin with the above three functions is_val_in_row, is_val_in_col, and is_val_in_3x3_zone, that check if the given number val has already been filled in the row i, column j, and the 3×3 zone corresponding to the cell (i, j). Return 1 (true) if the number exists and 0 (false) otherwise. Based on these three functions, you should use another function is_val_valid that checks the legality of filling a cell (i, j) with a given number val. Give the helper function is_val_valid which you have to finish, your final job is to complete the function solve_sudoku that implements the recursive backtracking algorithm as shown in the first section. We suggest drawing a diagram of the recursive backtracking by hand if you don’t understand it. Building and Testing We suggest that you begin by developing your code using on the EWS Linux machine. For better flexibility, we have offered a make file that wraps the compilation process and program execution. In order to compile the whole program, type the following command under MP7 folder: If successful, the compiler produces an executable called mp7. You can then run the program by the following commands: The command make sudoku1 runs your program with a given sudoku instance specified in sudoku1.txt and so on. We give you three Sudoku instances and you are free to make any change from the given files. By default, the program will invoke a hidden golden checker to test your solution and display the solution message every time you make a Sudoku instance. Note that we will use another Sudoku instance (hidden) to test your program during the final grading. All Sudoku instances to test your program will be legal (i.e., a solution always exists). Grading Rubric Functionality (totally 90 points) +10 – is_val_in_row function works correctly +10 – is_val_in_col function works correctly +30 – is_val_in_3x3_zone function works correctly +40 – solve_sudoku function works correctly Style (totally 5 points) +5 – code is clear and well-commented, and compilation generates no warnings (note: any warning means 0 points here) Comments, clarity, and write-up (totally 5 points) +5 – introductory paragraph explaining what you did (even if it’s just the required work) Note that some point categories in the rubric may depend on other categories. If your code does not compile, you may receive a score close to 0 points. int is_val_in_row(const int val, const int i, const int sudoku[9][9]); int is_val_in_col(const int val, const int j, const int sudoku[9][9]); int is_val_in_3x3_zone(const int val, const int i, const int j, const int sudoku[9][9]); int is_val_valid(const int val, const int i, const int j, const int sudoku[9][9]); int solve_sudoku(int sudoku[9][9]); make make sudoku1 make sudoku2 make sudoku3 ——————- Begin Verifying MP7 ——————— [+10]: Your is correct. [+10]: Your is correct. [+30]: Your is correct. [+40]: Your is correct. Your final score for this MP is 90 ——————– End Verifying MP7 ———————- No labels
