Assignments Office Hours Hall of Fame Notes
Assignments Office Hours Hall of Fame Notes

Streamlined Sudoku

Assigned: 2019-10-16
Due Date: 2019-10-22 by 11:59PM U.S. Central Time

The greatest challenge to any thinker is stating the problem in a way that will allow a solution.

— attributed to Bertrand Russell

Now that you've gotten your feet wet with a bit of C++, your managers want you to up the ante, to forge your own journey from scratch.

Minisoft has just secured a deal with a company called Macrohard to produce a Sudoku-solver. Macrohard wants to ship it with their latest operating system, Doors 11™, so they need this solver to work with their proprietary text-based representation of Sudoku games. You'll have to follow their standards if you want to succeed!

Goals

Assignment Spec

WARNING: This assignment is time-consuming and introduces new C++ concepts that may be tough to grasp at first. Give yourself adequate time to complete this assignment!

Getting Started

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

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 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 n;
int_data >> n;
std::cout << "Your number is: " << n << 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.

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)

Macrohard uses 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 (either by using something like std::cin or command-line arguments, your choice,) 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!

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.

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 Macrohard will come out with an SPF2.0 that supports it.

Some standard library classes you might find helpful (but do not have to use!) in your code and tests:

Grading and Deliverables