实现 Sudoku 游戏的AI部分。
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
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.
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
Tasks to Complete
Setup Your Environment
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.
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.
Download the shells on openlab
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 your team
Form a team of 1-2 people on Gradescope. The procedure (naming rules, etc.) is
described in the Team Formation section, under Deadlines.
Program your AI
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.
Compile Your AI
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).
Test Your AI
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 Your Project Report
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.
Submit Your Project
Part1 AI, Part2 AI
Download your BTSolver file and submit it to the appropriate assignment on
Gradescope.
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.
Deadlines
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.
Three Deadlines
Part1 AI
Implement MRV, LCV, and FC.
Part2 AI
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.
Final Report
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.
Tournament Bonus
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.
