Java代写 | COSC 1285 / COSC 2123   Assignment 2: Solving Sudoku  

本次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 first 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 filled 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 filled in  
with discrete values from 1-9. Sudoku puzzles have some of these cells pre-filled with  
values, and the aim is to fill 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-filled in. After filling 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 first 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 different 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 find 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 first 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 {i1, i2, i3, i4, i5, i6}, and the following subsets  
of 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
i1 i2 i3 i4 i5 i6  
{
i1, i3}  
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 {i2, i3, i4} and {i1, i5, i6}, we have the resulting submatrix:  
i1 i2 i3 i4 i5 i6  
{
{
i2, i3, i4}  
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].com  微信:itcsdx


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

blank

发表评论