Info Lectures Assignments Staff Office Hours Hall of Fame Notes
Info Lectures Assignments Staff Office Hours Hall of Fame Notes

Sudoku

Assigned: 2020-03-11
Due Date: 2020-03-24 by 11:59PM U.S. Central Time

Goals

Assignment

Write a Sudoku solver.

The rubric can be found here.

Gradescope

You will need to submit your GitHub repository to Gradescope. There is a linter which is run on each submission; the results of the linter will be viewable by your code moderator when grading.

Getting Started

Get your copy of the assignment repo here: https://classroom.github.com/a/mezJ_Fea.

You will be implementing a program that loads in Sudoku puzzles, solves them, and then prints them out. If you're unfamiliar with Sudoku, you can read about it here.

Part 0: Streams and Operator Overloading

In this assignment, you'll have your first exposure to operator overloading in C++, specifically overloading the >> and << operators to support reading in data and sending out data, respectively. You may also find this and this tutorial to be helpful in figuring out what that looks like in the context of a class, though the example in the tutorial is not perfect.

You might already be familiar with this concept through std::cin and std::cout:

std::istream int_data = std::cin;  // Source of data is stdin

int num;
int_data >> num;
std::cout << "Your number is: " << num << std::endl;

Note: reassigning int_data = std::cin is a bit contrived for this example. It's just to demonstrate that we're getting data from a generic std::istream, and the fact that the source of data is specifically std::cin doesn't matter in order for >> to work.

We would like to be able to do the following:

std::istream& a_single_unsolved_puzzle = /* Some source of data from somewhere */;

YourPuzzleClass puzzle;
a_single_unsolved_puzzle >> puzzle;  // Initialize the puzzle
std::cout << puzzle << std::endl;  // Print the solved puzzle

Note: YourPuzzleClass is a bad name for a class; it's just for illustration purposes.

Here is a more concrete example:

#include <fstream>
#include <string>

// ...

std::ifstream puzzle_stream("data/simple.spf");
if (puzzle_stream.fail()) {
  // Handle read error.
}

// ...

std::istream& input_stream = puzzle_stream;

std::string tag;
input_stream >> tag;

// ...

Note: "data/simple.spf" shouldn't be hard-coded as shown above in your code; it's just for illustration purposes. Also, your code probably won't look quite like this. This example just shows how to read from a file.

You will need to create a dedicated class for the purpose of storing a single Sudoku game, and you will need to overload std::istream &operator>> and std::ostream &operator<< to support reading in a single puzzle's worth of data and sending out a solved puzzle. If you've done it correctly, you should even be able to support sending/receiving data to/from arbitrary sources, like network connections, although that's not a requirement for this assignment.

Part 1: The Sudoku Puzzle Format (.spf)

We are using a text-based file format for representing game(s) of Sudoku. A valid .spf file looks like this:

Here's a full example of a valid .spf file containing two Sudoku puzzles:

#spf1.0
85___24__72______9__4_________1_7__23_5___9___4___________8__7__17__________36_4_
___8_5____3__6___7_9___38___4795_3______71_9____2__5__1____248___9____5______6___

In your program, you should allow the user to specify the location of a local file using command-line arguments, and then you should:

Once you've read in the data from the SPF file, you should use your Sudoku puzzle class to solve each puzzle in the file.

Design hint: the code that loads and processes an entire .spf file doesn't necessarily have to live in the same class that represents a single Sudoku puzzle. Your Sudoku puzzle class only needs to be capable of being initialized with data for a single Sudoku puzzle, not the entire .spf file!

Project Structure

Your data files should go in the data/ folder or the test/data folder depending on whether you are running the main application or the tests. In either case, you should be able to access the file with the prefix data/<your-file>.spf.

The main function is located in apps/solve.cc. To this main function, select the configuration with the target solve next to the green Run button in the top right. The rest of the project is structured similarly to the last assignment. Feel free to add or modify files. Also note that any files that are in include/sudoku are visible to anyone, so only put the files/methods/data/etc. you want exposed in that folder.

Part 2: Solving Sudoku

You are not required to implement any specific Sudoku-solving algorithm. Feel free to look on the Internet for various strategies for solving Sudoku, or invent your own — just remember our course policies on citing outside code.

You are advised to not spend too much time on this part of the assignment. Don't worry about efficiency; pick an algorithm that is simple and easy to understand and implement. You might find this article on Wikipedia helpful. Here is another guide on solving Sudoku puzzles.

If that wasn't enough, below is a small guide on solving Sudoku puzzles.

How to solve a Sudoku puzzle Solving a Sudoku puzzle may seem like a daunting task at first, so we’re providing some guidance.

A naive solution would be to try every possible way to fill in the squares:

SolvePuzzle() {
  for (every possible way to fill in the blank squares) {
    if (filled-in board is valid) {
      return filled-in board
    }
  }

  return IMPOSSIBLE
}

However, the number of ways to do this is 9^(# of empty squares), which is way too large. In order to speed this up, we should stop exploring a branch as soon as we attempt to fill in a number which is incompatible (i.e. it creates a duplicate in a row, column, or 3x3 square):

SolvePuzzle() {
  // this prunes invalid branches as soon as possible
  if (board is not valid) {
    return IMPOSSIBLE
  }

  if (board is valid and board is completely filled in) {
    return board
  }

  find an empty square

  for (digit in {1, ..., 9}) {
    fill in the empty square with digit
    recursively call SolvePuzzle on the modified board

    if (modified board has a solution) {
      return solution to modified board
    }
  }

  return IMPOSSIBLE;
}

Thus, your primary focus should be to implement a function that checks if a board is valid. Make sure that you implement this functionality in a modular fashion. You’ll probably notice that a lot of the same concepts which apply to checking a TicTacToe board also apply to checking a Sudoku board. Also, make sure you are using references where you can: you don't want to make a bunch of copies of the board when you don't need to. This will improve the speed of the algorithm.

If a given Sudoku puzzle is unsolvable, you should report that somehow (returning the string "Unsolvable", or returning the original unsolved puzzle would be sufficient).

Other Info

You may assume that every Sudoku game in an SPF file will be a standard 9x9 board, but your code should still be extensible enough to support different board sizes with only minor changes. Hexadecimal Sudoku (16x16) is a thing, and maybe one day we will come out with an SPF2.0 that supports it.

Some standard library classes you might find helpful in your code and tests:

C++ I/O streams are very similar to Java I/O streams.

Grading and Deliverables