Implement the game of Sudoku, per the below:
$ ./sudoku n00b
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.
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.
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.
Your work on this problem set will be evaluated along four axes primarily.
To what extent does your code implement the features required by our specification?
To what extent is your code consistent with our specifications and free of bugs?
To what extent is your code written well (i.e., clearly, efficiently, elegantly, and/or logically)?
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.
First, log into cs50.io and execute
within a terminal window to make sure your workspace is up-to-date.
Then, create a new directory inside of your
chapter4 (Remember how?) and navigate inside. Once there, obtain a copy of this problem’s distro by typing:
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:
You should see that your directory contains six files.
Makefile debug.bin l33t.bin n00b.bin sudoku.c sudoku.h
Much like the Game of Fifteen, Sudoku is a game of logic involving numbers. But it’s much more interesting. Consider the puzzle below:
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.
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.
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.
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.
Lather, rinse, and repeat these sorts of tricks enough times, and (assuming no PEBKAC) we’ll end up with the solution below.
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:
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, 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:
You should find a brand new executable called
sudoku in your current working directory. Go ahead and run it by typing
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 and l33t), 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:
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.
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
BG_. Here are the colors that ncurses comes with:
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
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
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 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. You needn’t understand how
fclose work yet, though you soon will! What this function ultimately does is load 81
ints into the global array called
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
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. 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
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_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.
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.
show_banner, why don’t we also peek at
show_cursor. Recall that functions like
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
shutdown. We think you can handle those!
So that’s everything. Not bad for about 600 lines.
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
~/workspace/chapter4/sudoku and record in it your answers to the below:
strcmp. What does it mean if
strcmp, when passed two strings as arguments, returns
How would you rewrite the line below, excerpted from
main, using only
int max = (strcmp(g.level, "debug") == 0) ? 9 : 1024;
Under what circumstances might the call to
sscanfbelow, excerpted from
sscanf(argv, " %d %c", &g.number, &c)
What fields in
grepresent the coordinates at which the user’s cursor belongs?
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!)
Around what line number in
maincould you add additional
casestatements to handle keystrokes besides N, R, and ctrl-L?
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
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_RIGHT, constants that represent the characters fed to ncurses'
getchfunction when arrow keys are pressed. (See the
getchfor 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_cursorhelps 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_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_DCor to some other number from 1 to 9 by hitting that number. 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.
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.
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.
update50 again to ensure that your IDE is up-to-date.
Recall that you were asked to implement the
Be sure that the following files exist in
cd ~/workspace/chapter4/sudoku/ ls
cd ~/workspace/chapter4/sudoku/ submit50 cs50/2017/ap/sudoku
If you run into any trouble, email firstname.lastname@example.org!
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.
KEY_DCgenerally 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_DC; some keyboards send different codes altogether.