xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

java代写-COMP 250

时间：2021-04-25

Final Project

COMP 250 Winter 2021

posted: Friday, Apr. 16, 2021

due: Friday, Apr. 30, 2021 at 23:59

General Instructions

• Submission instructions

– Please note that the submission deadline for the final project is very strict. No sub-

missions will be accepted after the deadline.

– As always you can submit your code multiple times but only the latest submission will

be kept. We encourage you to submit a first version a few days before the deadline

(computer crashes do happen and codePost may be overloaded during rush hours).

– This is the file you should be submitting on codePost:

∗ ChessSudoku.java

Do not submit any other files, especially .class files. Any deviation from these

requirements may lead to lost marks

• Please note that the classes you submit should be part of a package called finalproject.

• Starter code is provided for this project. Do not change any of the class names, file names,

method headers. You can add helper (i.e. private!) methods if you wish. Note also that

for this project, you are NOT allowed to import any other class (all import statements other

than the one provided in the starter code will be removed). Any failure to comply with

these rules will give you an automatic 0.

• The project shall be graded automatically. Requests to evaluate the project manually shall

not be entertained, so please make sure that you follow the instruction closely or your code

may fail to pass the automatic tests.

• Whenever you submit your files to codepost, you will see the results of some exposed tests.

These tests are a mini version of the tests we will be using to grade your work. If your code

fails those tests, it means that there is a mistake somewhere. Even if your code passes those

tests, it may still contain some errors. We will test your code on a much more challenging set

of examples. We highly encourage you to test your code thoroughly before submitting your

final version.

• You will automatically get 0 if your code does not compile.

• Failure to comply with any of these rules will be penalized. If anything is unclear, it is up to

you to clarify it by asking either directly a TA during office hours, or on the discussion board

on Piazza.

1

Learning Objectives

This project is meant for you to practice once again working with recursive algorithms. In particular,

you will learn about backtracking algorithms which at the base use the idea depth-first search on

search trees. The starter code provided for this project is not as extensive as in the past assignments.

This will leave you more freedom on how to go about implementing the tasks your code is required

to perform.

Introduction

A Sudoku is a Japanese logic puzzle which has been extremely popular for the past 20 years. In

classic Sudoku, the player has to fill a 9 by 9 grid using digits from 1 to 9 making sure that no digit

is repeated on any row, column or 3 by 3 box composing the grid. If you have never done so, I would

suggest you to try solving some Sudoku puzzles (you can find many here). As you might know,

many different variants of Sudoku exist. My personal favourite is Chess Sudoku which I discovered

when last summer I found myself binge watching a YouTube channel called Cracking the Cryptic

(by the way, I highly recommend the channel even if you think Sudoku is not for you. You’ll change

your mind!). A Chess Sudoku puzzle is a classic Sudoku puzzle with the addition of one or more of

the following chess inspired rules:

• Knight Rule: a digit must not appear a chess knight’s move away from itself. Knights in chess

move forming an L shape: either two squares vertically and one horizontally, or two squares

horizontally and one square vertically. See this figure for a graphical representation.

• King Rule: a digit must not be a King’s move away from itself. Which to the classical rules

of Sudoku only adds the fact that a digit cannot be a single diagonal move away from itself.

• Queen Rule: every 9 in the grid acts like a chess Queen and must not be in the same row/-

column/3x3 box or diagonal of any other 9.

For this project you will write a program that will attempt to solve Classical and Chess Sudoku

puzzles. The starter code contains a simple class representing a Sudoku puzzle. The class also

contains several methods that allow you to load a Sudoku grid from a txt file and display it on the

screen.

Your goal is to implement the method solve() which modifies the ChessSudoku object on which

it is call, by filling in the grid to obtain a solution.

Backtracking

There are many different ways you can write a program that solves Sudoku’s puzzles. A common

way to approach the problem is using a backtracking algorithm. Backtracking is a brute force

approach that consists in building a set of solutions incrementally. The idea is to use recursion to

build a solution step by step. In the usual scenario, we have different options at each step and we

simply make a decision. As soon as the algorithm realizes that the step taken led to a set of solutions

