Due on Sunday, November 14 at 10pm

For this project, you will work as a team to write a set of C programs to create and solve Sudoku puzzles according to the rules and requirements. In addition, you will write a set of programs (C and/or bash) to test individual parts and the entirety of the software.

Getting Started

  1. One member from each team should start by accepting the assignment and “Create a Team” using the appropriate team name.
  2. Other group members can then join the appropriate team on the assignment invitation page.
  3. Clone the new project to a Git repository on your Unix account as you have done in previous labs.
  4. Now you are ready to go!

Background

Sudoku is well known logic puzzle where numbers between 1 and 9 are placed on a 9x9 grid of cells. The placement of numbers has to follow certain rules. There are many variations of Sudoku, but for this project you will start with the most common version of Sudoku. In this version, the 9x9 grid is further divided into 9 square shaped regions of size 3x3 as shown below.

Rules

In a valid Sudoku grid, every number from 1 to 9 must appear:

  • Only once in every row
  • Only once in every column
  • Only once in every 3x3 squared region

The puzzle is presented as a 9x9 valid grid with some numbers missing. The objective is for a person or program solving the Sudoku puzzle to fill in missing numbers without violating any of the aforementioned rules. For example, in the figure above, the numbers in red are filled by the solver (i.e., a person or program).

Base Requirements

Your design and implementation must follow the below requirements.

The Sudoku Puzzle shall:

  1. execute from the command line with usage syntax ./sudoku mode difficulty, where
    • "mode" is a string input set to create or solve
    • "difficulty" is a string input set to easy or hard
  2. validate it received the appropriate number and type of arguments according to the usage syntax
  3. create or solve a puzzle according to the mode and difficulty input entered by the user

The create mode shall:

  1. create a randomized sudoku puzzle that has a unique solution
  2. allow for two levels of difficulty in the generated puzzle with,
    • easy including 37 given numbers and 44 missing numbers
    • hard including 25 given numbers and 56 missing numbers
  3. print the created puzzle to stdout

The solve mode shall:

  1. read puzzles from stdin including puzzles presented in the:
    • customized format used by the create mode, and
    • “standard format” with integers in each row are separated by a single space (example below)
  2. accept Sudoku puzzles with different difficulty levels.
    • Note: The difficulty argument may be omitted in the solve mode as the goal is simply to solve a valid puzzle
  3. check that it received a valid puzzle of appropriate size (e.g. 9x9) with a minimum of 25 given numbers (i.e., hard) which do not break sudoku rules
  4. not change any of the given numbers in a received puzzle
  5. generate a solution for the received puzzle
  6. print the solution to stdout in the format received

Visual representation

As a suggestion, the Sudoku puzzle can be built to use textual representation with characters such as | and __ to build the grid, white spaces as needed, and integers 0 to 9 to represent numbers in the puzzle with 0 representing a missing number. If you wish to use this or a different textual representation, the choice for representation should be clearly specified in the DESIGN.md and the same format must be used for both the create mode and the solve mode.

Below is an example of the “standard format” in which every number in the puzzle is separated by a single space and 0s are used to represent missing numbers.

Testing

A good testing plan is key to the success of any project. For the Sudoku project, your testing plan shall include:

  • Fuzz testing: This can be done using a bash script or C program. Consider using the create mode to generate n puzzles, where n is a command-line argument. Then, testing should check that:
    • the solution generated with the solve mode is valid, i.e, it follows Sudoku rules and does not change any of the starting numbers given in the grids
    • each created puzzle generated in the create mode has a unique solution
  • Unit testing for all modules including those for creating and solving a Sudoku puzzle

  • Regression testing is also recommended.

You must create testing programs or scripts for your project and also include the output from testing in your submission.

Documentation

You need to provide the following documentation for your project:

  • README.md: This document should contain details about:
    • where things are located in your repository
    • how to use the entire program in its different modes and difficulty levels
    • how the program can be executed
    • the level of functionality that was implemented
    • anything “unusual” and/or particularly “amazing” about the design, implementation, and testing.
  • DESIGN.md: This document should contain an overview of the visual representation and algorithms used for creating and solving Sudoku puzzles.
  • IMPLEMENTATION.md: This document should contain language-specific details for implementation of the chosen visual representation and algorithms described in the DESIGN.md.
  • TESTING.md: This document should contain descriptions of:
    • all the testing implemented
    • the individual time and average time across 3 - 5 runs for the developed program to solve Sudoku puzzles with difficulty levels easy and hard

Code organization

There are at minimum two modules in this project, the “Sudoku creator” and “Sudoku solver”. Hence, the code should be organized in such a way that each module’s specific code is in the respective directory. In addition, there should be a separate library of functions that are common across modules.

Github & Workflow

ALL of the components of your project (e.g., code, documentation, Makefiles, shell scripts, logs, and presentation slides) should be maintained in your team git repository (except temporary files, object files, executables, and archives/libraries). Make certain that no temporary file is included in your repository.

Note: We will check the git commit logs to see how the team has been using git to track the project development, as well as which team members contributed actively and substantially to the project. In that spirit, do not have a few big commits only towards the deadline. Keep pushing new edits to GitHub as you are developing the project.

GitHub issues offer a nice tool for project management. Do make use of it for task assignment and tracking within the group.

It is also recommended that each member works on a separate branch to minimize conflicts during concurrent development. Subsequently, it is important that team members merge and integrate often to minimize integration problems and address any problems early on in the process. Check out this guide on Git Feature Branch Flow.

