本次Java代写是解决数独算法问题

Algorithms and Analysis COSC 1285 / COSC 2123

Assignment 2: Solving Sudoku

Objectives

There are three key objectives for this assignment:

•

•

•

Apply transform-and-conquer strategies to to solve a real application.

Study Sudoku and develop algorithms and data structures to solve Sudoku puzzles.

Research and extend algorithmic solutions to Sudoku variants.

3

Introduction and Background

Sudoku was a game ﬁrst popularised in Japan in the 80s but dates back to the 18th

century and the “Latin Square” game. The aim of Sudoku is to place numbers from 1

to 9 in cells of a 9 by 9 grid, such that in each row, column and 3 by 3 block/box all

9

digits are present. Typical Sudoku puzzle will have some of the cells initially ﬁlled in

with digits and a well designed game will have one unique solution. In this assignment

you will implement algorithms that can solve puzzles of Sudoku and its variants.

Sudoku

Sudoku puzzles are typically played on a 9 by 9 grid, where each cell can be ﬁlled in

with discrete values from 1-9. Sudoku puzzles have some of these cells pre-ﬁlled with

values, and the aim is to ﬁll in all the remaining cells with values that would form a valid

solution. A valid solution (for a 9 by 9 grid with values 1-9) needs to satisfy a number of

constraints:

1

2

3

4

. Every cell is assigned a value between 1 to 9.

. Every row contains 9 unique values from 1 to 9.

. Every column contains 9 unique values from 1 to 9.

. Every 3 by 3 block (called a box) contains 9 unique values from 1 to 9.

As an example, consider Figure 1. Figure 1a shows the initial Sudoku grid, with

some values pre-ﬁlled in. After ﬁlling in all the remaining cells with values that satisfy

the constraints, we obtain the solution illustrated in Figure 1b. As an exercise, check

that every row, column and 3 by 3 block/box (delimited by bold black lines) satisfy the

respective constraints.

(

a) Puzzle.

(b) Solved.

Figure 1: Example of a Sudoku puzzle from Wikipedia.

For further details about Sudoku, please visit https://en.wikipedia.org/wiki/

Sudoku.

Killer Sudoku

Killer Sudoku puzzles are typically played on 9 by 9 grids also and have many elements

of Sudoku puzzles, including all of its constraints. It additionally has cages, which are

subset of cells that have a total assigned to them. A valid Killer Sudoku must also satisfy

the constraint that the values assigned to a cage are unique and add up to the total.

Formally, a valid solution for a Killer Sudoku of 9 by 9 grid and 1-9 as values needs

to satisfy all of the following constraints (the ﬁrst 4 are the same as standard Sudoku):

1

2

3

4

5

. Every cell is assigned a value between 1 to 9.

. Every row contains 9 unique values from 1 to 9.

. Every column contains 9 unique values from 1 to 9.

. Every 3 by 3 block/box contains 9 unique values from 1 to 9.

. The sum of values in the cells of each cage must be equal to the cage target total

and all the values in a cage must be unique.

2

As an example, consider Figure 2. Figure 2a shows the initial puzzle. Note the cages

are in diﬀerent colours, and in the corner of each cage is the target total. Figure 2b is the

solution. Note all rows, columns and 3 by 3 blocks/boxes satisfy the Sudoku constraints,

as well as the values in each cage add up to the target totals.

(

a) Puzzle.

(b) Solved.

Figure 2: Example of a Killer Sudoku puzzle. Example comes from Wikipedia.

Sudoku Solvers

In this assignment, we will implement two families of algorithms to solve Sudoku, namely

backtracking and exact cover approaches. We describe these algorithms here.

Backtracking

The backtracking algorithm is an improvement on blind brute force generation of solu-

tions. It essentially makes a preliminary guess of the value of an empty cell, then try

to assign values to other unassigned cell. If at any stage we ﬁnd an empty cell where it

is not possible to assign any values without breaking one or more of the constraints, we

backtrack to the previous cell and try another value. This is similar to a DFS when it

hits a deadend, if a certain branch of search tree results in an invalid (partial) Sudoku

grid, then we backtrack and another value is tried.

Exact Cover

To describe this, we ﬁrst explain what is the exact cover problem.

Given a universe of items (values) and a set of item subsets, an exact cover is to select

some of the subsets such that the union of these subsets equals the universal of items (or

they cover all the items) and the subsets cannot have any overlapping items.

For example, if we had a universe of items {i

_{1}, i_{2}, i_{3}, i_{4}, i_{5}, i_{6}}, and the following subsetsof items: {i , i }, {i , i , i }, {i , i , i }, {i , i } and {i }, a possible set cover is to select

1

3

2

3

4

1

5

6

2

5

6

{

i , i , i } and {i , i , i }, whose union includes all 6 possible items and they contain no

2 3 4 1 5 6

overlapping items.

The exact cover can be represented as a binary matrix, where we have columns (rep-

resenting the items) and rows, representing the subsets.

For example, using the example above, we can represent the exact cover problem as

follows:

3

^{i}1 i

_{2 }i

_{3 }i

_{4 }i

_{5 }i

_{6 }

{

i

_{1}, i_{3}}1

0

1

0

0

0

1

0

1

0

1

1

0

0

0

0

1

0

0

0

0

0

1

1

0

0

0

1

0

1

{

{

i , i , i }

2

3

4

i , i , i }

1

5

6

{

i , i }

2

5

{

i }

6

Using the above matrix representation, an exact cover is a selected subset of rows,

such that if we constructed a sub-matrix by taking all the selected rows and columns,

each column must contain a 1 in exactly one selected row.

For example, if we selected {i

_{2}, i_{3}, i_{4}} and {i_{1}, i_{5}, i_{6}}, we have the resulting submatrix:^{i}1 i

_{2 }i

_{3 }i

_{4 }i

_{5 }i

_{6 }

{

{

i

_{2}, i_{3}, i_{4}}i , i , i }

0

1

1

0

1

0

1

0

0

1

0

1

1

5

6

**程序代写代做C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！

**E-mail:** [email protected] **微信:**itcsdx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。