辅导data编程设计、讲解Python，c++，Java程序
- 首页 >> Python编程 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).
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).