CS 1112 Project 4, part A due Thurs, Apr. 8, 11pm EDT

Sudoku checker

Sudoku is a popular Japanese puzzle game that rose to international popularity in 2005. At the higher levels of difficulty, the puzzles are difficult to solve for both human and machine! In this project, you will write a “Sudoku checker” that determines whether a candidate solution is valid—we are not writing a program to solve the puzzle. If you are not familiar with the game, consult Wikipedia and try to solve a few puzzles online!

A Sudoku solution is valid if all of the following properties are true:

1. The provided solution fits in a 9×9 grid.
2. The entire board contains only integers in the range of 1–9 (inclusive).
3. Each row contains the numbers [1..9], with no repeated values.
4. Each column contains the numbers [1..9], with no repeated values.
5. Each 3-by-3 sub-grid (delineated by heavy lines in the puzzle and solution above) contains the numbers [1..9], with no repeated values.

You will write a function isValidSudoku(), containing at least one subfunction, isValidPartition(), as specified below:

Subfunction isValidPartition() has one type double input parameter called subarray which stores integer values. This function returns the type logical value true if the following are true:

• subarray is a length-9 vector or a 3-by-3 matrix.
• subarray contains the numbers [1..9] with no repeated values (properties 3, 4, and 5 above). Otherwise the logical value false is returned.

Function isValidSudoku() has one type double input parameter called board which stores integer values. This function returns the type logical value true if board is a valid Sudoku solution (properties 1–5 above); otherwise it returns the logical value false. This function should make effective use of isValidPartition().

You will write the function headers as well as concise and informative function comments for these functions. Note these additional considerations:

• You can use vectorized and/or non-vectorized code; both are worth practicing!
• This question involves designing your own algorithm using the constructs and data structures that we have discussed—loops, conditionals, 1D and 2D arrays. Practice using them instead of looking up specialized built-in functions. For full credit, do not use built-in functions other than these basic ones: zeros(), ones(), length(), size(), and from Chapter 6 of our textbook, sum(), any(), and all(). (You don’t need all of them.)
• We have broken down the problem into the two functions, isValidPartition() and isValidSudoku(), already. Do you have other ideas for further problem decomposition using subfunctions?

To help you with testing, we provide two example 9-by-9 matrices below. Be sure to do additional testing! Tip: write your subfunctions in their own “.m” files first, so you can test them in the command window, and then copy them into isValidSudoku.m after you’re confident they work.

validSol = [1 7 2 5 4 9 6 8 3; ...
            6 4 5 8 7 3 2 1 9; ...
            3 8 9 2 6 1 7 4 5; ...
            4 9 6 3 2 7 8 5 1; ...
            8 1 3 4 5 6 9 7 2; ...
            2 5 7 1 9 8 4 3 6; ...
            9 6 4 7 1 5 3 2 8; ...
            7 3 1 6 8 2 5 9 4; ...
            5 2 8 9 3 4 1 6 7];

invalidSol = [1 7 5 8 3 9 4 2 6; ...
              6 3 8 2 7 4 9 1 5; ...
              4 2 9 6 5 1 3 7 8; ...
              8 1 6 3 9 6 7 4 2; ...
              5 4 7 1 6 2 8 3 9; ...
              2 6 3 4 2 7 6 5 1; ...
              7 5 4 9 2 6 1 8 3; ...
              9 8 1 5 4 3 2 6 7; ...
              3 6 2 7 1 8 5 9 4];

Balancing chemical reactions

Systems of linear equations often arise when trying to balance the effects of multiple interacting processes. Their interaction couples the equations governing any one of them, so the total set of equations must be solved simultaneously. Fortunately, regardless of whether such equations originate from mechanics, chemistry, or biology, Matlab makes solving them a straightforward affair.

