Sudoku Term Project Assignment

---

Grading

The requirements for the Sudoku project are listed in the section below. Here are the requirements to achieve various TP grades:

Grade	Requirements
90	Nice user interface Parts 1, 2, 3, and 4 working properly At least one moderately challenging extra feature (eg. undoing and redoing entire game states, or mouse/keyboard only modes)
80 (MVP)	Usable user interface Parts 1, 2, and 3 working properly
70	Usable user interface Parts 1 and 3 working properly Part 2 UI indication of incorrect value (from solution board files, not backtracking)
60	Usable user interface Part 1 mostly working (either automatic or manual legals do not need to be completed)

Note that these are not the only ways to achieve the listed grades, but they should give you an idea of the requirements needed to hit different grade thresholds. If you want to swap out one of the features listed above with a different one of comparable difficulty, discuss it with your mentor! It will most likely be allowed (and encouraged). Make this project your own!

Project Requirements

Part 1: Basic Sudoku Playing App

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 loads hardcoded boards from text files (which we supply) by type (easy, medium, etc)
   • 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: sudoku-starter-files.zip.
3. Draw board
   • Clearly denotes 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 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.

Part 2: Sudoku Solver

1. Incorrect Value Indicator
   • If the user enters an incorrect value (it does not match the solution at that cell), there should be an indication that they made a mistake. You can choose what the UI looks like (eg. red dot on the cell, changing the cell color).
2. Backtracking Solver
   • In order to do the above requirement, you must find a solution to the Sudoku board using efficient backtracking ordered by the fewest number of legals.
   • 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.

Part 3: Hint 1

1. Hint 1 Description: Obvious Singles
   • When a cell has only one legal value remaining, then this hint is to set the cell to that value.
2. Hint Indication
   • There should be a way for the user to ask for a hint. The hint should highlight the relevant cell (the cell with only 1 legal value).
3. Applying the Hint
   • There should be also a way for the user to ask for the hint to be performed. The app should automatically place the correct value in the cell that has only 1 legal value.

Part 4: Hint 2

1. Hint 2 Description: Obvious Tuples
   • When N cells in a region (a row, column, or block) 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. This means that no other cell in that region can contain any of those N values.
   • After adding this hint, you should be able to solve every easy and medium board, and even some hard boards simply by using hints!
2. Hint Indication
   • You should update your hint indication feature you implemented in part 3. If there is an obvious single, that hint should still be provided. However, if there are no obvious singles on the board, then you should highlight a set of cells involved in an obvious tuple.
3. Applying the Hint
   • Similarly, you should update your hint application feature you implemented in part 3. If there is an obvious single, then you should still apply that hint automatically. However, if there are no obvious singles, then you should automatically apply an obvious tuple. This means that you should find a group of N cells that share N values, and remove those N values from every other cell in the region.
4. A Hint on Implementing Hint 2
   • Use itertools.combinations() to loop over all the possible combinations of N values from a list of values. For example:

     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)

     Running that code produces this output:

     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')

Additional Features

We hope everyone includes 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. Below are some ideas for you, but you are encouraged to get really creative.

Note: this list is not in any particular order, and certainly leaves off many other wonderful ideas!

1. Keyboard Only / Mouse Only mode

   This gives you the opportunity to modestly consider accessibility issues. Design game modes that only require keyboard input or mouse input. Try to make the user experience as streamlined as possible!

2. Autoplayed Singletons
   

   In medium-or-harder play, the the user can press a key 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). It will repeat this process until there are no singletons left.

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. Web Browser Control + OCR (Optical Character Recognition)

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

12. Et Cetera

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

---