that would be invalid (i.e. they won’t satisfy the constraints of the problem), then it backtracks,

2

effectively eliminating all solutions that could be obtained by taking that last step. You can think

of this as if the set of all possible solutions is represented by the leaves of a tree where each internal

node represents a step taken toward a possible solution (i.e. a partial solve to the problem). Then

a backtracking algorithm would perform a depth-first search on this tree and as soon as it figures

out that the solutions obtained in a certain branch would be invalid, it simply discards that whole

branch and moves to the next one.

For example, when we begin to solve a problem we can think about starting at the root of a tree

where its children denoted the possible choices we have available. By choosing one of its children

(i.e. by making a choice) we take a step toward a certain sets of possible solutions (i.e. the leaves

that are reachable from that child). Other choices will then be available to us and we’ll keep taking

steps forward until we either reach a leaf (i.e. a solution) or an internal node which we know will not

lead to any valid solution. If we reach a valid solution, then our task might be over. On the other

hand, if we reach an invalid solution or an internal node that will not lead to any valid solution, we

take a step back and at the previous level of the tree we choose the next child.

Consider the following tree:

root

/ | \

A B C

/\ /\ /\

D E F G H I

The leaves denote the set of possible solutions to the problem. Let’s say that only G, H, and I are

valid solutions. Now, a backtracking algorithm would start from the root and visit the first child

(i.e. take a decision that represents a first step toward a solution). We might then already realize

that A would not lead to any valid solution. If that’s the case we would then backtrack, undoing

what we had done in the last step and getting back to the root node where we’ll then take the next

available choice that will lead us to node B. From B the next step will lead us to the leaf F which

does not represent a valid solution. We will then backtrack, undoing what we had done in the last

step and getting back to B where we can then take the next available choice. This will lead us to G

which happens to be a valid solution and hence we are done.

How can you apply this type of reasoning to solving a Sudoku? The idea would be the follow-

ing:

as long as there are empty cells in the grid

pick an empty cell and place a number in it

if a conflict occurs (i.e., at least one of the Sudoku rules is broken),

then remove that number and backtrack

if there are no conflicts, attempt to fill in the rest of the grid

if you were unable to fill the rest of the grid

then remove that number and backtrack

It is up to you to figure out how to code this idea into your program. I would highly suggest you

3

to spend some time solving a couple of Sudokus before starting to write your program. This will

allow you to better understand the problem at hand and think about possible steps you can take

to optimize your program. This project is much more open-ended than your previous assignments

and it leaves you the freedom to be more creative and try to bring together everything you have

learned throughout the semester.

Your Task

In the ChessSudoku class implement the method solve(). You can find additional information on

the method in the template code. Please feel free to add as many private helper methods/classes

as your see fit.

Testing and Evaluation

Your program will be tested on several classic Sudoku puzzles, as well as different variants of the

chess Sudoku puzzles.

Together with the template code, we provided you with a set of txt files representing different

Sudoku puzzles with different difficulties which you can use to test your program. Following the

same format you can create as many new puzzles as you like to further test your code. The puzzles

we’ll be using to grade your assignment will remain secret. Please note that the txt files should be

stored in the project folder of your program, and not the package folder, nor the src folder.

This is how we will evaluate your code:

+ 75% Your program finds a solution to 3x3 Sudoku puzzles in less than 10 seconds (assuming

they have a solution). The points awarded will be proportional to the number of puzzles from

the secret tests your code can solve.

+ 10% Your program find a solution to square puzzles up to 5x5 (assuming they have a solution).

+ 10% Your program has an additional feature that finds all possible solutions to a given puzzle.

This will involve continuing the search after the first solution is found (i.e., pretending that

solution doesn’t exist) to see if another solution can be found. All the solved Sudokus should

be correctly stored in the field named solutions.

last 5% The remaining 5% of the grade will be established based on your code’s ranking in a

tournament where each program will be given one minute to solve each Sudoku puzzle on our

computer. The ranking is established based on the number of Sudokus it succeeds at solving,

from a set of 10 problems ranging from very easy to very difficult.

