CS16, Summer 2012

Practice Lab:
Two-dimensional arrays

Goals for this lab

By the time you have completed this lab, you should be able to

Create and initialize two-dimensional arrays
Apply nested for loops with two-dimensional arrays
Write functions to process two-dimensional arrays

Step by Step Instructions

Step 1: Create a practice directory

Step 2: Practice using a 2-dimensional array from the ch prompt

Start ch.
Then create a two-dimensional array, x, that can store 3 rows of 10 int values (so 30 ints altogether):

ch> int x[3][10];

Another ch feature, the stackvar command, can be used to show the contents of all stack variables. Try it now, and notice that ch filled the array with zeroes (unlike standard C):

ch> stackvar
    x (C array)
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

Let's fill up the array with values that better reflect their positions. Complete the following steps:

Set the elements of the first row to the values 0 through 9 in order. Leave the first element (x[0][0]) alone, because it already equals 0. You can set the others one at a time, as in:
```
ch> x[0][5] = 5;
5
```
But no need to do that 9 times when you can use a for loop instead:
```
ch> int i;
ch> for (i=0; i<10; i++) /* set array element here */;
```
And then you can use stackvar again to verify the elements are set properly. You might notice a new variable on the stack (i in our case) used for loop control:
```
ch> stackvar
    x (C array)
0 1 2 3 4 5 6 7 8 9
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
    i                   10
```
Only the first row was affected if you did the last step as instructed. Usually we initialize all of the values in all of the rows of an array like this one using nested for loops. In that case, i normally refers to a current row, and j refers to each element in the row. Since x has 3 rows and 10 values in each row, i should vary from 0 to 2, and j should vary from 0 to 9, just like the following for loops (the '\' continuation characters at the end of each of the first two lines are to make ch happy):
```
ch> int j;
ch> for (i=0; i<3; i++)\
ch>     for (j=0; j<10; j++)\
ch>         /* refer to x[i][j] here */
```
Type the headers of these nested loops now at the ch prompt, and on the last line:
set x[i][j] to 10 times i, plus j

Check your work with stackvar to make sure it matches the following before going to part c:
```
ch> stackvar
    x (C array)
0 1 2 3 4 5 6 7 8 9
10 11 12 13 14 15 16 17 18 19
20 21 22 23 24 25 26 27 28 29
    i                   3
    j                   10
```
It is worth examining x more closely. First notice that it really can be treated as 3 one-dimensional arrays, each of size 10. To prove it, and learn about another ch tool at the same time, try finding the sums of each row using the built-in ch function named sum:
```
ch> sum(x[0])
45.0000
```
Try it for the other two rows too. Then to find out how versatile the sum function is, try sum(x) all by itself.
Last week you learned that an array name "points" to a memory address, the location where the first array element is stored, and you learned that ch will display this address if you just type the array's name. Do that now (your results will differ from the following):
```
ch> x
0x9678d10
```
Then type the "names" of each of the three component arrays, to find out what prints. For example:
```
ch> x[0]
0x9678d10
```
What do you notice about the address of x[0] compared to the address of x by itself? Now, remembering the addresses are shown in hexadecimal, try to calculate the difference between x[1] and x[0]. Notice it is the same as the difference between x[2] and x[1]. Hmmm. You should find the difference is 28 hexadecimal (or 40 decimal) in both cases - the size of ten 4-byte integers.

Step 3: Write and test a function to sum a column of a 2-D array

In Step 2.c. above, you saw that you can find the sum of a row in a 2-dimensional array by passing just the row to a function. To sum the elements of a column requires a special purpose function. And whenever a function must process more than one dimension of an array, it is necessary to specify the constant size(s) of all but the first dimension in the function's header.

Do NOT exit ch (to keep the array from Step 2 in memory), but open emacs or another editor to create a file named colsum10.chf (a ch "function file"). Type or copy/paste this comment and function header at the beginning of the file - and edit NAME(S):

/* returns sum of the first n values in column k of x,
   where x is an array with 10 values per row
   NAME(S), 5/16/2011 */
int colsum10(int x[][10], int n, int k)

Complete the function to return an int value that is the sum of the first n elements in column k of x.

Save the file as colsum10.chf in your practice directory. Then test it from the ch prompt. If something doesn't work correctly, fix the problem before going to Step 4. Here are some correct answers to expect:

ch> colsum10(x, 3, 2)
36
ch> colsum10(x, 3, 9)
57

Step 4: Write and test functions to check Sudoku rules

Sudoku has many rules, and so a program attempting to play it would need many functions to verify the rules are followed. Don't worry, we won't make you write all of these functions right now! But you can handle a couple of them now. A Sudoku puzzle is a table of integers with 9 rows and 9 columns, so it is readily summarized by an array such as the following:

ch> int puzzle[9][9];

Among other rules, any single row (and column) of a Sudoku puzzle must not contain more than one of the digits 1 through 9. Usually 0 is used to indicate "empty" elements, so it is okay to have more than one 0 in a row (or column). A perfect row (or column) would have all of the digits 1 through 9, so no 0s. The following nested loops make the sixth row and column of puzzle technically perfect, while all of the other rows and columns are legal but mostly empty:

ch> int i;
ch> for (i=0; i<9; i++) \
ch>     puzzle[5][i] = puzzle[i][5] = i+1;

But then the following statement will cause rule violations in the third row and third column of puzzle. See why:

ch> puzzle[2][2] = 3;
3
ch> stackvar
    puzzle (C array)
0 0 0 0 0 1 0 0 0
0 0 0 0 0 2 0 0 0
0 0 3 0 0 3 0 0 0
0 0 0 0 0 4 0 0 0
0 0 0 0 0 5 0 0 0
1 2 3 4 5 6 7 8 9
0 0 0 0 0 7 0 0 0
0 0 0 0 0 8 0 0 0
0 0 0 0 0 9 0 0 0
    i                   9

You can exit ch now. Make a copy of this skeleton program in your ~/cs16/practice directory, and cd to this directory. You can cp a copy from the instructor's account:

-bash-4.1$ cp ~kyledewey/cs16/practice/check.c ~/cs16/practice/

Study the parts of the program that are complete: (1) symbolic constants are defined to represent all of the possible return values from your functions; (2) the two functions currently are defined to return a value indicating the function is not done yet; and (3) a main function is completely defined to read 81 values from stdin (i.e., the user or a redirected file) into a 9x9 integer array, and print the results of the two functions (if done) for every row and column of the puzzle.

Accomplish as many of the following steps as you have time to complete in the indicated order. Check the results of each part before going on to the next part. Store a copy of the puzzle above in ~/cs16/practice/ to check your results: puzzle1.txt (also can cp ~kyledewey/cs16/practice/puzzle1.txt).

Use the input redirection arrow, <, to input the data to your program, as in the following complete sample run:

-bash-4.1$ ./check < puzzle1.txt
enter 81 puzzle values in row order:
row 0 is okay
row 1 is okay
row 2 is illegal
row 3 is okay
row 4 is okay
row 5 is perfect
row 6 is okay
row 7 is okay
row 8 is okay
column 0 is okay
column 1 is okay
column 2 is illegal
column 3 is okay
column 4 is okay
column 5 is perfect
column 6 is okay
column 7 is okay
column 8 is okay

Only expect matching results if and when you have completed all of the following parts - but remember that it is not necessary to do them all!

Type your name(s) in the comment at the top.

Revise the okRow function to actually check the 9 values in the array named row. Return OKAY only if all values are greater than or equal to 0 and less than or equal to 9, and no value (except 0) is in the array more than once. Otherwise return ILLEGAL.

First make a plan! In our solution, we created an array of size 10 named in, with all elements initialized to 0 (int in[10] = {0};). Then in a for loop (i=0; i<9; i++), we checked the value of in[row[i]] - if it still was equal to 0, then we set it 1; but if it already was set to 1, then we returned ILLEGAL. You might try that approach too, or devise one of your own.

Revise the okColumn function to check the 9 values in column k of the two-dimensional puzzle array, returning OKAY or ILLEGAL as appropriate
Enhance the okRow function to return PERFECT if all 9 values (1-9) are included in the array.
Enhance the okColumn function to return PERFECT if all 9 values (1-9) are included in column k of the puzzle.

Fully test each step before proceeding to the next one.

Extra Challenge
Another rule for Sudoku puzzles applies to nine 3x3 boxes within the 9x9 puzzle. These boxes are formed by grouping rows and columns 0-2, 3-5 and 6-8. So the first box, for example, includes all adjacent elements from puzzle[0][0] through puzzle[2][2]. This rules is essentially the same as the row and column rules described above - a box is perfect if all values 1-9 are present, okay if one or more of those values is replaced by 0, or illegal in any other case.
Write function okBox to work like okRow and okColumn above. The function should have the following header:
int okBox(int puzzle[9][9], int top, int left)
So okBox(puzzle, 0, 0) would check the first 3x3 box, and okBox(puzzle, 6, 6) would check the last one.
Revise a copy of check.c to check all nine 3x3 boxes of the puzzle, and neatly print the results.

Revise a copy of check.c to keep track of all checks. Then print summary results at the end, such as "All rows okay" or "4 out of 9 rows illegal" or even "Entire puzzle is perfect."

Adapted by Kyle Dewey from a lab prepared by Michael Costanzo.