Lab 4: C Programming Project
Overview
This C programming project focuses on dynamic memory allocation, pointers, file I/O, and string manipulation.
Program Description
In this lab, you will write a program to play a game of Sudoku with the user. The goal of the game is to fill in missing numbers in an 9x9 array. Each number in the set [1-9] must be found in every row, every column, and every 3x3 block in the array. For example, here is an example game, including initial game state and final game state. The user-provided solution is shown in red. Note that a Sudoku board could have multiple solutions! Thus, the solution provided with the initial puzzle may not be the only valid solution the user should provide.
| Initial State: | Final State: |
|---|---|
 |
(User input in red) |
An example game program, including user input, is shown below. While your program does not have to match this example program letter-by-letter, it should provide similar functionality.
SUDOKU GAME
Rules: Fill the 9x9 square such that each row, column,
or block contains all of the numbers 1-9
Enter game filename to load: sudoku_puzzle.txt
Loading game file sudoku_puzzle.txt
Current puzzle has 51 unsolved items
1 2 3 4 5 6 7 8 9
|-----------------------|
1 | 5 3 # | # 7 # | # # # |
2 | 6 # # | 1 9 5 | # # # |
3 | # 9 8 | # # # | # 6 # |
|-----------------------|
4 | 8 # # | # 6 # | # # 3 |
5 | 4 # # | 8 # 3 | # # 1 |
6 | 7 # # | # 2 # | # # 6 |
|-----------------------|
7 | # 6 # | # # # | 2 8 # |
8 | # # # | 4 1 9 | # # 5 |
9 | # # # | # 8 # | # 7 9 |
|-----------------------|
Enter row,col,value to solve a square, or -1 to exit: 1,3,4
Current puzzle has 50 unsolved items
1 2 3 4 5 6 7 8 9
|-----------------------|
1 | 5 3 4 | # 7 # | # # # |
2 | 6 # # | 1 9 5 | # # # |
3 | # 9 8 | # # # | # 6 # |
|-----------------------|
4 | 8 # # | # 6 # | # # 3 |
5 | 4 # # | 8 # 3 | # # 1 |
6 | 7 # # | # 2 # | # # 6 |
|-----------------------|
7 | # 6 # | # # # | 2 8 # |
8 | # # # | 4 1 9 | # # 5 |
9 | # # # | # 8 # | # 7 9 |
|-----------------------|
Enter row,col,value to solve a square, or -1 to exit: 1,4,6
Current puzzle has 49 unsolved items
1 2 3 4 5 6 7 8 9
|-----------------------|
1 | 5 3 4 | 6 7 # | # # # |
2 | 6 # # | 1 9 5 | # # # |
3 | # 9 8 | # # # | # 6 # |
|-----------------------|
4 | 8 # # | # 6 # | # # 3 |
5 | 4 # # | 8 # 3 | # # 1 |
6 | 7 # # | # 2 # | # # 6 |
|-----------------------|
7 | # 6 # | # # # | 2 8 # |
8 | # # # | 4 1 9 | # # 5 |
9 | # # # | # 8 # | # 7 9 |
|-----------------------|
Enter row,col,value to solve a square, or -1 to exit: 1,6,8
Current puzzle has 48 unsolved items
1 2 3 4 5 6 7 8 9
|-----------------------|
1 | 5 3 4 | 6 7 8 | # # # |
2 | 6 # # | 1 9 5 | # # # |
3 | # 9 8 | # # # | # 6 # |
|-----------------------|
4 | 8 # # | # 6 # | # # 3 |
5 | 4 # # | 8 # 3 | # # 1 |
6 | 7 # # | # 2 # | # # 6 |
|-----------------------|
7 | # 6 # | # # # | 2 8 # |
8 | # # # | 4 1 9 | # # 5 |
9 | # # # | # 8 # | # 7 9 |
|-----------------------|
Enter row,col,value to solve a square, or -1 to exit: -1
Exiting game immediately by user command
One Solution Board for this puzzle:
Current puzzle has 0 unsolved items
1 2 3 4 5 6 7 8 9
|-----------------------|
1 | 5 3 4 | 6 7 8 | 9 1 2 |
2 | 6 7 2 | 1 9 5 | 3 4 8 |
3 | 1 9 8 | 3 4 2 | 5 6 7 |
|-----------------------|
4 | 8 5 9 | 7 6 1 | 4 2 3 |
5 | 4 2 6 | 8 5 3 | 7 9 1 |
6 | 7 1 3 | 9 2 4 | 8 5 6 |
|-----------------------|
7 | 9 6 1 | 5 3 7 | 2 8 4 |
8 | 2 8 7 | 4 1 9 | 6 3 5 |
9 | 3 4 5 | 2 8 6 | 1 7 9 |
|-----------------------|
This program will read a puzzle from a text file saved to disk. This file has a specific format that must be followed, to ensure compatibility across all programs. A row in the input file corresponds to a row in the puzzle. Numeric values must be separated by spaces. Numbers that are part of the initial puzzle shown to the user must be preceded by an asterisks (*).
Here is the input file for the demo game shown previously:
*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
The user should be able to set entries in the game board by providing input in the form row,column,value to solve a specific square, or enter -1 to exit the program.
When the user has filled in all blank spaces in the game board, the program should determine if the current board is a valid solution and inform the user accordingly. Note that a Sudoku board could have multiple solutions! The solution provided with the initial puzzle may not be the only valid solution the user could provide. Thus, you should not simply compare the user's input to the original solution. Instead, you need to test the user's solution against the Sudoku rules previously described.
Requirements: Makefile
You must create a Makefile for your program (with the name Makefile). I should be able to enter the directory containing your code and type "make" to trigger compilation. If the Makefile is broken, or if I need to type anything else (or dig into the source code to figure out how to compile your program), your program will be returned to you with no grade assigned.
Use the following GCC options in your Makefile to set the compiler to a very picky mode:
- -std=c99 (Use the more modern C99 standard for the C language)
- -Wall and -Wextra (Turn on all warnings and extra warnings. By viewing and fixing issues that generate warnings, you will produce better, safer, C code)
- Warning: Don't delete the existing -c flag flag in the Makefile example from the previous lab! (It is essential to Makefile operation)
Configure your Makefile so that the name of your program binary is sudoku
Makefile grading nodes:
- If your program produces any warning during compilation (with these options), 5 points will be deducted.
- If your program doesn't compile on my virtual machine (and the error is such that your code wouldn't compile on any of your classmate's machines either!), zero points will be awarded.
Requirements: Memory Structures
Use a two-dimensional array of integers to store the current state of the puzzle. In this array, values of 1-9 represent user input, and a value of -1 represents a space with no current value. As the game is played, update this array based on user input.
You must use dynamic memory allocation to store this array. Remember to release dynamic memory before exiting! How can this be accomplished? In C, a two-dimensional array is simply an array of arrays, and you can allocate a single-dimensional array using malloc() or calloc(). This method is documented at the C FAQ site.
Tip: A demo program that uses dynamic memory allocation is provided for your reference. Note that it stores an array of integers, while you will want an array of characters. It can be compiled and run with the command:
unix> gcc dynamic_2d_array.c -std=c99 -o dynamic_2d_array
Requirements: Other
- I will compile and test your program in a Linux virtual machine that meets the installation process followed at the beginning of the semester. Don't relay on anything that wouldn't be in this default installation!
- You must implement the program in C
- You cannot use global variables.
- You must use both header files (.h) and source files (.c) where appropriate
- You must create a C structure for a datatype called sudoku that is saved in a header file. The following information (at a minimum) should be contained in this structure
- Pointer to the array containing the game state
- Pointer to the array containing the game solution (if your implementation requires this)
- Any additional variables used to track the state of the game (Dimensions of the board? Number of spaces remaining to be filled?)
- You must use functions with struct sudoku parameters. The actual division of the program into functions is up to you.
- All source files must be commented, including your name and email address.
- Feel free to use fancier text editors or IDEs that auto-indent your code and provide other convenience features. Just note, however, that you still must have a Makefile that allows your project to be compiled by typing make at the command line! (i.e. I will not install any IDEs on my computer, and still should be able to compile your project).
- Geany (fancy code text editor) - install via sudo apt-get install geany
- CodeBlocks (cross-platform IDE) - install via sudo apt-get install codeblocks
Requirements: Test Case
As part of this lab, you must submit a test case that demonstrates your program operation, including both valid and invalid human input. This test case has two components:
- A sample sudoku puzzle file. Examples puzzles should be easy to find online.
- A sample human input file that contains test values that a human would enter on the keyboard.
Here is an example of what a test case should look like. The sample sudoku puzzle file used in the demo above could be stored in the file suduko_puzzle.txt:
*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
Then, the sample human input file could be stored in the file human_input.txt. Note that this file is exactly what a person would type at the keyboard while running the program! This is the same input that was used to run the demo program output above.
sudoku_puzzle.txt 1,3,4 1,4,6 1,6,8 -1
The human input file can be run using Unix input redirection. Via this mechanism, your program can automatically read from this file instead of standard input (i.e. the keyboard) with no code changes required! The command to accomplish this is simple:
unix> ./sudoku < human_input.txt
Be sure to test that your test case functions in this manner.
Note: When you use input redirection, the input will not be echoed on the screen in the same way that keyboard input is echoed. It is OK if your program output looks a little strange in this mode. You don't need to adjust your program code to accomodate this.
Resources
- Need C programming resources? Visit the class Resources page
- The Instant Online Crossword Puzzle Maker may help you construct creative new sample puzzles for your program.
Getting Started
First, go to the directory that will hold your project.
unix> cd ~/bitbucket/2014_spring_ecpe170/lab04
Second, write your program in this directory! It's easy...
Here is one way to approach this lab in a step-by-step manner:
- Create a .c file for source code and .h file for header information. Put in a few lines of code - just enough to compile and produce some output.
- Create the Makefile - you'll need this to compile your program! Base this off of the advanced "Makefile-4" from the previous lab, but call it Makefile here.
- Test the Makefile
- Create a sudoku puzzle file (or copy the example above for a fast start)
- Add these files to your version control repository, and commit a new changeset. Be careful - don't include any of the temporary files your text editor might create! Those end in a tilde (~).
- Write file I/O code - Read in the crossword puzzle file and echo the output on the screen (for debugging)
- Test file I/O code
- Commit a new changeset to version control
- Write dynamic memory code - Save the crossword puzzle into dynamic array(s) created based on the demo program code. You might want multiple arrays, one for the puzzle itself, and another for all of the clues.
- Test dynamic memory code
- Commit a new changeset to version control
- Write the game play logic, prompting the user for input and comparing against the correct answer.
- Test game play logic
- Commit a new changeset to version control
- ... and so on ...
Submission
(1) Check all of your code (including Makefile and test cases) into version control, and push to BItBucket.
Want to test your submission to ensure you don't lose points due to version control errors? You could do a checkout of your repository into a different directory. Then, verify that all files are present and that you can still compile this copy of your project in its new location.
- Warning: Don't be sloppy and add too many files to version control! 5 points will be deducted if intermediary files (i.e. .o object files) end up in your repository.
- Warning: Don't be sloppy and add too few files to version control! Zero points will be awarded if missing source code or Makefiles prevent your program from compiling and running!
- Warning: Make sure your Makefile has the exact name "Makefile", so that I can compile your program simply by typing "Make" in the directory.
