CMU 15-112: Fundamentals of Programming and Computer Science
Term Project: Sudoku
This term project is either solo or collaborative in a team of two.
There will not be larger teams than two-person teams.
Sometime soon, you will have to fill out a form indicating whether you
work solo or with a partner. Some key points:
- You cannot reverse your decision.
Whatever you fill out on that form, that will stand for the duration of the project. After the form is submitted, you cannot leave a team, and you cannot join a team. - Partners must work entirely collaboratively.
If you opt to have a partner, then you must work closely together on the whole project. You absolutely may not split up the work so one partner only does some parts of the project and the other partner only does other parts. - Partners each submit their project to Autolab.
Each submission must include a file, partners.txt, that contains only two lines with the names and andrew ids of both partners. In addition, each Python file must include a comment at the top listing both partners' names and andrew ids, something like this:
The two submitted projects should be identical. In any case, graders will randomly select one of the two and that is the one that will be graded.# project partners: David Kosbie (koz) and Mark Stehlik (mjs)
- Partners will receive the same grade.
You will both attend the same grading session. Questions about your project (the code and the design) will be asked of each you in turns, and only the partner being asked a question may answer it, even if the other partner knows the answer. Thus, it behooves you to work closely together and to be sure each of you knows the code and the design very well. - Teams must produce more than individuals.
Naturally, we would expect two-person teams to be more productive than a single person. Perhaps not exactly twice as productive, but still, more productive. Thus, the standards for A/B/C level work will be appropriately higher for two-person teams.
As for citations, these should be placed directly in your code, with a comment including the URL of the source's website (or, if it is not a website, a brief but clear explanation of the source). This includes if you use code from the course website (such as from this document, or, for example,
getRadiusEndpoint
from the CS Academy notes). If necessary,
also include a very brief explanation of how you used the source -- this is
not necessary in most cases, if you simply used a function or a few lines
of code from it, but if you used larger blocks or if you adapted the code,
just say so. The point is to make it abundantly clear to us which code
is entirely yours, which is partly yours, and which is not yours.
Grading for Solo Projects:
- A: All the required deliverables working properly, including both kinds of hints, with perhaps just 1 or 2 small bugs, plus a nice user interface and at least one challenging extra feature or several well-made moderately-challenging extra features.
- B: All the required deliverables working properly, including just the first kind of hints, with perhaps up to 3 or 4 small bugs, plus a usable user interface and at least one working extra feature.
- C: Most of the required deliverables working properly, with perhaps 1 or 2 larger bugs and a few smaller bugs.
- D: Most of the required deliverables not working properly, but still shows much effort.
- R: Shows a clear lack of effort.
Grading for 2-Person Team Projects:
While we will grade each project on its own merits, you should expect that a 2-person team project of the same quality as a 1-person project would score about 5 points, or a half-letter-grade, less. Thus, the "A" from above would be an A-/B+ for a 2-person team. To safely secure an A, a two-person team should change the word "or" to "and" from above. That is:
- A: All the required deliverables working properly, with perhaps just 1 or 2 small bugs, plus a nice user interface and at least one challenging extra feature AND several well-made moderately-challenging extra features.
Deadlines and Deliverables:
- Checkpoints (tp1 + tp2):
You will have two checkpoints (tp1 and tp2), each worth 5% of your overall tp grade. All checkpoints include required 15-minute meetings with your assigned TP Mentor. The purpose is to confirm that you are making solid progress, and to discuss any issues you may have with your code, your user interface, etc. In each of these meetings, you will demo the work you have done so far, and discuss your code design, and your plans for next steps. Any unexcused missed meetings cannot be made up and will result in -50 on that checkpoint's score. Arriving more than 5 minutes late counts as a missed meeting. Also, grading for 2-person teams will only start when both students are present. Note that for scheduling purposes, your TP Mentor may at their discretion arrange the meetings to be within 2 days after the given checkpoint deadline.
Checkpoint Schedule tp1 Wed 12-Apr Grade is based only on active participation in the meeting. tp2 Wed 19-Apr Grade is based mainly on the quality of your Basic Sudoku Playing App (part 1 below). - Term Project Deliverable (tp3):
The final term project deliverable, tp3, is due on Wed 26-Apr at 5pm. No late submissions will be accepted. The tp3 deliverable includes the following (with details explained below):- Your Python code
- A partners.txt file listing the partners on the project (or just "Solo" if project is solo).
- A readme.txt file with high-level details of your project.
- A video.txt file with a link to a short video where you present your project.
- Deliverable Details:
Zip File:
Both tp2 and tp3 require that you submit a zip file to Autolab containing all the important files we need to grade your project. Note that we do not actually have to be able to run your project, although that is preferred. But if that's not possible, just be sure to provide us with all your code and all the other required elements. We will then view your project actually running on your computer. With that, to submit tp2 or tp3, follow these steps carefully:- Copy all the files needed to run your submission, including images, but no other files, in a new folder.
- Be sure the submission folder does not contain the installed cmu_graphics folder (which is huge).
- Zip the submission folder (if you cannot figure out how to do this, go to OH for help!)
- Improperly zipped, or entirely unzipped, submissions will not receive credit.
- The max size for the zip file is 10 megabytes (and we would prefer that your submission is much smaller than this)
- So... Check the size of your zip file. If it is larger than 10 MB, then you have to delete some of the media in your submission folder and rezip it until it is below 10 MB, preferably well below that.
- Submit your zip file to tp2 or tp3, as appropriate, in Autolab.
- Then, be sure to verify that this worked by doing the following:
- Download your submission from Autolab
- Double-click on the downloaded zip file to extract it.
- Inspect the files in the extracted folder to be sure they are as expected.
- If there are any problems, let us know immediately, and fix the problems and resubmit before the deadline!
partners.txt
Everyone must include this file in each submission, not just tp3. It must include the names and andrew ids of both partners, or "Solo" if the project is solo.
readme.txt
For tp3, you must include the (brief) file readme.txt in your zip file, which includes the following:- A short description of the project -- its name and what it does.
- How to run the project. For example, which file the user should run in an editor.
- Which libraries you are using that need to be installed, if any.
- A list of any shortcut commands that exist. Shortcut commands can be used to demonstrate specific features by skipping forward in a game or loading sample data. They are useful for when you are testing your code too!
video.txt
For tp3, place the file video.txt inside your submitted zip file. This file should contain just one line with a link to your project video. Be sure that your video's permissions are set so that we can view it without a password.
Important Note: since a video that reasonably closely follows our submission specs is essential for our grading purposes, we will not grade any project that does not include a reasonably well-made video. This means that you will receive a 0 without one.
Your video should be 1-3 minutes (and no more than 5 minutes in any case) that captures the main idea of the project. It should show the most important and coolest features of the project, with narration to explain how it works. For Sudoku projects, we would expect this to especially showcase your Extra Features.
This demo should not provide a full walkthrough of the whole project, and does not need to cover every single feature. Think of it as more of a trailer for the project as a whole. Your video demo should be uploaded to YouTube (or some other video hosting service), and your submission on Autolab should include a file called video.txt that contains a link to the uploaded video.
The quality of the video and audio does not need to meet any particular standard, but it should meet your own standards such that you would be happy to include it in your project portfolio. Feel free to use a video camera or a screen capture program to record. As for creating the videos, one approach is to use zoom. Create a meeting just with yourself, share the screen (with sound if you wish), record the meeting, and you are set. Also, on Macs, Quicktime is a great option. Another solid choice is Screencastify, a Chrome plugin that can record the entire screen easily (not just Chrome), integrates directly with Drive and YouTube, and is overall really easy to use. That said, you can use any video creation software you wish. Also, note that parts of some demo videos may be selected to appear in a showcase video we make for the course website. - Copy all the files needed to run your submission, including images, but no other files, in a new folder.
Backups:
This is a very important hint. To avoid a catastrophic loss of work, you should make frequent backups of your term project files -- we suggest at least once daily. These should be stored off of your laptop. They can be on an external hard drive, on Google Drive, or anywhere else that is convenient for you. Note that we cannot grant extensions for lost work. So be smart and backup your files daily!
Part 1. Basic Sudoku Playing App
The first major deliverable (tp2) is an app that lets the user play Sudoku. We will discuss the details in lecture, but this app must include all of the following:
- App features
- Runs offline using desktop-installed version of CS Academy (may also run online, but this is not required)
- Screens: Splash screen, Help screen, Play screen
- Load board
- Randomly load hardcoded boards from text files (which we supply) by type (easy, medium, etc)
- Draw board
- Clearly denote each of the following: 3x3 blocks, initial board values, user-added board values, the currently selected cell, game over, and all other required elements for basic gameplay.
- Levels of Play
- Users can select level of play ('easy', 'medium', 'hard', 'expert', 'evil'). This affects which boards are selected and which hints are required.
- Automatic Mode for Legals
- The app automatically maintains legal values in each cell. Each time a value is placed in a cell, that value is automatically removed from all the legals in that cell's row, column, and block.
Part 2. Additional Sudoku Playing App Feature
This additional feature is required in tp3, but not in tp2:
- Red dot (or similar) on incorrect values
-
Requires finding the solution board using efficient backtracking ordered by fewest number of legals.
Red dot appears if:
- User enters a wrong value.
Regarding the backtracker:- Your backtracker must try to solve the next cell with the fewest number of legal values -- unless you used another more-clever approach that somehow runs even faster than that.
- In any case, your backtracker must run much faster than the naive backtracker which simply tries to solve the next empty cell.
-
Requires finding the solution board using efficient backtracking ordered by fewest number of legals.
Red dot appears if:
Part 3. Sudoku Hint Generator ("Smart Solver")
This feature is also required in tp3, but not in tp2. To receive an A, your app must include both kinds of hints. To receive a B, your app must include just the first kind of hint.
In this part, you will add a hint generator, so the user can ask for a hint. We will include two hint types that together can solve every easy and medium board, and even some hard boards. If you wish, as one or more of your extra features, you can add more hints to solve even harder boards. If you do that, you may use the web to find lists and descriptions of these kinds of hints. Just be sure to cite the websites you use, and be sure that none of them include any code at all (in Python or any other language), just English descriptions of the hints. For example, here is a page describing the 'XY Wing' hint. Again, that is for an extra feature, should you choose to do it. There are only two hint types that are required.
As for the user interface, there are two levels to a hint. The first level simply highlights the cell or cells that involve the hint (but no values are set, and no legals are banned). The second level actually performs the move -- setting the value (for hint 1) or banning some of the legal values (for hint 2). We use 'h' for the first type of hint, and 'H' for the second (stronger) kind of hint, but you can use another method for the user to ask for these hints. Whatever you decide, you must support these two levels of hints, with the two kinds of hints described below.
First, some vocabulary. We will say that the target cells (or just "targets") for a hint are the cells that contain the pattern, such as an Obvious Single or an Obvious Pair (explained below). Once we find our target cells, we then find the moves for the hint. These are a list of either:
- ('set', row, col, value)
- ('ban', row, col, values)
Hint #1: Obvious (or "Naked") Singles
When a cell has only one legal value remaining, then this hint is to set the cell to that value. The target cell is simply the one cell with the Obvious Single, and the moves list contains one entry of type 'set'.
Hint #2: Obvious (or "Naked") Tuples (Pairs, Triples, Quads, Quints)
Note: this hint is more challenging. Take your time. Read this carefully. Be sure to understand every word here! Plus, while we provide important details here, this writeup is intentionally incomplete, leaving some hard parts for you to figure out! You can do it!
When N cells in a region together only include N unique legal values, then those N values must somehow be placed in those N cells. We do not know which cell contains which value, but we do know that together those N cells must contain those N values.
The target cells for this hint are the N cells containing the Obvious Tuple.
Once we found an Obvious Tuple, the moves list will contain bans (and not sets). That is, using this hint, we cannot actually set any values, but we can ban some legal values from some cells. For every region that contains all N target cells, we have to ban the N values from the legal values in every cell in that region except the target cells themselves.
Sometimes, you will find an Obvious Tuple which does not result in any new bans. In that case, this is not a valid hint and should be ignored.
Hints:
- List of regions
We found it extremely helpful to include a list of regions, where each region is a list of 9 (row,col) pairs. There are 27 valid regions -- 9 rows, 9 cols, and 9 blocks. By placing them all in a single list of regions, we can have a single loop handle all 3 region types, rather than copy-paste-edit the code for rows to make it work for cols and then again to make it work for blocks. - itertools.combinations
We then looped N from 2 to 5 (inclusive), and for each N, we looped over every region, and for each region, we checked every combination of N cells in that region as our target cells. Then, for each of these possible target cells, we tried every combination of N values (from 1 to 9) to see if that combination of N values is an Obvious Tuple in that combination of N target cells. If so, we return that hint!
How did we find these combinations? We useditertools.combinations
. See the hints section further down in this document for more on that.
Part 4. Sudoku Extra Features
We expect everyone to include some clever and engaging extra features. The points you receive for these features will depend on two things: (1) how much they improve gameplay, and (2) how sophisticated the code is. Here are some ideas for you, but you are encouraged to get really creative here. Just be sure to list all your extra features in a triple-quoted string at the top of your app!
Note: this list is not in any particular order, and certainly leaves off many other wonderful ideas!
- Manual Mode for Legals
Allow the user to toggle between automatic and manual modes for legals. In manual mode, the user is responsible for updating all the legals. By default, this mode might be manual for easy boards and automatic for medium-or-harder boards. - Autoplayed Singletons
In medium-or-harder play, the the user can press a key (we used 's' for this) and the app will automatically select the next singleton (cell with only one legal value) and make that move (entering that sole legal value into that board cell), or indicate that there are no singletons at that time. You may add additional ways that your app handles singletons (such as automatically setting all of them, rather than requiring pressing 's'). For example, we used 'S' (uppercase s) to set all the singletons. - Undo and Redo
Users can undo moves, all the way back to the starting board, and then they can redo undone moves. After an undo, if the user makes a new move, then the list of moves to redo is cleared. - Beautiful UI
An especially engaging, powerful, easy-to-use, beautiful user interface. -
Sudoku Variations
Implement one or more of the variations listed here or here or here (or many other websites). Some of these are very challenging, others are simply beautiful. -
Preferences
A preferences file that is loaded with colors (for empty cells, initial board values, the current selection, etc) and other preferences (show/hide legals, etc), and is saved each time the user changes these preferences. -
Faster Backtracker
Improve the backtracker to solve boards (especially harder boards) as fast as possible. -
Better Hint Generator
Generate hints that solve hard, expert, or evil boards. -
Random Board Transformer
Given a Sudoku board, use some random sequence of legal-board-preserving transformations like those mentioned here (and many other websites) to transform the board into an equivalent but very different looking board. This gives the user what seems like an infinite number of boards at the same level of difficulty to play based on a small set of starter boards. -
Random Board Generator
Write an algorithm to randomly generate Sudoku boards. Be sure to be level-appropriate. Medium boards, for example, must be solvable using only the first two hints. -
Save board as PDF
Let the user save the board and the solution (on separate pages) as a PDF. -
Et Cetera
Again, this list is very incomplete. Dream up your own wonderful ways to enhance gameplay or the user experience. -
Exotic UI
If you are feeling especially ambitious, and only with pre-approval from the course faculty, you may go for something more exotic, like controlling the app by voice, or by the camera using physical movements (pointing, for example). Tread carefully, though: time is limited and these kinds of features often do not get completed by the project deadline. -
Web Browser Control + OCR (Optical Character Recognition)
Another ambitious feature is to use selenium to control the web browser, so your Python app can access the board while you are using sudoku.com in Chrome. Then, you can use PIL (pillow) to do OCR (optical character recognition), so that you can detect the values on the board in the browser. Then, you can use your hint generator to display hints, or even to automically solve the board (again, directly in Chrome). This is very cool if also ambitious. Good luck!
Sudoku Hints and Resources
You may find the following hints and resources to be helpful as you write your projects.
- Starter Files
- Files
Here are the starter files that contain 200 images of Sudoku boards, text files of those 200 boards, and solutions for 15 of those 200 boards: - removeTempFiles
When you zip or unzip files on a Mac, the OS sometimes adds .DS_Store files that you may not want. Here is a script that will remove all the .DS_Store files from a folder and all the folders it contains.
You can use it to remove other kinds of files, such as all .txt files. But use it carefully, because it permanently deletes files!import os def removeTempFiles(path, suffix='.DS_Store'): if path.endswith(suffix): print(f'Removing file: {path}') os.remove(path) elif os.path.isdir(path): for filename in os.listdir(path): removeTempFiles(path + '/' + filename, suffix) removeTempFiles('sampleFiles') # removeTempFiles('sampleFiles', '.txt') # be careful
- Files
- Running Offline
- Installing Python and VS Code
See the notes on Getting Started with VS Code. - Using pip
Many students struggle to get pip to install modules into the same Python that they are using (since most computers have several versions of Python installed at any given time). Here is a simple fix: using the same VS Code setup that you will use for your term project, run the following code to install a pip module:
After this example, you can do this and it should work:import sys, os def runPipCommand(pipCommand, pipPackage=None): # get quoted executable path quote = '"' if 'win' in sys.platform else "'" executablePath = f'{quote}{sys.executable}{quote}' # first upgrade pip: command = f'{executablePath} -m pip -q install --upgrade pip' os.system(command) # input the package from the user if it's not supplied in the call: if pipPackage == None: pipPackage = input(f'Enter the pip package for {pipCommand} --> ') # then run pip command: command = f'{executablePath} -m pip {pipCommand} {pipPackage}' os.system(command) runPipCommand('install', 'pyjokes') # <-- replace 'pyjokes' with your module!
import pyjokes print(pyjokes.get_joke())
- Fonts
Unfortunately, fonts do not fully work in the desktop version of CMU Graphics. These fonts should work properly, however (or at least they will very soon): serif, sans-serif, cursive, fantasy, and monospace.
- Installing Python and VS Code
- Update (27-Nov-2022) to Running Offline
Important: our amazing CS Academy dev team deployed an updated version of the offline cmu_graphics package today. This gives you some great features, but also requires some changes in your code!
To use these features, do this:- Upgrade your cmu_graphics installed version, by either:
- (Preferred approach) Run the pip script above with this line:
runPipCommand('install --upgrade', 'cmu_graphics')
- Or: download the upgraded version from here.
- (Preferred approach) Run the pip script above with this line:
- Delete cmu_cs3_graphics.py (it is no longer needed!)
- Change this line in your app:
to this:from cmu_cs3_graphics import *
from cmu_graphics import *
Once you have properly updated cmu_graphics, you then get these handy new features:- Do not use cmu_cs3_graphics.py and do not import cmu_cs3_graphics (just import cmu_graphics)
- Builtin support for runAppWithScreens (no need to add this code to your app, it is in cmu_graphics now)
- Support for getImageSize, so you can now do this:
imageWidth, imageHeight = getImageSize(url)
- Support for some additional font families ('serif', 'sans-serif', 'cursive', 'fantasy', and 'monospace')
- Support for resizing the app window, and the new user event handler
onResize(app)
- Key handlers can now take an optional "modifiers" argument,
which is a list that can contain 'shift', 'control', and 'meta'.
For example:
def onKeyPress(app, key, modifiers): if ((key == 'a') and ('control' in modifiers)): print('You pressed control-a!')
- Upgrade your cmu_graphics installed version, by either:
- Screens
- runAppWithScreens + setActiveScreen
Together, these two functions make it relatively easy to run an app that uses screens (such as a splash screen, help screen, and play screen). First, for each screen, define your MVC functions with that screen (and an underscore) as a prefix. For example, for the splash screen, we may name it 'splash', and then we would define 'splash_onKeyPress', 'splash_redrawAll', and so on. Note that instead of 'splash_onAppStart', you define 'splash_onScreenStart'.
Next, you have to decide which screen will be the initial screen when the app first launches. Say it is 'splash'. Then, instead of do this:
Do this:runApp()
You can still add other keyword parameters, such as to set the width, like so:runAppWithScreens(initialScreen='splash')
Finally, once the app is running, just callrunAppWithScreens(initialScreen='splash', width=800)
setActiveScreen(newScreen)
to change which screen is active. That's it! - Demo App (runAppWithScreensDemo)
Try running runAppWithScreensDemo1.py in the online sandbox. Press 's' to switch between active screens. This works! Note that for now, the onScreenActivated event only works on offline (and not in the Sandbox) (coming soon!).
Demo with Multiple Files
As your term project grows, you may wish to place the code for each screen in its own file. Here is an example that shows you how to do that:
- runAppWithScreens + setActiveScreen
- Files and Folders
- readFile
Here is the code you need to read a file:
With that, you can do something like this:def readFile(path): with open(path, "rt") as f: return f.read()
contents = readFile('boards/easy-01.png.txt')
- writeFile Here is the code you need to write a file:
With that, you can do something like this:def writeFile(path, contents): with open(path, "wt") as f: f.write(contents)
contents = 'This is just a string. Woohoo!' writeFile('someFolder/myFileName.txt', contents)
- readFile
- os.listdir
To list the files in a directory (that is, folder), firstimport os
, then useos.listdir(path)
, which returns a list of all the filenames in that directory. So you can do something like this:for filename in os.listdir('boards'): if filename.endswith('.txt'): pathToFile = f'board/{filename}' fileContents = readFile(pathToFile) doSomething(fileContents)
- Paths in Windows OS
Windows paths can include backslashes, like 'C:\15-112\term-project\tp.py'. That string will not work as a file path in Python, because backslashes are escape characters. For example, '\t' is the tab character in that string. You can fix this by using '\\', which is the escape character for a backslash! So for each \ in your path, just use two of them. Thus, the above path can be used as 'C:\\15-112\\term-project\\tp.py'.
There are two other ways to handle this. First, you can generally use forward slashes (like '/') and those should work in most cases on all platforms. Second, you can useos.sep
, which is always set to the appropriate file path separator ('/' on Mac, '\\' on Windows). But if you are intent on using backslashes on Windows, then escape them, as noted.
- app.getTextInput(prompt)
In graphical apps, useapp.getTextInput(prompt)
instead ofinput(prompt)
. This will result in a modal input dialog box (which is desirable), instead of a text-based input in the console (which is not desirable, not in a graphical app). Also, do not call this function inredrawAll
. - random.choice
Userandom.choice(L)
to randomly choose an element from the list L. - itertools.combinations
Useitertools.combinations()
to loop over all the possible combinations of N values from a list of values. For example:
Running this code produces this output:import itertools L = [ 'cat', 'cow', 'dog', 'gnu', 'pig'] print('Here are all the animals:') print(' ', L) print('Here are all the combinations of 3 animals:') for M in itertools.combinations(L, 3): print(' ', M)
Here are all the animals: ['cat', 'cow', 'dog', 'gnu', 'pig'] Here are all the combinations of 3 animals: ('cat', 'cow', 'dog') ('cat', 'cow', 'gnu') ('cat', 'cow', 'pig') ('cat', 'dog', 'gnu') ('cat', 'dog', 'pig') ('cat', 'gnu', 'pig') ('cow', 'dog', 'gnu') ('cow', 'dog', 'pig') ('cow', 'gnu', 'pig') ('dog', 'gnu', 'pig')
Here are some demos that show how to use PIL to work with images: image-demos.zip.
- demo1_drawing_images.py
This shows how to draw an image, and to do some basic manipulations (flipping, scaling, rotating). - demo2_editing_pixels.py
This shows how to create a new empty image, and then to usegetpixel()
andputpixel()
to edit images. Note that these functions can be a bit slow, especially if you loop over all the pixels in larger images. - demo3_using_ImageDraw.py
This shows how you can use ImageDraw to draw directly onto an image. The example only draws ovals, but ImageDraw includes a bunch of other shapes. For more on ImageDraw, see here. - demo4_using_sprites.py
This shows how to use a spritesheet image along withcrop()
to animate a sprite. - demo5_using_animated_gifs.py
This shows how to display an animated gif. - demo6_saving_as_pdf.py
This shows how to save one or more images in a PDF.
If you want to include sounds in your app, check out soundDemo.zip. Enjoy!
Also see these hints that we discussed in lecture.
Be creative and have fun!