[Our objective for this problem is to show how you can use Matlab as a solver of systems of linear equations. We do not expect you to know linear algebra, nor are we trying to teach linear algebra. We will use the solver as a “black box,” so your only real task is to turn a set of given equations into a matrix and a vector and then use the solver, which is just an operator. So there's no need to be afraid of the chemistry or math!]

Consider a set of n linear algebraic equations of the general form (1) $$\begin{array}{ccccccccc} a_{11}x_{1} &+& a_{12}x_{2} &+& \ldots &+& a_{1n}x_{n} &=& b_{1} \\ a_{21}x_{1} &+& a_{22}x_{2} &+& \ldots &+& a_{2n}x_{n} &=& b_{2} \\ \vdots & & \vdots & & & & \vdots & & \vdots\\ a_{n1}x_{1} &+& a_{n2}x_{2} &+& \ldots &+& a_{nn}x_{n} &=& b_{n} \end{array}$$ where the a's are known constant coefficients, the b's are known constants, and the n unknowns, x₁, x₂, …, x_n, are raised to the first power. This system of equations can be expressed in matrix notation as $$\mathbf{Ax} = \mathbf{b}$$ or (2) $$\left[ \begin{array}{cccc} a_{11} & a_{12} & \ldots & a_{1n} \\ a_{21} & a_{22} & \ldots & a_{2n} \\ . & . & & . \\ . & . & & . \\ . & . & & . \\ a_{n1} & a_{n2} & \ldots & a_{nn} \end{array} \right] \left[ \begin{array}{c} x_{1} \\ x_{2} \\ . \\ . \\ . \\ x_{n} \end{array} \right] = \left[ \begin{array}{c} b_{1} \\ b_{2} \\ . \\ . \\ . \\ b_{n} \end{array} \right]$$ To solve this linear system of equations is to find the values x₁, x₂, …, x_n such that $\mathbf{Ax} = \mathbf{b}$. In Matlab, the solution can be found using the backslash, called the matrix left divide operator (3):

x = A\b

where A is the n-by-n matrix of coefficients, b is the length-n column vector of constants, and the result x is the length-n column vector of values such that $\mathbf{Ax} = \mathbf{b}$.

Your job: Write a script chemBalance.m to find the amount of ingredients (methane and oxygen, in moles) to produce 5 mol (roughly 90 mL) of water via the following reaction:

x_m CH₄ + x_o O₂ → x_c CO₂ + x_w H₂O

Here, x_m is the amount of methane provided, x_o is the amount of oxygen provide provided, x_c is the amount of carbon dioxide produced, and x_w is the amount of water produced. In order to balance this reaction, we write down equations conserving the number of atoms of each element. Conservation of oxygen (O), for example, leads to the following equation:

2 x_o = 2 x_c + x_w

(each oxygen molecule provides two oxygen atoms, while each carbon dioxide molecule requires two oxygen atoms and each water molecule requires one).

You need to do the following:

1. Write down two more elemental conservation equations: one for hydrogen (H) and one for carbon (C). Additionally, write down an equation specifying our desired amount of reaction product. This gives us a total of four equations, matching our number of unknowns.
2. Rewrite these equations in the general form of (1) by collecting terms together, where the unknowns are x_m, x_o, x_c, and x_w. This means for each equation, re-arrange it so that the unknowns are on the left hand side while the constants are on the right hand side. For example, the oxygen equation can be rearranged as follows:

   2 xo	= 2 xc + xw	Original
   2 xo - 2 xc - xw	= 0	All unknowns moved to left side; all constants moved to right side
   0 xm + 2 xo - 2 xc - 1 xw	= 0	Re-order left side and make coefficients explicit

   The final rearranged equation should have all four unknowns on the left side in a consistent order; some of their coefficients may be zero, as shown above. Do this rearrangement of each conservation equation by hand (on paper)—you do not need to include this step in your script or submit it (though documenting it in a code comment doesn't hurt).
3. In your script, create the 4-by-4 matrix A—the coefficients of the 4 unknowns in the 4 equations—and the length-4 column vector b—the constants on the right side of the re-arranged equations—as shown in (2).
4. Apply the matrix left division operator as shown in (3) to solve for x_m, x_o, x_c, and x_w.
5. Finally display the values of x_m and x_o neatly, labeling them as the required amounts of methane and oxygen (with units).

Note that in this problem, most of the work is done by hand and you will write very little code. However, make sure that your script is cleanly commented and that the print output is clean and descriptive.