CSE 303: Autumn 2006, Assignment 3

Due: Wednesday 25 October 2006, 2:00pm

Updates

• Sunday, October 22: Changed the beginning of problem 2 to define the "union" of two bounding boxes.

Assignment Overview

This is an individual assignment in which you will modify some small C programs. Begin by downloading hw3.tgz and unpacking it with tar -xvzf hw3.tgz. This contains all the files referred to in this assignment. (Note: Soon we will assume that you know how to unpack files like this.)

1. Sudoku

The program sudoku.c solves sudoku puzzles. As explained in this Wikipedia article on sudoku, the aim of these puzzles is to enter the digits 1 through 9 in each cell of a 9×9 grid made up of 3×3 subgrids (called "regions") so that each row, column, and region contains exactly one instance of each digit. A set of clues, or "givens", constrain the puzzle such that there is only one way to correctly fill in the remainder.

Description

The given program attempts to solve puzzles passed in on stdin. The expected format can be seen in puz9x9a.txt. Cells that contain the digits 1-9 are clues, and cells that contain 0 must be filled in by the program. If you name the program sudoku when you compile it, you should be able to invoke it by typing ./sudoku <puz9x9a.txt. The result is printed on stdout, along with a header showing the date. The output should look exactly like puz9x9asolution.txt, though the date will vary.

Changes

You will fix some problems with this program, and then modify it.

• When you attempt to compile sudoku.c, you will get an error. Fix this error by adding a single character to the program. In a file named readme.txt, write a short explanation for why this change is necessary under the heading "Problem 1A". Hint: learn more about parameter passing of multi-dimensional arrays.
• After you fix the above problem and attempt to run the program as described earlier, it will crash with a "Segmentation Fault." Once you have found out where the program is crashing, fix this problem by removing one character and adding two characters (all on the same line). Write a short explanation for why this change is necessary under the heading "Problem 1B" in readme.txt. Hints: Think about where data exists in memory.
• After you complete the two above changes, you should be able to invoke the program as described above. You may note, however, that the program does not actually solve the puzzle correctly. Though each row and column contains exactly one instance of each digit, each 3×3 subgrid may contain repeated numbers. Modify the program so that it gives a correct solution. The sample solution does this by adding seven lines (including one comment) to the program, and your solution should be of similar complexity. For reference, the file puz9x9bsolution.txt contains the correct solution to puz9x9a.txt, though it is in a different format.
• The sudoku puzzles processed by this program are not very easy for humans to read. They would be much easier to read if they visually separated the 3×3 subgrids in each puzzle, as in puz9x9b.txt. Modify the program to read puzzles in this format and output them in a similar format. The output from the program when run on puz9x9b.txt should look exactly like puz9x9bsolution.txt (except that the date may be different).
• Right now, the program may do unexpected things if we pass in a puzzle in the wrong format. Modify the program to detect problems with the format. If any are detected, print an appropriate error message to stderr and exit with a non-zero return code. Hints: scanf, fprintf.

Advice

Understand the code provided to you. You can use man to learn about C library functions that are unfamiliar (e.g. man puts). Some functions (such as time), are also Linux commands, and man may show documentation for these rather than the C library functions. The documentation is there, however, under a different "section". You can use man -a to show all man pages for all sections one after the other, or you can use man -S <section name>, to access the section you want. The section name is given is given in parentheses after the page name in the first and last lines of the man page (e.g. man -S 2 time).

When debugging the segmentation fault, try adding printf statements to the program to find out where the program crashes. (Sometimes, this is the only way to debug such problems.) Make sure you remove these printf statements in your final version.

When detecting bad input, you don't need to detect every possible deviation from the format we specified (although you are free to do so, if you wish). We only require you to detect format errors that would cause you to read incorrect values from the file.

Note: Writing programs like this one to solve puzzles is a classic problem in artificial intelligence. This program searches the entire space of solutions, which is horribly inefficient and won't produce an answer in any reasonable ammount of time for some puzzles. We invite you to look for better solutions outside of class!

2. Bounding Boxes

You have been hired to help develop a high-performance 2D graphics system for a handheld device. Your current task is to develop a "bounding box" data structure that will be used throughout the system, and you will experiment with a number of options. Open the file bboxes.c, which contains the definition for a BBox type, and several supporting functions. At the location indicated, you will add four functions that compute the "union" of two bounding boxes. The union of two bounding boxes is a new bounding box that is just large enough to enclose the two original bounding boxes. Note that, as in most window systems, X increases from left to right, and Y increases from top to bottom. It is reasonable to assume that top <= bottom and left <= right.

• BBoxUnion1 takes two BBox arguments and returns a BBox.
• BBoxUnion2 takes two pointers to BBox arguments and returns a pointer to a new BBox that holds the union. Use malloc to heap-allocate a new BBox for the result to point to. Do not call any helper functions other than malloc and other functions that were originally included in the file bboxes.c.
• BBoxUnion3 behaves just like BBoxUnion2, except that it uses BBoxUnion1 as a helper function. It should not read any fields in the BBox type directly.
• BBoxUnion4 has return-type void and takes as arguments three pointers to bounding boxes. It mutates the first bounding box to contain the union of the second and third bounding boxes.

Advice

You can comment out parts of BBoxTest to test some of your functions before you write the others. No function body needs to be longer than a few lines. The correct output is below.

[(0,0) (0,0)]
[(-4,-8) (0,0)]
[(0,0) (5,10)]
[(-3,-3) (1,1)]
[(-1,-1) (6,6)]
[(-4,-8) (0,0)]
[(-4,-8) (5,10)]
[(-3,-3) (6,6)]
[(-4,-8) (0,0)]
[(-4,-8) (5,10)]
[(-3,-3) (6,6)]
[(-4,-8) (0,0)]
[(-4,-8) (5,10)]
[(-3,-3) (6,6)]
[(-4,-8) (0,0)]
[(-4,-8) (5,10)]
[(-3,-3) (6,6)]

3. Survey

Please fill out this survey to give the CSE 303 teaching staff us a sense of how well our course materials are being received and to ask for your feedback. The survey is completely anonymous. Please fill it out only once.

4. Extra Credit

Remember the course policy on extra credit. You may do either or both of the following problems.

• Your final solution for sudoku.c solves 9×9 puzzles with 3×3 regions. Make another program called sudoku2.c that solves either 9×9 puzzles with 3×3 regions or 4×4 puzzles with 2×2 regions (as in puz4x4.txt). You must dynamically allocate the array that holds the puzzle so as not to waste space. The program should assume that puzzles are size 9×9 unless a command line argument "-4" is received. The output for 9×9 puzzles should be the same, and the output for 4×4 should be like that shown in puz4x4solution.txt.
• Add a function called BBoxOverlap to the file bbOverlap.c. This function should take two BBox arguments and return an interger that is 0 if the boxes do not overlap or 1 if they do. The function body must contain only four comparison operations ANDed together and returned. (This is a very fast bounding-box overlap test that is used in many graphics systems.) The correct output of the program is "0 0 1 1 1 1 1 0 0 0 0 1 1 1 1 1 0 0 ".

Assessment

Your solutions should be

• Correct C programs that compile without errors or warnings using gcc -Wall on attu.cs.washington.edu
• In good style, including indentation and line breaks
• Of reasonable size

Turn-in instructions

Use the standard turn-in instructiond described here. Your directory should contain the files sudoku.c, bboxes.c, and readme.txt. If you do the extra credit, you should also turn in sudoku2.c and/or bbOverlap.c.