4

学霸联盟

COMP 250 Winter 2021

posted: Friday, Apr. 16, 2021

due: Friday, Apr. 30, 2021 at 23:59

General Instructions

• Submission instructions

– Please note that the submission deadline for the final project is very strict. No sub-

missions will be accepted after the deadline.

– As always you can submit your code multiple times but only the latest submission will

be kept. We encourage you to submit a first version a few days before the deadline

(computer crashes do happen and codePost may be overloaded during rush hours).

– This is the file you should be submitting on codePost:

∗ ChessSudoku.java

Do not submit any other files, especially .class files. Any deviation from these

requirements may lead to lost marks

• Please note that the classes you submit should be part of a package called finalproject.

• Starter code is provided for this project. Do not change any of the class names, file names,

method headers. You can add helper (i.e. private!) methods if you wish. Note also that

for this project, you are NOT allowed to import any other class (all import statements other

than the one provided in the starter code will be removed). Any failure to comply with

these rules will give you an automatic 0.

• The project shall be graded automatically. Requests to evaluate the project manually shall

not be entertained, so please make sure that you follow the instruction closely or your code

may fail to pass the automatic tests.

• Whenever you submit your files to codepost, you will see the results of some exposed tests.

These tests are a mini version of the tests we will be using to grade your work. If your code

fails those tests, it means that there is a mistake somewhere. Even if your code passes those

tests, it may still contain some errors. We will test your code on a much more challenging set

of examples. We highly encourage you to test your code thoroughly before submitting your

final version.

• You will automatically get 0 if your code does not compile.

• Failure to comply with any of these rules will be penalized. If anything is unclear, it is up to

you to clarify it by asking either directly a TA during office hours, or on the discussion board

on Piazza.

1

Learning Objectives

This project is meant for you to practice once again working with recursive algorithms. In particular,

you will learn about backtracking algorithms which at the base use the idea depth-first search on

search trees. The starter code provided for this project is not as extensive as in the past assignments.

This will leave you more freedom on how to go about implementing the tasks your code is required

to perform.

Introduction

A Sudoku is a Japanese logic puzzle which has been extremely popular for the past 20 years. In

classic Sudoku, the player has to fill a 9 by 9 grid using digits from 1 to 9 making sure that no digit

is repeated on any row, column or 3 by 3 box composing the grid. If you have never done so, I would

suggest you to try solving some Sudoku puzzles (you can find many here). As you might know,

many different variants of Sudoku exist. My personal favourite is Chess Sudoku which I discovered

when last summer I found myself binge watching a YouTube channel called Cracking the Cryptic

(by the way, I highly recommend the channel even if you think Sudoku is not for you. You’ll change

your mind!). A Chess Sudoku puzzle is a classic Sudoku puzzle with the addition of one or more of

the following chess inspired rules:

• Knight Rule: a digit must not appear a chess knight’s move away from itself. Knights in chess

move forming an L shape: either two squares vertically and one horizontally, or two squares

horizontally and one square vertically. See this figure for a graphical representation.

• King Rule: a digit must not be a King’s move away from itself. Which to the classical rules

of Sudoku only adds the fact that a digit cannot be a single diagonal move away from itself.

• Queen Rule: every 9 in the grid acts like a chess Queen and must not be in the same row/-

column/3x3 box or diagonal of any other 9.

For this project you will write a program that will attempt to solve Classical and Chess Sudoku

puzzles. The starter code contains a simple class representing a Sudoku puzzle. The class also

contains several methods that allow you to load a Sudoku grid from a txt file and display it on the

screen.

Your goal is to implement the method solve() which modifies the ChessSudoku object on which

it is call, by filling in the grid to obtain a solution.

Backtracking

There are many different ways you can write a program that solves Sudoku’s puzzles. A common

way to approach the problem is using a backtracking algorithm. Backtracking is a brute force

approach that consists in building a set of solutions incrementally. The idea is to use recursion to

build a solution step by step. In the usual scenario, we have different options at each step and we

simply make a decision. As soon as the algorithm realizes that the step taken led to a set of solutions