Code & Documentation

In your team repository, you should have everything needed to build your project along with its documentation and output files or logs. These files should be in an intuitive directory structure and include:

  • Source code (.c, .h)
  • Makefile(s)
  • Top-level README explaining what & where everything is
  • DESIGN.md (updated since the first draft)
  • IMPLEMENTATION.md (updated since the first draft)
  • TESTING.md
  • Testing shell scripts (if any)
  • testing.out

Of course, it is the expectation that all programs should compile without warnings or errors, and should execute without segmentation faults or memory leaks.

Project Timeline

  1. The project is being assigned on November 1, 2021.

  2. You are expected to meet with your team members starting on November 2, 2021, plan your project, and begin your design documents.

  3. Come to the classroom during lecture time and work with your team members. Learning fellows and the professor will be around. Note: we probably won’t have time to debug your code, rather we can give you suggestions on the design.

  4. You must arrange at least one meeting per week (i.e., two total) with your team shepherds to discuss the design and task breakdown in the weeks of November 1 and November 8, 2021.

  5. Below are a list of milestones and due dates that you should work toward:

    • November 3 at 10pm: A first draft of the Design Specification (i.e., DESIGN.md). This draft should be pushed to your team’s GitHub repo with the commit message "design draft".
    • November 8 at 10pm: A first draft of the Implementation Specification (i.e., IMPLEMENTATION.md). This draft should be pushed to your team’s GitHub repo with the commit message "implementation draft".
    • November 14 at 10pm: The final submission for the project. This commit should be tagged projsubmit.

NOTE: Extensions and late submissions of the project are NOT allowed. There is no exception. Any submission after 10pm on the final due date will receive an immediate late penality. Any submission after the due date will not be accepted.

Final Presentation

On November 15 & 16, each team will give a 7-minute presentation on the project, including a live demo, the high-level algorithm design, testing strategy, code organization, work partition, and lessons learned. This is a chance to showcase your hard work, all you have learned, and even go above and beyond! Find ways to make your experience and presentation memorable.

Team Evaluations

Each team member is required to complete a brief evaluation form that asks about participation, contribution, distribution of work, etc. within their team. Completing and submitting this assessment is required as part of the 5% project participation grade.

Important: Every team member will initially be assigned the same group project grade, however, each student’s final project grade can be adjusted by the instructor to reflect that individual’s contribution to the team and engagement through the project phase. This decision is strictly at the discretion of the course instructor and the CS50 teaching team.

Choose your topping

After completion of the base requirements, each team has the option to choose one of the outlined “topping options” to implement as a part of their project.

  1. Graphical UI: Implement and show the game progress using a graphics software.
    • Your graphics component need not run on Linux servers.
    • It doesn’t have to be written in C.
    • You can dump your sequence of moves to a file and show the animation using a program independent of your Sudoku project. That program can be in any programming language of your choice.
  2. Sudoku variants: Given the large number of Sudoku variants, your program can implement another variant in addition to the basic 9x9 grid form. The user can choose the type of Sudoku to create or solve. As an example, a 3D Sudoku can be in the form of a 9x9x9 cube, where numbers need to be filled in this cube satisfying the Sudoku rules.
  3. Sudoku across machines: While we have not talked about socket programming you are invited to review the lecture notes on this topic and you can actually apply socket programming to realize a client-server model for your Sudoku program. The Sudoku creator runs at one server and Sudoku solver runs at another. The solver requests a Sudoku challenge from the creator and then solves it. To implement it, you will need to think about how to send the Sudoku puzzle using sockets.

Extra credit: You can select a second topping for extra credit or come up with your own interesting ideas to expand the base project + your one topping to gain extra credit points.

Grading

Grades will be calculated as the sum of several factors, adding up to a percentage that will be applied to the maximum number of points available for the project.

Extra credit will be given to the team(s) with the fastest times on creating and solving a Sudoku puzzle with the difficulty level of hard.

Grade Target 3-person Team 2-person Team
Design review, progress check with learning fellow and/or TA shepherd 5 5
Documentation and testing 15 15
Final product quality, including design, code, style, visual representation, and use of git 40 40
Functionality of create and solve modes with difficulty level easy 25 30
Solving with difficulty level hard within “reasonable” time 5 5
Successful implementation of one “topping” option 5 0
Project demo and presentation 5 5
Total 100 100
  Extra Credit
To the team(s) with the fastest solve times on difficulty level hard 5
To the team(s) that implement a second “topping” option from the options listed above or implement other interesting ideas that go above and beyond 5

Meet Our Teams!

Team (present order#) Members Learning Fellow TA Shepherd
Wonam (1) Sam Rothschild, William Kalikman, Jonah Weinbaum Kysen Annabel
Team5 (2) Dylan Bienstock, Salifyanji Namwila, Veronica Quidore Samuel Annabel
Group 9 (3) Khadijah Bell, Will Schlachtenhaufen, Gabriel Asher Samuel Chahak
The C Crew (4) Saksham Arora, Sayuri Tais Miyamoto Magnabosco, Brody Thompson William Amittai
Bug Exterminators (5) Alan Sun, Jinxu Guo Kysen Amittai
indifferent (6) Ethan Chen, Bansharee Ireen, Jeffrey Jiang William Elorm
The C Turtles (7) Noah Jerris, Brian Yu, Andrea Robang William Elorm
gitwithit (8) Holland Blumer, Patrick Howard Samuel Chahak