In this programming assignment, you will be tasked with implementing various approaches to solving Sudoku as a Constraint Satisfaction Problem. You will have the choice of programming in C++, Java, or Python. Much of the code has already been written for you, however, you will be asked to fill in the blank functions from whichever shell you decide to use. Please read this document before attempting to do any work.
Your grade will depend on your agent’s performance measure. Optionally, at the end of the quarter, your agent will compete against your peers’ agents in a class-wide tournament. There are a total of 5 methods to implement: Variable Selection Heuristics:
- Minimum Remaining Value (MRV)
- Minimum Remaining Value with Degree heuristic as a tie-breaker (MAD)
Value Selection Heuristics:
- Least Constraining Value (LCV). Has a specific tie-breaking mechanism for this assignment; see appendix.
- Forward Checking (FC)
- Norvig’s Check (NOR)
For more information on Norvig’s Check, see lecture slides for chapter 6.
Extra Heuristics (Tournament AI):
- Students are free to implement their own heuristic if they wish to, and use that heuristic to participate in the tournament. This is optional, extra credit.
To learn more about Sudoku, click here: https://www.learn-sudoku.com/what-is-sudoku.html
We will be working with Monster Sudoku instead of the regular Sudoku. Monster Sudoku (or Mega Sudoku) is a puzzle that follows the rules of Sudoku and is played on a NxN grid, N being any positive integer including
N > 9. The numbers that fill each square are selected from the first N positive integers. For display purposes, they are shown as 1, 2, …, 9, A, B, …, Z so that each token takes up exactly one column when printed.
Monster Sudoku puzzles are described by four parameters:
- N = the length of one side of the NxN grid, also the number of distinct tokens
- P = the number of rows in each block, also the number of block columns.
- Q = the number of columns in each block, also the number of block rows.
- M = the number of values filled in from the start.
Note: Norvig uses “box” where we use “block” – the terms are equivalent.
Additional information of the assignment is given below.
The performance measure of your agent is based on how well it does on Gradescope’s automated tests. Each function will have its own set of automated tests in Gradescope. Your grade is based on the number of tests passed. However, not all tests are visible; test your program thoroughly.
Each difficulty has a different board dimension and number of values given initially:
- Easy: P = Q = 3, N = 9 with 7 given values
- Intermediate: P = 3, Q = 4, N = 12 with 11 given values
- Hard: P = Q = 4, N = 16 with 20 given values
- Expert: P = Q = 5, N = 25 with 30 given values
In this section, you will find help setting up your coding environment. This project will take advantage of UCI’s openlab; any other coding environment is not supported. Think of openlab as a remote Linux computer you connect to when you are working on your program.
To connect to openlab, you will need to use SSH. SSH stands for Secure Shell. It is a program designed to allow users to log into another computer over a network. A Windows user will need to install PuTTY, while Mac/Linux users do not have to install anything and can use the terminal directly.
If you are new to Linux or the terminal, there are simpler, GUI alternatives to use the openlab and move files between openlab and your computer. Windows has WinSCP, and Mac has Cyberduck.
First, make sure you are connected to the UCI network. If you are outside UCI, you can use the VPN provided by UCI from this link.
Install the VPN and use it whenever you need to connect to openlab outside UCI. If you are not connected to the UCI network or the VPN, you cannot connect to openlab.
SSH into the openlab server to connect to openlab. If you are on Windows and using PuTTY, type openlab.ics.uci.edu into the Host Name box; make sure the port is 22 and the SSH flag is ticked. Click open, and login using your ICS account.
If you are using Mac, open the terminal found under Application -] Utilities. Enter ssh [email protected] and login using your into ICS account.
Keep in mind that your ICS account password is different from the one you use when logging into Canvas. If you forget your ICS account password, refer to this page for more information.
The same instructions are used to connect to openlab using WinSCP or Cyberduck (make sure the file protocol is SFTP, which stands for SSH File Transfer Protocol). The Host Name box should be openlab.ics.uci.edu , port is 22, username/password is your ICS account.
To download the shells on openlab, you will use Git. On openlab, whether through PuTTY or terminal, execute the following git clone command.
If there are updates to the project, execute git pull in the Sudoku_Student directory.
Form a team of 1-2 people on Gradescope. The procedure (naming rules, etc.) is described in the Team Formation section, under Deadlines.
Once you have your environment and team set up, you can start to program your agent. In the src folder of your shell you will find the source code of the project. You are only allowed to make changes to the BTSolver class. For WinSCP users, you can edit the file in openlab directly by opening the file using a text editor installed on your PC (right-click the file you want to edit then select the appropriate options). You can also use vim; refer to the Appendix: Helpful Tips section.
If you don’t know how or where to start, also refer to the Appendix: Helpful Tips section below (especially the Dependecies section). Afterwards, read all the code provided to you in the shell, including the comments, and understand how the whole system works. For Part1 AI, MRV should be the simpler function to try tackling first.
Remember that LCV has a tie-breaking mechanism. Refer to the Appendix for the details.
There are also Coding Clinic sessions you may want to attend. These are “office hours” with the people who worked on the shell, though you cannot ask them to write the code for you.
PLEASE MAKE SURE YOUR CODE RUNS ON OPENLAB! All grading is done inside openlab, so please test your code and make sure it runs on openlab before submitting. Do not test your AI anywhere other than inside openlab, as there are no guarantees it would work inside openlab. The procedures for compiling and testing are described below.
Inside the directory with the Makefile file, execute the command: make
A bin folder should have appeared with the compiled product in there. It is recommended to do this before any coding to ensure that the shell works fine (the shell will compile without any student code).
To run your program after you have compiled it, navigate to the bin folder. You should find the compiled program inside. Refer to the Shell Manual Appendix at the end of this document for help running it. To generate large amounts of boards to use with the folder option, refer to the Board Generator.
If you are using the Python Shell make sure you are using Python 3.5.2. On openlab, run the command module load python/3.5.2 to load Python 3.5.2.
Write a report according to the Professor’s instructions. Make sure your report is in pdf format. You only need to write the report once, after all functions have been written. Submit by the last deadline.
Part1 AI, Part2 AI
Download your BTSolver file and submit it to the appropriate assignment on Gradescope.
After you submit your project and the deadline passes, your final AI be entered into a tournament with your classmates. The tournament checks to make sure you followed all the instructions correctly, then runs your agent across several hundreds boards offour different difficulty level consisting of several boards each using the special heuristics the AI has. Every agent is run on the same boards to ensure fairness. Your agent’s total score is calculated and a scoreboard is constructed that will be made available. Your agent will be timed-out if it hangs for longer than one hour for a board. After the scoreboard is constructed, scores are checked for any illegal submissions. These include two agents with the same score.
Note: C++ is significantly faster than Python in most cases. Take this into account if you are planning to participate in the end-of- quarter tournament.
For this project, you will have a team formation deadline and three AI deadlines throughout the quarter, each of which build on top of each other. Refer to the syllabus on Canvas for the exact dates of the deadlines.
- Team Formation submission
- Part1 AI, Part2 AI
- Final Report
- Tournament Bonus / Final AI (Part2 AI)
For every submission, you will lose 10% for each late day after the deadline.
The submission of Team Formation must follow strict rules: Team names must use only numbers and alphabetic characters. Any symbols including whitespace, is not allowed. Capital letters are allowed. The submission text must follow this format:
team_name member_1_name, member_1_netid, member_1_id_number member_2_name, member_2_netid, member_2_id_number
YetAnotherAITeam123 John Smith, jsmith, 12345678 Jane Doe, jdoe, 11235813
You will lose points (up to 100%) if you don’t follow the stated rules above. Type this in a .txt file and submit it to Gradescope.
Implement MRV, LCV, and FC.
Implement MAD and NOR.
Each of the methods in Part1 and Part2 should be able to pass all provided Gradescope tests. Some tests are hidden; please test your functions thoroughly for edge cases.
If you write each section in clear, logical, technical prose, you will get 100% credit. You will lose 10% credit for each late day after deadline.
A report template is given at the bottom of the manual, and a report template should already be uploaded on canvas.
Submit the report in pdf form on Canvas . You only need to write the report once.
Your AI’s score will be compared to other students and ranked based on the total score obtained. The tournament bonus is between 1-10, where the top 10% will get a 10, the second 10% will get a 9, and so on. Generally, a 10 means a 10% bonus to your Final AI submission. Only students who submitted the Final AI by the deadline will be allowed to enter the tournament.