代写data编程设计、代做Python，c++，Java程序

日期：2021-05-24 10:57

Matrix puzzle solver project

Introduction

This project is to build a system that provides a GUI for solving matrix puzzles. It is flexible

in what puzzles can be: they all use a matrix but they have different constraints or rules

that specify what values are in the matrix and what constitutes a solution.

The main parts of the project are to make an object oriented design, to implement a GUI

that allows a user to choose what puzzle to try and to use the GUI to solve it. And then

to write a solver for magic square and a solver for sudoku. You have to give a performance

analysis with empirical results for your solvers.

Detailed Requirements

This project requires you to do the following:

1. Produce an object-oriented design for matrix puzzle representation, the design

should allow for the following requirements.

o Represent a matrix puzzle type as an Abstract Data Type with an

independent internal data representation (e.g. as a vector, a single

dimensional array, a 2d array).

o Different values can be included in the puzzle (see below for the kinds of

puzzle we consider to represent – magic square, soduku, etc)

o Different constraints should be able to be set, these define the problem

that has to be solved “The Puzzle”. In magic square there are constraints

on the value of the sum of diagonals, rows, columns, in sudoku there are

constraints on the arrangement of the values 1-9 throughout the matrix

(see description below).

o Certain sets of allowable operations can be made to update the puzzle

to try to find a solution (e.g. swap values). Other operations include to get

a string representation, and to compare a solution is better or worse than

another one.

o You need to provide a documented class hierarchy that allows for

representing different kinds of matrix puzzle.

2. Implement GUI: your matrix puzzle representation and provide a graphical user

interface. Requirements:

o Allow a user to choose different previously stored puzzle types to use (e.g.

to play magic square, or to play sudoku).

o Display a puzzle matrix to a user.

o Allow a user to manipulate the puzzle and try to find a solution.

o Storage to save completed or in progress solutions to different puzzles to

a file and reloaded.

o Storage to save puzzle files – that is preconfigured

o You can either use a web based GUI app

3. Implement solver: You will implement a solver for Magic Square and Sudoku.

Requirements:

o There can be two types of solver – one for magic square and on for

sudoku.

o It is suggested to use evolutionary computation (e.g. genetic algorithms)

to implement your solver. Alternatives are with integer programming but

this is not recommended because will likely be too slow.

o The solver should generate a solution in a short amount of time.

? The magic square solver should solve a 20x20 magic square in less

than 5 minutes. Full marks will only be given if it can solve a 20

x 20 magic square in less than 1 second on average in 30 runs

on a standard laptop and 10 seconds for a 200 x 200 square.

? The Sudoku solver should be faster.

? Provide a table of results which show the results of a doubling

experiment in which you double the size of the problem and

measure the average time taken by the solver to find a solution

for (completed) runs of up to 1 hour each. Provide also a model

to estimate the time needed to solve much larger problems based

on these statistics.

o While the solver is running the GUI should not just be frozen, it should

update to show some progress (e.g. a partial solution)

o It should be possible for the user to stop the solver at any time during its

running and see the current best solution if the solver was taking too long.

o The user should also be able to start the solver to finish their current in

progress solution.

o Allow a user to set constraints on the values of certain elements in the

matrix. EG to add another constraint on the location of the value 1 to be

at index 1,1 in the matrix.

Runtime requirement: your solver should go from a square like this to the one below in

less than 1s.

Constraint requirement: The user should be able to fix some portions of the matrix such

as the 1-9 here, the final solution will respect the locations that are set (nb if the user

constraints result in an impossible to find solution it will still be possible for the user to

stop the program and see the current best result as is also required).

Format of the solver result table requirement:

N (Magic

square

size)

Runtime (average

of 30 runs)

5 0.9 +/- 0.05

10 2.1 +/- 0.01

20 3 +/- 0.01

40 4.01 +/- 0.5

This table shows an example of the result table that should be provided for each solver.

This example shows an example of the results that would be obtained if the algorithm

ran in O(lg n + 1). Your algorithm will most likely not do this, but see if you can provide

an estimate (see the textbook for further description of “doubling experiments”. The 95%

confidence intervals shown should be found from 30 test runs.

Magic Squares:

Magic squares are a square matrix arrangement of n x n integers from 1 to n squared.

They have an ancient heritage and here are some magic squares from ancient Chinese

civilizations:

The rules are constraints on the values that require that all rows, columns and diagonals

add up to the same value as shown here:

The size of the square can be any value.

Sudoku

Sudoku is another, related, type of matrix puzzle with different rules (constraints). The

objective is to fill a 9x9 grid with the numbers 1 – 9 so that each column, row and diagonal

contains all the digits 1 to 9. The square with 9 digits is placed in a grid of 6 3x3 grids (see

figure below). Each row, column, and diagonal in the larger grid also contains the values

1 – 9 as well (see figure below).

In Soduku, a partially filled board is provided by a puzzle setter, the solver has to place

the remaining values: (see picture below).