that would be invalid (i.e. they won’t satisfy the constraints of the problem), then it backtracks,

2

effectively eliminating all solutions that could be obtained by taking that last step. You can think

of this as if the set of all possible solutions is represented by the leaves of a tree where each internal

node represents a step taken toward a possible solution (i.e. a partial solve to the problem). Then

a backtracking algorithm would perform a depth-first search on this tree and as soon as it figures

out that the solutions obtained in a certain branch would be invalid, it simply discards that whole

branch and moves to the next one.

For example, when we begin to solve a problem we can think about starting at the root of a tree

where its children denoted the possible choices we have available. By choosing one of its children

(i.e. by making a choice) we take a step toward a certain sets of possible solutions (i.e. the leaves

that are reachable from that child). Other choices will then be available to us and we’ll keep taking

steps forward until we either reach a leaf (i.e. a solution) or an internal node which we know will not

lead to any valid solution. If we reach a valid solution, then our task might be over. On the other

hand, if we reach an invalid solution or an internal node that will not lead to any valid solution, we

take a step back and at the previous level of the tree we choose the next child.

Consider the following tree:

root

/ | \

A B C

/\ /\ /\

D E F G H I

The leaves denote the set of possible solutions to the problem. Let’s say that only G, H, and I are

valid solutions. Now, a backtracking algorithm would start from the root and visit the first child

(i.e. take a decision that represents a first step toward a solution). We might then already realize

that A would not lead to any valid solution. If that’s the case we would then backtrack, undoing

what we had done in the last step and getting back to the root node where we’ll then take the next

available choice that will lead us to node B. From B the next step will lead us to the leaf F which

does not represent a valid solution. We will then backtrack, undoing what we had done in the last

step and getting back to B where we can then take the next available choice. This will lead us to G

which happens to be a valid solution and hence we are done.

How can you apply this type of reasoning to solving a Sudoku? The idea would be the follow-

ing:

as long as there are empty cells in the grid

pick an empty cell and place a number in it

if a conflict occurs (i.e., at least one of the Sudoku rules is broken),

then remove that number and backtrack

if there are no conflicts, attempt to fill in the rest of the grid

if you were unable to fill the rest of the grid

then remove that number and backtrack

It is up to you to figure out how to code this idea into your program. I would highly suggest you

3

to spend some time solving a couple of Sudokus before starting to write your program. This will

allow you to better understand the problem at hand and think about possible steps you can take

to optimize your program. This project is much more open-ended than your previous assignments

and it leaves you the freedom to be more creative and try to bring together everything you have

learned throughout the semester.

Your Task

In the ChessSudoku class implement the method solve(). You can find additional information on

the method in the template code. Please feel free to add as many private helper methods/classes

as your see fit.

Testing and Evaluation

Your program will be tested on several classic Sudoku puzzles, as well as different variants of the

chess Sudoku puzzles.

Together with the template code, we provided you with a set of txt files representing different

Sudoku puzzles with different difficulties which you can use to test your program. Following the

same format you can create as many new puzzles as you like to further test your code. The puzzles

we’ll be using to grade your assignment will remain secret. Please note that the txt files should be

stored in the project folder of your program, and not the package folder, nor the src folder.

This is how we will evaluate your code:

+ 75% Your program finds a solution to 3x3 Sudoku puzzles in less than 10 seconds (assuming

they have a solution). The points awarded will be proportional to the number of puzzles from

the secret tests your code can solve.

+ 10% Your program find a solution to square puzzles up to 5x5 (assuming they have a solution).

+ 10% Your program has an additional feature that finds all possible solutions to a given puzzle.

This will involve continuing the search after the first solution is found (i.e., pretending that

solution doesn’t exist) to see if another solution can be found. All the solved Sudokus should

be correctly stored in the field named solutions.

last 5% The remaining 5% of the grade will be established based on your code’s ranking in a

tournament where each program will be given one minute to solve each Sudoku puzzle on our

computer. The ranking is established based on the number of Sudokus it succeeds at solving,

from a set of 10 problems ranging from very easy to very difficult.

4

学霸联盟