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:
  1. 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.
  2. 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.
  3. 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:
    # project partners: David Kosbie (koz) and Mark Stehlik (mjs)
    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.
  4. 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.
  5. 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.
Whether working solo or with a partner, you must complete this on your own (of course, with help always available by our amazing TA's). In particular, you must not use any online sources that mention Sudoku and which include any code at all (Python or otherwise) or which discuss code in any way. You may use online sources that simply teach how to solve Sudokus manually (without code), but you must clearly cite those if you do. You may also use online sources that explain how to do non-Sudoku-related Python tasks, such as loading or saving a file, but again you must clearly cite those if you do.

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:

In addition, we may award small amounts of bonus for extraordinary work, especially for exceptionally well-made extra features.

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:
Deadlines and Deliverables:


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:

  1. 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

  2. Load board
    • Randomly load hardcoded boards from text files (which we supply) by type (easy, medium, etc)

  3. 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.

  4. 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.

  5. 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:

  1. 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:
      1. User enters a wrong value.
      You may use a different UI than a red dot, so long as it is very clear.

      Regarding the backtracker:
      1. 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.
      2. In any case, your backtracker must run much faster than the naive backtracker which simply tries to solve the next empty cell.

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:
  1. ('set', row, col, value)
  2. ('ban', row, col, values)
These are the changes to the board that the user should make in response to the hint (or the changes that would be automatically made if the user asks the app to actually do the moves for them).

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:
  1. 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.

  2. 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 used itertools.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!

  1. 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.

  2. 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.

  3. 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.

  4. Beautiful UI
    An especially engaging, powerful, easy-to-use, beautiful user interface.

  5. 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.

  6. 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.

  7. Faster Backtracker
    Improve the backtracker to solve boards (especially harder boards) as fast as possible.

  8. Better Hint Generator
    Generate hints that solve hard, expert, or evil boards.

  9. 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.

  10. 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.

  11. Save board as PDF
    Let the user save the board and the solution (on separate pages) as a PDF.

  12. Et Cetera
    Again, this list is very incomplete. Dream up your own wonderful ways to enhance gameplay or the user experience.

  13. 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.

  14. 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.


Be creative and have fun!