Problem: Sudoku

Questions? Feel free to head to CS50 on Reddit, CS50 on StackExchange, the #cs50ap channel on CS50x Slack (after signing up), or the CS50 Facebook group.

tl;dr

Implement the game of Sudoku, per the below:

$ ./sudoku n00b

Academic Honesty

This course’s philosophy on academic honesty is best stated as "be reasonable." The course recognizes that interactions with classmates and others can facilitate mastery of the course’s material. However, there remains a line between enlisting the help of another and submitting the work of another. This policy characterizes both sides of that line.

The essence of all work that you submit to this course must be your own. Collaboration on problems is not permitted (unless explicitly stated otherwise) except to the extent that you may ask classmates and others for help so long as that help does not reduce to another doing your work for you. Generally speaking, when asking for help, you may show your code or writing to others, but you may not view theirs, so long as you and they respect this policy’s other constraints. Collaboration on quizzes and tests is not permitted at all. Collaboration on the final project is permitted to the extent prescribed by its specification.

Below are rules of thumb that (inexhaustively) characterize acts that the course considers reasonable and not reasonable. If in doubt as to whether some act is reasonable, do not commit it until you solicit and receive approval in writing from your instructor. If a violation of this policy is suspected and confirmed, your instructor reserves the right to impose local sanctions on top of any disciplinary outcome that may include an unsatisfactory or failing grade for work submitted or for the course itself.

Reasonable

  • Communicating with classmates about problems in English (or some other spoken language).

  • Discussing the course’s material with others in order to understand it better.

  • Helping a classmate identify a bug in his or her code, such as by viewing, compiling, or running his or her code, even on your own computer.

  • Incorporating snippets of code that you find online or elsewhere into your own code, provided that those snippets are not themselves solutions to assigned problems and that you cite the snippets' origins.

  • Reviewing past years' quizzes, tests, and solutions thereto.

  • Sending or showing code that you’ve written to someone, possibly a classmate, so that he or she might help you identify and fix a bug.

  • Sharing snippets of your own solutions to problems online so that others might help you identify and fix a bug or other issue.

  • Turning to the web or elsewhere for instruction beyond the course’s own, for references, and for solutions to technical difficulties, but not for outright solutions to problems or your own final project.

  • Whiteboarding solutions to problems with others using diagrams or pseudocode but not actual code.

  • Working with (and even paying) a tutor to help you with the course, provided the tutor does not do your work for you.

Not Reasonable

  • Accessing a solution to some problem prior to (re-)submitting your own.

  • Asking a classmate to see his or her solution to a problem before (re-)submitting your own.

  • Decompiling, deobfuscating, or disassembling the staff’s solutions to problems.

  • Failing to cite (as with comments) the origins of code, writing, or techniques that you discover outside of the course’s own lessons and integrate into your own work, even while respecting this policy’s other constraints.

  • Giving or showing to a classmate a solution to a problem when it is he or she, and not you, who is struggling to solve it.

  • Looking at another individual’s work during a quiz or test.

  • Paying or offering to pay an individual for work that you may submit as (part of) your own.

  • Providing or making available solutions to problems to individuals who might take this course in the future.

  • Searching for, soliciting, or viewing a quiz’s questions or answers prior to taking the quiz.

  • Searching for or soliciting outright solutions to problems online or elsewhere.

  • Splitting a problem’s workload with another individual and combining your work (unless explicitly authorized by the problem itself).

  • Submitting (after possibly modifying) the work of another individual beyond allowed snippets.

  • Submitting the same or similar work to this course that you have submitted or will submit to another.

  • Using resources during a quiz beyond those explicitly allowed in the quiz’s instructions.

  • Viewing another’s solution to a problem and basing your own solution on it.

Assessment

Your work on this problem set will be evaluated along four axes primarily.

Scope

To what extent does your code implement the features required by our specification?

Correctness

To what extent is your code consistent with our specifications and free of bugs?

Design

To what extent is your code written well (i.e., clearly, efficiently, elegantly, and/or logically)?

Style

To what extent is your code readable (i.e., commented and indented with variables aptly named)?

To obtain a passing grade in this course, all students must ordinarily submit all assigned problems unless granted an exception in writing by the instructor.

Getting Started

First, log into cs50.io and execute

update50

within a terminal window to make sure your workspace is up-to-date.

Then, create a new directory inside of your workspace called chapter4 (Remember how?) and navigate inside. Once there, obtain a copy of this problem’s distro by typing:

