This problem is for if you'd like to tackle something a bit more challenging. You won't get *extra* points if you solve it correctly, but we will indicate in the Grade Book that you either attempted or solved the challenge problem. Problem 5: Sudoku and Satisfiability In this problem we're going to solve a sudoku problem as a satisfiability (which is really all that Sudoku is! A review of how Sudoku works: Each row contains each number from 1 to 4, and no duplicate numbers. Each column contains each number from 1 to 4, and no duplicate numbers. Each 2x2 block (the ones with the bold outline) each contain the numbers from 1 to 4, with no duplicates. Solve the following problem as a satisfiability problem. 4 3 4 2 3 2 Use the predicate Pi,j,n) : the cell at row i and column j has the number n. (a) For this puzzle, we can immediately write out 6 predicates that we know evaluate to TRUE. Do that here. n (b) We can write out a formula to specify the entire solution of the puzzle. The solution is an assignment of truth values such that the conjunction of constraints for rows, columns and blocks are all satisfied. In this part of the problem, you'll work on specifying this formula. Note: It may be helpful to know that we can use the symbol V P(i) to indicate P(0) V P(1) V P(2)... V P(n), and the same for 'A'. i. Write out the equation for the rows. i=0 ii. Write out the equation for the columns. iii. Write out the equation for the blocks. iv. Write out a formula to indicate the entire solution, which is a conjunction of the above 3. (c) Now, solve the puzzle using the parts you wrote out above, showing how you utilize the satisfiability to solve this. For full credit, I want to see evidence of you utilizing the statements you wrote out above, not just a final solution to the puzzle. This problem is for if you'd like to tackle something a bit more challenging. You won't get *extra* points if you solve it correctly, but we will indicate in the Grade Book that you either attempted or solved the challenge problem. Problem 5: Sudoku and Satisfiability In this problem we're going to solve a sudoku problem as a satisfiability (which is really all that Sudoku is! A review of how Sudoku works: Each row contains each number from 1 to 4, and no duplicate numbers. Each column contains each number from 1 to 4, and no duplicate numbers. Each 2x2 block (the ones with the bold outline) each contain the numbers from 1 to 4, with no duplicates. Solve the following problem as a satisfiability problem. 4 3 4 2 3 2 Use the predicate Pi,j,n) : the cell at row i and column j has the number n. (a) For this puzzle, we can immediately write out 6 predicates that we know evaluate to TRUE. Do that here. n (b) We can write out a formula to specify the entire solution of the puzzle. The solution is an assignment of truth values such that the conjunction of constraints for rows, columns and blocks are all satisfied. In this part of the problem, you'll work on specifying this formula. Note: It may be helpful to know that we can use the symbol V P(i) to indicate P(0) V P(1) V P(2)... V P(n), and the same for 'A'. i. Write out the equation for the rows. i=0 ii. Write out the equation for the columns. iii. Write out the equation for the blocks. iv. Write out a formula to indicate the entire solution, which is a conjunction of the above 3. (c) Now, solve the puzzle using the parts you wrote out above, showing how you utilize the satisfiability to solve this. For full credit, I want to see evidence of you utilizing the statements you wrote out above, not just a final solution to the puzzle