15-112
Fall 2022 (Lecture 3)

Home

Syllabus

Schedule

Gallery

Staff

Piazza

Autolab

OH Queue

Forms

CS Academy

TP Showcase

CMU 15-112: Fundamentals of Programming and Computer Science
Term Project: Sudoku

The term project is entirely solo. 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.
The term project includes the following deliverables:
  1. Sudoku playing app (without hints but with highlighted incorrect values)
  2. Sudoku hint generator ("smart solver")
  3. Sudoku extra features
In addition, we will have Sudoku Contests and the TP Showcase in the last week of classes.

Grading:

In addition, we may award small amounts of bonus for extraordinary work, especially for exceptionally well-made extra features. We may also award small amounts of bonus for the winners of the various contests (see below).

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 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
    • Standard mode + Keyboard-only mode + Mouse-only mode
      Note: this has two purposes: to give you the opportunity to modestly consider accessibility issues, and to give you a modest UI design challenge. Also, we will only require this for non-bonus gameplay (so, for example, you could have a mouse-only help screen, or a mouse-based bonus feature, even when in keyboard-only gameplay mode).

  2. Load board
    • Randomly load hardcoded boards from text files (which we supply) by type (easy, medium, etc)
    • Manually enter a board (both graphically and by text file)

  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.
      • Note: the writeup initially required denoting "incorrect board values" here. That was dropped from part1, and instead moved to part2. Once you write your backtracker in part2, only then do you have to also display some graphical feedback to users when they make incorrect plays.

  4. Levels of Play
    • Users can select level of play ('easy', 'medium', 'hard', 'expert', 'evil'). This affects which boards are selected, which hints are required, and the default values for the user interface (such as whether legals are displayed by default).

  5. Automatic and Manual Modes for Legals
    • The user can toggle between automatic and manual modes for legals. In automatic mode, 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. In manual mode, the user is responsible for updating all the legals. By default, this mode should be manual for easy boards and automatic for medium-or-harder boards.

  6. 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'), but these must be in addition to the 's' feature. For example, we used 'S' (uppercase s) to set all the singletons.

Part 2. More Sudoku Playing App Features
These additional features are required, but are not due at tp1:

  1. Red dot (or similar) on incorrect values or legals
    • Requires finding the solution board using efficient backtracking ordered by fewest number of legals. Red dot appears if:
      1. User enters a wrong value.
      2. User bans a legal that is the right 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.

  2. Undo and Redo
    • Users must be able to undo moves, all the way back to the starting board, and then they must be able to redo undone moves.
    • After an undo, if they user makes a new move, then the list of moves to redo is cleared.
    • The writeup originally said: "This step requires using instances of a State class." However, we are relaxing that as follows: Wherever you see the State class below, read it as "the State class or one or more similarly well-chosen and well-designed classes". One key use of this class is to support using a single undoRedoList or both an undoList and a redoList of copies (actually, deepcopies) of State instances.
    • At a minimum, instances of a State class should have two properties:
      • state.board
        A 2d list of the values placed in each cell on the board, or 0 if no value is placed there yet.
      • state.legals
        A 2d list of the sets of legal values for each cell on the board. So state.legals[row][col] is a set, something like {2,3,8}.

Part 3. Sudoku Hint Generator ("Smart Solver")
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. Beautiful UI
    An especially engaging, powerful, easy-to-use, beautiful user interface.

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

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

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

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

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

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

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

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

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

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

Sudoku Contests
On the last day of classes (Thu 8-Dec), we will have some Sudoku contests in lecture. These will be required, but hopefully also good fun. Top performers in each contest will receive some few tiny bonus points and/or perhaps some kind of small prize. The goal here is not to win points, though. The goal is to have fun in the pursuit of learning. And the only requirement is that you attend and fully participate.

Everyone must participate in the various human solver contests. You are not required to participate in the computer solver contest, but you are strongly encouraged to do so.

Please read this carefully. And please treat this in the fun way it is intended. Thanks!

  1. Fastest Computer Solver
    To participate in the Fastest Computer Solver contest, do this: by 6pm Tuesday 6-Dec, submit to "fast_solve" in the "etc" category in Autolab a single Python file (no other files, nothing zipped, just one Python file), which contains a function exactly matching this spec: 
    def fast_solve(initialBoard):
   ...
   return solutionBoard
    This function:
    1. must be named "fast_solve".
    2. must take an initial 9x9 board (which will be a legal, partly-solved board at any possible level of difficulty).
    3. must be non-mutating (so make a deepcopy of the initial board, perhaps).
    4. must return the correct solved board for that board.
    5. must use backtracking meaningfully, but beyond that, you can do whatever you want.
    6. must not print anything to the console.
    7. must not crash (of course).
    8. Also, the file must not have any top-level code, so when we load it, nothing runs until we call your fast_solve function.
    The winner will be the submission that correctly solves every board we use for the contest, and has the lowest total time doing so.

  2. Fastest Human Solver
    To prepare for the various "Fastest Human Solver" contests (which everyone must participate in), you have to slightly modify your term project by tp2 so you can set it in "competition" mode. These changes are tiny and should take you literally 5-10 minutes or less. They are:
    1. No hints
      Simply ignore 'h' and 'H' (or whatever way you let the user ask for a hint).
    2. No red dots
      Instead, when you would have shown a red dot (or equivalent), the game immediately ends (it's even ok if you end the game by crashing your app!)
    3. Save board on game-over
      When the user solves the entire board, your app should immediately save the solved board to a file (named whatever you want) that you can then upload to Autolab. The file format should match the format we used in the boards we provided to you earlier -- no brackets, one space between values, etc. You will want to use writeFile from further up in this doc.

    With that, bring your charged laptop to class on the last day of classes! On that day, we will have the Fastest Human Solver contest. We will post a link to a file containing a board (live, during lecture) to Piazza, in the same format as the boards we have already supplied to you. You should download that file, which you can rename as you wish. Your app should then load the board in that file. The contest will not start until everyone has set up their board properly. Once you have it loaded and ready to go, you need to lower your screen and briefly wait. Once everyone is ready, we start solving! Remember: no hints and no red dots and no backtracking! You can (and probably should) use legals. When you are done, you will submit the file with your solved board to Autolab. Your submission must be in the same format as our saved boards. The time it takes to submit to Autolab counts, so do that quickly. However, don't worry if Autolab takes a while to autograde -- your timestamp is the moment Autolab recieves your file, no matter how long autograding takes.

  3. Fastest Human Team Solvers
    This is the same as the "Fastest Human Solver" contest, only you must work in teams of size N>2. The rule is simple: each person must set one and only one value before passing the laptop to the next person, and this must proceed in a rotation for all the members of your team. Everyone must also be involved in the solving process (so you can't have one person solving everything and simply telling everyone else what to type). The laptop-rotation rule only applies to setting values and not to legals (so if you ban or unban a legal, you should keep the laptop until you set a value). Everyone must be on a team (and only one team). You can pre-arrange your teams before Tuesday, or we will group you up on Tuesday if you have not done so. We will start with a partly-solved puzzle no harder than 'medium'.

  4. Fastest Keyboard-Only Solver
    This is the same as the "Fastest Human Solver" contest, only you must be in keyboard-only mode. We will start with a mostly-solved puzzle no harder than 'medium'. This will go quickly!

  5. Fastest Mouse-Only Solver
    This is the same as "Fastest Keyboard-Only Solver" contest, only you must be in mouse-only mode.
Be creative and have fun!