In C

sudoku: Checking Sudoku solutions Write a program sudoku that (part 1) checks whether a proposed Sudoku solution is correct and (part 2) checks whether a partially-solved Sudoku puzzle with one unknown square can be solved. sudoku takes a single argument, which is the path to a le containing a completed or almost-completed Sudoku puzzle. A completed Sudoku puzzle is a 9 9 matrix containing the digits 1{9, inclusive. The matrix is divided into nine 3 3 submatrixes, themselves arranged in a 3 3 square. A completed Sudoku puzzle is a correct solution if and only if it has the following properties: Each digit occurs exactly once in each row (that is, no row contains any digit more than once. Each digit occurs exactly once in each column. Each digit occurs exactly once in each submatrix. For example, this completed puzzle is a correct solution: 2 6666666666664 5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9 3 7777777777775 An almost-completed Sudoku puzzle is similar, except that one or two elements are unspeci ed. This problem has two parts. For part one (6 points), you must be able to check whether a completed Sudoku puzzle contains a correct solution. For part two (6 points), you must be able to determine whether an almost-completed Sudoku puzzle is solvable. The remaining 4 points are for style. Both parts are submitted as a single program. You will receive partial credit if your program correctly handles part one. 1.7.1 Correctness checking The input le contains a completed Sudoku puzzle. The puzzle is given on nine lines, each of which con- tains nine digits without any separation. Note that the digit 0 will not occur. The input le file1.txt corresponding to the puzzle above would contain: 534678912 672195348 198342567 859761423 426853791 713924856 961537284 287419635 345286179 When given such a le, sudoku must determine whether the completed puzzle is a correct solution (meaning it satis es the three properties). If so, it prints correct. Otherwise, it prints incorrect. If the input le does not exist, is not readable, or does not follow the format speci ed here, sudoku may print error.

Usage $ ./sudoku file1.txt correct 1.7.2 Solvability checking The input le contains an almost-completed Sudoku puzzle. The format is the same as above|nine lines with nine characters each|except that up to two of the characters may be spaces instead of digits. The spaces indicate that the digit for that element is unspeci ed. The input le file2.txt contains an almost-completed puzzle with two unknown entries: 435269781 682571493 1978345 2 826195347 374682915 951743628 519 26874 248957136 763418259 If the input le contains an almost-completed puzzle, sudoku must determine whether the puzzle can be solved. If the puzzle has unspeci ed entries, can they be replaced by a digits such that the completed puzzle is a correct solution? If so, sudoku prints solvable. Otherwise, it prints unsolvable. If the puzzle contains no unspeci ed entries (that is, it is a completed puzzle), sudoku will print correct or incorrect as before. If the input le does not exist, is not readable, does not follow the format speci ed above, or contains more than two unspeci ed elements, sudoku may print error. Usage $ ./sudoku file2.txt solvable