Sudoku

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 be looking at only 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. A person or program solving the Sudoku puzzle should fill in the missing numbers without violating above mentioned rules. In the above given picture the numbers in red are filled by a solver.

Requirements

  1. You will invoke your Sudoku program from the command line with one command line argument and usage must be as follows:
    • ./sudoku create to create a random Sudoku puzzle
    • ./sudoku solve to solve a given Sudoku puzzle
  2. Sudoku creator must satisfy the following requirements:
    • Create a puzzle that has a unique solution
    • There must be at least 40 missing numbers in the generated puzzle
    • The puzzle must be randomized
    • The puzzle is printed to stdout
  3. Sudoku solver must satisfy the following requirements:
    • Be able to accept puzzles that have multiple solutions
    • Generate any one possible solution for the given puzzle
    • Must not change any given numbers in the puzzle
    • Should read the puzzle from stdin and print the solution to stdout.

Textual representation of the grid

Here is a suggested textual representation for your Sudoku grid to read from stdin and print to stdout.

  • The grid is represented as 9 lines of text
  • Each line contains 9 integers that range from 0 to 9, separated by a white space
  • 0 represents a missing number in the grid

If you wish to use a different textual representation please clearly specify it in your README.md and make sure to use the same format for both creator and solver.

Documentation

You need to provide the following documentation for your project:

  • DESIGN.md: This document should contain an overview of the algorithms that you use for your Sudoku creator and solver.
  • IMPLEMENTATION.md: This document should contain the details of how you implement the algorithms described in DESIGN.md.
  • TESTING.md: This document should contain the details of testing plan to test each module.
  • README.md: This document should contain the details about on how to use the solver and creator, and the format of their input and output.

Development

This is a group project, so you will make use of git to coordinate your development efforts. Follow the steps below to create a team repository:

  1. Accept the project assignment at this link of GitHub classroom.

  2. If you are the first team member accepting the assignment, please create a new team with your team name.

  3. If you are not the first member accepting this assignment, you should find your team name already listed. Choose your own team and click it to join the team. Make sure that you are selecting the correct team because you cannot change it later.

You may find this step-by-step guideline helpful.

Keep in mind that ALL of the components of your project (e.g., code, documentation, Makefiles, shell scripts, logs, presentation slides) should be maintained in your team git repository (except temporary files, object files, the executable, and libraries). 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.

We also recommend that each member works on a separate branch to minimize the conflict during concurrent development. Members should try to merge and integrate often so that potential integration problems can be identified and addressed early. Check out this guide on Git Feature Branch Flow.

Testing

A good testing plan is key to the success of any project. For the Sudoku project you are expected to perform the following testing:

  • Fuzz testing for Sudoku solver. Use your creator to generate n puzzles, where n is a command-line argument and test solver for these grids. Check the following:
    • The solution is valid, i.e, it follows Sudoku rules and doesn’t change already filled cells in the grids
    • The solver checks if each given puzzle has a unique solution (so you are also testing your creator n times).
    • Fuzz testing can be done using a bash script or a C program that takes n as command line argument.
  • Unit testing for both the creator and solver modules.
  • Regression testing is also recommended.

You must create a testing script for your project and also include the output of the testing script in your submission.

Code organization

There are two modules in this project, Sudoku solver and Sudoku creator. Your code should be organized in such a way that each module specific code should be in the respective directories. If required you must build a separate library of functions that are required by both modules.

Deliverables

Code & Documentation

For the first deliverable, your Design Specification, please name it as DESIGN.md and push it to your team’s GitHub repo by the due date (10pm on May 23).

For the final submission, be sure to tag your code in GitHub as projsubmit, include all of the files that make up your work for this Lab, including the usual README, describing anything “unusual” about how your solutions should be located, executed, and considered.

In your team repository you should have everything needed to build your project along with its documentation and results 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 version)
  • IMPLEMENTATION.md
  • TESTING.md
  • Testing shell scripts if any

On the due date, 10pm on May 31, your team repository should contain everything you want included for grading. We will extract the contents of your repository for final grading. You are also required to submit a peer assessment form.

All programs should compile without warnings or errors, and should execute without segmentation faults or memory leaks.

Final Presentation

On June 1, each team will give a 6-minute presentation on the project, including a live demo, the high-level algorithm design, testing strategy, code organization, work partition, and lessons learned.

Team Evaluations

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

Extra credits

Here are some options for extra credits.

  • Graphical UI: A possible extra credit is to 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.
  • Sudoku variants: Given the large number of Sudoku variants, your program can also implement other variants in addition to this 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.
  • Sudoku across machines: While we have not talked about socket programming, if you are interested in learning more about this topic, 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.

You are welcome to come up with your own interesting ideas to gain extra credits.