首页 >
> 详细

Sudoku [9 marks]

In these questions you will be working on writing code that will

solve Sudoku puzzles.

All these questions are part of the Core assignment, due in at the

deadline after reading week.

For the avoidance of doubt -- with the exception of the

SudokuSquareSet question, you may add extra #include and using

statements, if you need to.

Make sure you don't commit any compiled code to your GitHub

repository; or if you choose to use an IDE, any large project

directories created by your IDE. You can make these on your machine,

but don't commit or add them to your repository -- this isn't what

git is designed for.

a) Making a Sudoku board class

In the file Sudoku.h make a class Sudoku that holds an incomplete

Sudoku solution.

It should have a constructor that takes a single argument -- the size

of the board. For instance, for a 9x9 Sudoku, the constructor would

be given the value 9. Or, for a 16x16 board, the constructor would be

given the value 16.

You need to store the incomplete solution as a member variable. The

recommended way to do this, to start with, is to have a vector of

vectors (a square array), in which each square is represented as a

set

Initially, for a 9x9 Sudoku, if the grid is completely blank, each

set will contain the values {1,2,3,4,5,6,7,8,9}. When a square is

given some value, the set is cleared and replaced with a set

containing just that one value -- the other options are removed.

Write a function getSquare(int row, int col) that returns the value

in the cell in the square at the given row and column:

• If there is only one value in the set for that square, return

the number in that set.

• Otherwise, return -1 (a dummy value to indicate we don't know

what should be in that square yet)

b) Setting the value of a Sudoku

square

Write a function setSquare(int row, int col, int value) that sets the

value in the cell in the square at the given row and column, then

updates the sets of possible values in the rest of the grid to remove

choices that have been eliminated. For instance, if we put a '3' on a

given row, then nothing else on that row can have the value 3.

The implementation of setSquare is split into two parts.

First, the easy part: the set of possible values for that cell is

cleared, and value is inserted. This forces that cell to have that

value.

Then, a loop begins that does the following:

• Loop over the entire grid

• For each square that has only one value in it, remove that

value from the sets of possible values for:

o All the other squares on that row

o All the other squares in that column

o All the other squares in the same box. A 9x9 grid is

divided into 9 boxes, each 3x3: no two values in the same

box can have the same value. For larger grids (e.g.

16x16), the size of the box is always the square root of

the size of the grid.

If at any point the set of values for a square becomes empty, the

function should return false: it has been shown that there is no

value that can go in a square.

The loop should continue whilst values are still being removed from

the sets of possible values. The reason for this is that after

setting the given square, we might end up with only one option being

left for some other squares on the grid. For instance, if on a given

row some of the squares had the sets:

{3,4} {3,5} {4,5}

...and we call setSquare to set the middle square to have the value

3, then before the loop:

{3,4} {3} {4,5}

On the first pass of the loop, we would find the square containing 3

and remove this from the other sets on the row (and the other sets in

the same column and box). The row then looks like:

{4} {3} {4,5}

We then start the loop again, and find the square containing the

value '4'. This is removed from the other sets on the row (and column

and box) to give:

{4} {3} {5}

We then start the loop again, and find the square containing the

value '5'.

This process stops when, having looped over the board, and updated

the sets by removing values, our sets have stopped getting any

smaller. At this point the function returns true.

For simple Sudodu puzzles, this process here is enough to solve the

puzzle. No guesswork is needed: setting the squares of the board to

hold the initial values specified in the puzzle, is enough to cause

all the other squares of the board to have only one option left.

You can test this by compiling and running BasicSudoku.cpp:

g++ -std=c++11 -g -o BasicSudoku BasicSudoku.cpp

This calls setSquare for the values in a simple Sudoku puzzle; then

uses getSquare to check your code has the right answer.

c) Searching for a solution

For more complex puzzles, after putting in the initial values using

setSquare, some of the squares on the board have more than one value

left in their set of possible values -- using logic alone, we cannot

deduce what the value has to be; we have to make a guess and see what

happens.

For this, we are going to use the Searchable class. This is an

abstract class for puzzles, containing the following virtual

functions:

• isSolution(): this returns true if the puzzle has been solved.

For Sudoku, this means all the squares contain just one value.

• write(ostream & o): a debugging function to print the board to

screen.

• heuristicValue(): an estimate of how far the puzzle is from

being solved. We will return to this in part (d)

• successors(): in a situation where a guess is needed, this

returns several new puzzle objects, each of which corresponds

to a different guess having been made.

Make your Sudoku class inherit from Searchable, by changing the

opening of the class definition to class Sudoku : public Searchable

Implement isSolution() to only return true if the puzzle has been

solved; i.e. every set in every square is of size 1.

Implement a write() function to print the board. You can display the

board however you like. A reasonable implementation is to print out

the board one row at a time:

• If the square has more than one value in its set, print a space

character

• Otherwise, print the value from the set.

(I'm not marking write(), it is to help your debugging. If you want

to print nothing at all, that's fine.)

Implement successors() as follows:

• Make an empty vector of successors to return. This should be a

vector

联系我们

- QQ：99515681
- 邮箱：99515681@qq.com
- 工作时间：8:00-23:00
- 微信：codinghelp

- 代写dataset留学生作业、代做c/C++，Java编程设计作业、Pyth 2019-11-21
- Cache Comparisons作业代写、R程序语言作业调试、R实验作业代 2019-11-21
- Programming作业代做、代写c++课程设计作业、C++程序语言作业调 2019-11-21
- Data Programming作业代写、代做dataframe X作业、P 2019-11-21
- Cricos 00213J作业代做、代写it Systems作业、代写pyt 2019-11-21
- 代做r Hw2留学生作业、代写decision Making作业、代写r编程 2019-11-21
- Tcss 380作业代写、代做c++编程设计作业、代写c/C++实验作业、P 2019-11-21
- 代写program留学生作业、Java程序语言作业调试、Java实验作业代做 2019-11-21
- Csci-1200作业代做、Data Structures作业代写、代做py 2019-11-21
- 代写tunedit Data作业、代做python编程设计作业、代写pyth 2019-11-21
- Csci 370作业代写、代做java课程设计作业、Java程序语言作业调试 2019-11-21
- 代写comp 1010作业、Program留学生作业代做、代写python， 2019-11-21
- Wisccompsci200作业代做、Java编程设计作业代写、Java语言 2019-11-21
- 4Cosc001w作业代做、Python程序语言作业调试、Python课程作 2019-11-20
- 代写csc 230作业、代做ascii留学生作业、Python，Java程序 2019-11-20
- Cmpt 361作业代写、代做system留学生作业、Java，C++编程语 2019-11-20
- 代做cs5783留学生作业、代写machine Learning作业、代写c 2019-11-20
- B365留学生作业代做、代写iris Data作业、代做r程序语言作业、代写 2019-11-20
- Inft 3033作业代做、代写c/C++编程语言作业、代做c++课程设计作 2019-11-20
- Cs610-101作业代写、Programming课程作业代做、C/C++, 2019-11-20