wget http://docs.cs50.net/2017/ap/problems/sudoku/sudoku.zip

Unzip the ZIP file (remember how?) and then delete the ZIP file from your chapter4 directory. Navigate into your newly-created sudoku directory and type:

ls

You should see that your directory contains six files.

Makefile  debug.bin  l33t.bin  n00b.bin  sudoku.c  sudoku.h

The numbers must be single

Much like the Game of Fifteen, Sudoku is a game of logic involving numbers. But it’s much more interesting. Consider the puzzle below:

Sudoku

The object of Sudoku is to fill this 9x9 grid in such a way that each column, each row, and each of the nine 3x3 boxes therein contain each of the numbers 1 through 9 exactly once. A whole bunch of strategies exist, but the general idea is to figure out iteratively what numbers could go where.

For instance, let’s home in on one of the 3x3 boxes that already has a lot of numbers and work the ol' process of elimination. Consider the box in the middle, highlighted below.

Sudoku

Let’s see, that box already has a 1, a 2, but no 3. Where could we put 3? Well, 3 can’t go in that box’s bottom row, since the box to the right already has a 3 in that row. And 3 can’t go on either side of the 7, since the box to the left already has a 3 in that row. Aha! It must be, then, that 3 belongs in that box’s top row, in which case there’s only one place to put it! And so we fill in that spot with a 3, per the below.

Sudoku

Let’s try another trick now. Rather than figure out where a number can go, let’s figure out where a number can’t go! Let’s home in on 9. Highlighted in gray now are all of the spots a 9 cannot go, either because there’s already another number there or because there’s already a 9 in the highlighted row, column, or box, per the below.

Sudoku

Well, look at that! Looks like we’ve found a home for 9 within that box in the middle because there’s only one place it can possibly go, per the below.

Sudoku

Lather, rinse, and repeat these sorts of tricks enough times, and (assuming no PEBKAC[1]) we’ll end up with the solution below.

Sudoku

If still not quite clear on how the game is played, feel free to turn to Wikipedia. And if interested for your own edification in the mathematics and algorithmics behind the game, you might also find these articles of interest:

Killing time

Now the real fun begins. You’re about to implement (most of) Sudoku in C.

Much like we’ve provided you with some code for prior games you’ve been tasked with implementing, so too have we provided a skeleton for Sudoku. Unlike those past games, though, this problem introduces a library called "ncurses" that will provide your implementation of Sudoku with a rudimentary GUI. To be sure, your program won’t look like OS X or Windows, but it will look a bit sexier than, say, the Game of Fifteen! Not only does ncurses trivialize adding colors into a program (and even dialogs and menus), it also allows you to treat your terminal window as a grid of characters (char), any one of which can be updated without affecting the others. That sort of feature is perfect for a game like Sudoku, as you’ll be able to add numbers to the game’s board one at a time without having to re-generate the whole screen after each move.

Historically, a typical terminal window was 80 characters wide by 24 characters tall (i.e., 80x24). Odds are, your terminal window in CS50 IDE isn’t that size, but there’s a way to ensure that it is that size, if you find yourself in a historical mood. At the prompt, type

watch tput lines

Your prompt should change, telling you that every 2 seconds it is updating what it perceives as the number of lines in your terminal window. If you drag your window up and down, you should see the number a few lines down update. When it says "24", you can press ctrl+C to quit the tput program. Similarly, you can type

watch tput cols

to figure out how many columns your terminal window has. When you stretch or shrink your window and it reports "80", you can press ctrl+C to quit.

Anyway, why this foray into terminal size? It turns out that ncurses individually addresses each character in your terminal window by way of (y, x) coordinates[2], whereby (0, 0) refers to your terminal window’s top-left corner, (0, 79) refers to your window’s top-right corner, (23, 0) refers to the bottom-left corner, and (23, 79) refers to the bottom-right corner.

Even if your window boasts dimensions smaller or larger than these, the idea is the same. When it comes time to fill in a blank with respect to Sudoku, you’ll simply update the char at some (y, x) coordinate.

Now, let’s talk about that skeleton. Basically, we’ve implemented the aesthetics for the game so that you can focus on the more interesting parts: the game’s features. In fact, we’ve written the code (and comments) in such a way that you should be able to learn quite a bit about ncurses and more simply by reading our code.

