Introduction

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.

Consistency Checks:

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

Sudoku Game Mechanics

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.

Performance Measure

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.

Problems

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.

Install Required Applications

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.

Connect to openlab

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

Understanding the Tournament

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.

Team Formation

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

For example,

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

Part1 AI

Implement MRV, LCV, and FC.