Because this game is meant to be more sophisticated (and fun) than previous ones, you’ll also find that we’ve given you quite a bit more code this time. Don’t freak out, but it’s just over 600 lines. But know now that none of it is all that complex. In fact, if you look at each of the functions in isolation, you’ll likely find each pretty straightforward. What’s neat is that when you combine so many building blocks, you get some pretty compelling results. In fact, let’s take a look.

Navigate to your ~/workspace/chapter4/sudoku directory and execute the increasingly familiar command below:

make

You should find a brand new executable called sudoku in your current working directory. Go ahead and run it by typing

./sudoku

You won’t yet see our skeleton but instead the game’s usage:

Usage: sudoku n00b|l33t [#]

Not only does our skeleton support two levels of game play (n00b[3] and l33t[4]), it also comes with 1024 different boards for each level. Ultimately, if you’d like to play a pseudorandomly chosen n00b board, you’ll want to execute just:[5]

./sudoku n00b

Per the menu along the game’s bottom, you can then hit Q to quit. Now, if you want to play a specific board, you can load it up manually. In fact, go ahead and execute

./sudoku n00b 42

to fire up our skeleton with n00b #42. You should see basically the below.

Sudoku

Notice how, for clarity’s sake, we use periods for blanks; underneath the hood, we represent each of those same blanks with 0 (an actual int). So this is all pretty neat, but this skeleton lacks that personal touch (not to mention support for basic things like moving the cursor). What do work right out of the box are [N]ew Game, [R]estart Game, and [Q]uit Game. Go ahead and hit Q to quit.

Now open up sudoku.h and play with all those mentions of color. It turns out that ncurses deals with colors in pairs, whereby characters have both a foreground color and a background color. By default, characters' foregrounds are white and backgrounds are black. But clearly we’ve overridden those defaults for our skeleton’s borders and logo. For now, you’ll want to leave that enum alone, but feel free to change the values of any constants whose names begin with FG_ or BG_. Here are the colors that ncurses comes with:

  • COLOR_BLACK

  • COLOR_RED

  • COLOR_GREEN

  • COLOR_YELLOW [6]

  • COLOR_BLUE

  • COLOR_MAGENTA

  • COLOR_CYAN

  • COLOR_WHITE

You will, of course, need to recompile your game to see any colorful changes. Not all that hard to make things look pretty hideous, eh?

In fact, for best results when working with ncurses you may find it convenient to change the theme of your CS50 IDE if you haven’t already. By default, your terminal window has a blue background because your default theme is "Cloud9 Day". You can change the theme of your workspace at any time, however, by going to View > Themes and then choosing from the slate of available options. One easy switch is to use "Cloud9 Night" from that list. To be clear, you don’t have to do this, but because the theme might override your ncurses color choices, a darker theme from the get-go might be your safest bet.

Now let’s take a look at, say, n00b.bin, but not in the matter to which we’ve become accustomed. Rather, execute the command below.

xxd -b n00b.bin

Wow! A whole lot of numbers probably flew past. You’ve just looked at the contents of a binary file. Inside of that file are a whole bunch of 32-bit ints, 1024 * 81 = 82,944 of them, in fact, as that file contains 1024 n00b boards, each of which includes 81 numbers and/or blanks (for a 9x9 grid). Similarly does l33t.bin contain 1024 l33t boards.

Now that you’ve run sudoku at least once, you might also have noticed a file called log.txt that wasn’t there when you first copied our code over. You’re welcome to examine it, but you needn’t pay much attention; it’s generated by our framework for testing purposes.

Alright, we’re flying through those files. One to go. Open up sudoku.c.

Curses, ncurses!

Grr…​ there’s a lot of code in that one.

The best way to tackle this problem is to start by understanding this file. We’ll get you started. First, take note of one of the file’s first lines:

#define CTRL(x) ((x) & ~0140)

Just as you can define what we know as constants with #define, you can also define "macros," short snippets of code that behave a little bit like functions but without the overhead (e.g., stack frames) of an actual function call. This particular macro will enable you to detect control characters from users, if you so desire. Out of the box, our skeleton already understands ctrl+L, a keystroke meant to induce a redrawing of the game’s screen.

Now take a look at the struct called g just below that macro. Inside this particular struct is a whole bunch of fields, each of which can be accessed using the dot operator (e.g., g.level). Because g is a global variable, so are those fields effectively global as well. Truth be told, we could have defined those fields as global variables themselves without using a struct, but because there are so many, all related to this game, we decided to encapsulate them.

Next notice our skeleton’s prototypes…​ but more on those later.

Now dive into main. Best, though, that we not hold your hand too much through this one. We daresay that learning to program is as much about writing your own programs as it is about reading others', particularly when your assignment (or job!) is to build upon the latter. Odds are you’ll thank us some day for actually having written comments in ours! There’s a lot going on in main, but do read each and every line. After all, it’s the function that drives this whole program. And because our other functions' names rather say what those functions do, you can probably read main from top to bottom and have a pretty good idea of how the program currently works. Notice, in particular, the do-while loop and switch with which the game listens for user input.

Notice, too, that we’ve embedded a secret debug level that has 9 boards. You should find that those boards, because they’re solvable so quickly, facilitate debugging.

Now let’s have a look at those other functions. A good one to start with is startup, which gets ncurses going. Notice how it calls a bunch of other functions that appear to configure ncurses. Although we’ve commented each call, you might want to pull up the man page for some or all of those functions, if only to get all the more comfortable with ncurses.

Next, have a look at load_board, which loads a n00b or l33t (or debug) board from disk, depending on the value, if any, in argv[2]. You needn’t understand how fopen, fseek, fread, or fclose work yet, though you soon will! What this function ultimately does is load 81 ints into the global array called g.board.

Now peek at draw_borders. Mostly we want you to poke around here because it demonstrates how to use ncurses. Notice, for instance, that the function first determines your terminal window’s dimensions using a macro called getmaxyx, a function built-in to ncurses. It eventually uses those maxima to fill your window’s topmost and bottommost rows with color and instructions. Notice how the function enables color, specifically turning on the COLOR_PAIR attribute that we called PAIR_BORDER back in sudoku.h. It then proceeds to draw the game’s borders by moving, left to right, coordinate to coordinate, laying down blank spaces, and doing some other neat things (like centering your TITLE and AUTHOR in the top order and planting instructions at the bottom) before shutting color back off.

Now take a look at draw_grid, which lays down the ASCII art representing our game board. Similarly does it first determine your window’s dimensions, then uses those values to determine coordinates for the grid’s top left corner[7]. Rather then generate the grid character by character, this function instead lays down whole strings (using mvaddstr, another ncurses function) at once, repeatedly inside of a for loop. Then it also reminds the user of the level and board they are playing, and so we constructed a string on the fly with sprintf, then added it to the screen with a final call to mvaddstr.

Incidentally, we’ve mentioned a few of them now, but if curious to learn more about all these ncurses functions, man is your friend.

Zip on over to draw_logo and draw_numbers. Based on the above descriptions of functions, these should be relatively easy to follow. Why all the arithmetic in draw_numbers, though? Admittedly, it took a bit of trial and error to get right on our part, but it simply ensures that numbers end up where they should on the screen and not on top of the grid’s own lines.

Glance at show_banner and hide_banner. Both pretty simple, these functions exist so that you can show (and hide) messages to users. In fact, while using ncurses, do not use printf as well. Bad things will happen.

Speaking of show_banner, why don’t we also peek at show_cursor. Recall that functions like mvaddch and mvaddstr end up moving your cursor in order to add text to the screen. That’s kind of annoying if you want to use that same cursor to play the actual game. And so it is necessary to remember where the cursor should be with respect to the grid. Glance back at that global called g and you’ll see how we do it. This show_cursor function relies on that struct to return the cursor to where it should be after screen updates.

You needn’t worry about handle_signal. That just leaves log_move, redraw_all, restart_game and shutdown. We think you can handle those!

So that’s everything. Not bad for about 600 lines.

The digits one through nine

The funny thing is that none of the 600 or so lines actually implements Sudoku. But that’s where you come in! Your challenge is to implement a few features, among them support for actual game play.

Before you do, though, a few questions for you. Create a file called questions.txt in ~/workspace/chapter4/sudoku and record in it your answers to the below:

  1. Notice that main calls strcmp. What does it mean if strcmp, when passed two strings as arguments, returns 0?

  2. How would you rewrite the line below, excerpted from main, using only if and else?

int max = (strcmp(g.level, "debug") == 0) ? 9 : 1024;
  1. Under what circumstances might the call to sscanf below, excerpted from main, return 2 instead of 1?

sscanf(argv[2], " %d %c", &g.number, &c)
  1. What fields in g represent the coordinates at which the user’s cursor belongs?

  2. What function (that we wrote) can you call to make the cursor actually appear at those coordinates? (Hint: we told you a little while back!)

  3. Around what line number in main could you add additional case statements to handle keystrokes besides N, R, and ctrl-L?

  4. Most n00b and l33t boards have lots of blanks. How many blanks are in debug #1? Debug #2? Debug #9? More than any other problem to date, this problem is about design. Do give some thought about how best to implement some feature, given the game’s framework. With that said, you are welcome to change most any aspect of code if the change fits your design better. However, what you must not change is anything with respect to logging, including log_move.

Required Features

  • At the moment, the cursor is "stuck" in the board’s center. Enable users to move that cursor up, down, left, and right by way of their keyboard’s arrow keys. You’re welcome to support other keys for movement as well, but you must support KEY_UP, KEY_DOWN, KEY_LEFT, and KEY_RIGHT, constants that represent the characters fed to ncurses' getch function when arrow keys are pressed. (See the man page for getch for even more constants.) You should only allow the user to move his or her cursor to coordinates where there are actual numbers or blanks (i.e., the cursor should "hop over" one-character lateral gaps between cells as well as the innermost crossbars that make up the grid’s lines), but you should find that the arithmetic already implemented in show_cursor helps with that! Even though you might be tempted to make the cursor hop over numbers that came with the board, resist the temptation; allow the cursor to be in any one of those 81 cells.

  • Enable the cursor to also "wrap around" from the top row to the bottom, bottom to top, left to right, or right to left if the user presses KEY_UP, KEY_DOWN, KEY_LEFT, or KEY_RIGHT, respectively, too many times.

  • Enable the user to replace any blank with a number by moving his or her cursor over that blank and then hitting a number from 1 to 9.

  • Enable the user to change a number that they already inputted back to a blank by hitting any of 0, a period, KEY_BACKSPACE, or KEY_DC or to some other number from 1 to 9 by hitting that number.[8] You needn’t (yet) prevent the user from altering numbers that "came with" the board.

Just implementing these two features (movements and number entry) will allow users to play (and win!) the game of Sudoku…​ but even if they fill in all the numbers correctly, they won’t know it quite yet! We’ll complete the implementation of Sudoku in the next portion of this problem.

The student becomes the teacher

Now it’s time to augment the game by adding the following additional features:

  • Do not allow the user to alter numbers that "came with" the board. (Note that in the first part of the problem, this restriction was not enforced!)

  • Any time the user changes the board, check whether the game has been won. If so, display a congratulatory banner, turn all 81 numbers green, and prevent the user from changing the board further.

  • Any time the user changes the board, check whether they have inserted a number where it does not belong at the moment (because that same number already exists in the same column, row, or 3x3 box). If so, display a banner warning the user of the problem that disappears the moment the user changes the board again (unless the change introduces a new problem, in which case the user should again be warned).

  • Display numbers that "came with" the board in a different color than those that the user has inputted.

  • Allow the user to undo the last change made to the board by hitting U or ctrl+Z.

When all is aligned

Once your implementation is working, you might find that you feel a little like this:

And you might wish that your Sudoku game was more like this. But you’ll have created a pretty darn impressive game, that hopefully your family and friends will enjoy.

To play with the staff’s own implementation of Sudoku, you may execute the below.

~cs50/chapter4/sudoku

How to Submit

Step 1 of 3

Execute update50 again to ensure that your IDE is up-to-date.

Step 2 of 3

  • Recall that you were asked to implement the sudoku.

    • Be sure that the following files exist in ~/workspace/chapter4/sudoku/:

  • Makefile

  • sudoku.c

  • sudoku.h as with:

    cd ~/workspace/chapter4/sudoku/
    ls

Step 3 of 3

Submit Sort Race:

cd ~/workspace/chapter4/sudoku/
submit50 cs50/2017/ap/sudoku

If you run into any trouble, email sysadmins@cs50.harvard.edu!

You may resubmit any problem as many times as you’d like before the deadline.

Your submission should be graded for correctness within 2 minutes, at which point your score will appear at cs50.me!

This was Sudoku.


2. Yes, annoyingly, (y, x) coordinates and not the typical (x, y) coordinates.
5. Those are two zeroes in n00b.
6. Which, for whatever reason, doesn’t always look yellow.
7. We decided that we wanted the grid roughly in the middle of your window but slightly to the left, and so we came up with those formulas by trial and error.
8. Know that KEY_BACKSPACE and KEY_DC generally map to a keyboard’s Backspace and Delete keys, respectively, if they’re actually present. Don’t worry if your own Backspace and/or Delete keys don’t seem to work, even though you’re listening for KEY_BACKSPACE and KEY_DC; some keyboards send different codes altogether.