讲解 program、Python设计编程辅导
The aim of this practical is to model a puzzle game called ‘Stitch’ as a MIP problem, using the linprog
function in scipy. We will then extend our MIP model to produce new ‘Stitch’ puzzles. You will also
provide a report, intended to be read by a non-specialist audience, to show how your submission works,
and to discuss how MIP is useful in practice.
‘Stitch’ is a puzzle game, where the target is to fill in a grid with coloured rectangles.
The puzzle is given as an grid (some levels of the game are not a grid, but for this practical we
will only consider grids). A level is completed by filling the grid with rectangles.
Some locations in the grid contain a number. Each number must be contained in a rectangle made from
that many squares, and each rectangle must contain exactly one number.
For example, here is an example puzzle
2
2 2
3
Here is the solution to this puzzle:
2
2 2
3
Notice that each rectangle contains one number, and the ‘2’s are in a rectangle made from two squares,
and the ’3’ is in a rectangle made from 3 squares.
Here is another, larger puzzle:
6 6
4
and its solution:
Operational Research Practical 2 - Stitch (v1.0)
Overview
Introduction
n × m6 6
4
Again, there is one number in each rectangle, which gives the size of the rectangle.
For this practical, we will use a standard format for writing these puzzles, where we give the width,
height, number of blocks, and then the location of each of the numbers (the blocks can be given in any
order). The square at location startx[i] and starty[i] contains the number blocksize[i] . We will
refer to this as the ith block. For these two levels the format is:
and
Here is one larger level (solved), along with its representation in our format:
data = {
"width": 3,
"height": 3,
"numblocks": 4,
"startx": [0, 1, 2, 0],
"starty": [0, 1, 1, 2],
"blocksize": [2,2,2,2]
}
data = {
"width": 4,
"height": 4,
"numblocks": 3,
"startx": [0,3,0],
"starty": [0,0,3],
"blocksize": [6,6,4]
}This practical has 2 coding parts. Submit at least one Python program for each part. Your code should
include comments to explain any potentially confusing parts:
1. Implement the game as MIP.
2. Make new interesting levels of the game.
You should also submit a report. Your report should be written as a report for a company that develops
puzzle games.
Your report should be written in size 12 font:
• Explain how you implemented Part 1 and Part 2 (including any extensions) using Mixed Integer
Programming (MIP) in a way suitable for a non-expert.
• Discuss what kind of other problems the company could solve using MIP, and how MIP could
provide value to the company (you do not have to model any further problems in MIP). This part of
your report should be 2ritten for a non-specialist audience and be no longer than 1 page.
data = {
"width": 8,
"height": 14,
"numblocks": 15,
"startx": [7,4,2,6,3,5,1,4,0,7, 3, 2, 5, 6, 4],
"starty": [0,1,2,2,3,3,4,7,8,9,10,11,11,12,13],
"blocksize": [8,7,4,10,2,8,11,7,12,12,7,9,3,5,7]
}your report should be 2ritten for a non-specialist audience and be no longer than 1 page.
Coding Part 1
You can implement the game in MIP in any manner you prefer, this part will guide you through one
possible route. We will use the following main variables (and booleanisations of them, if you need them).
• A grid of domain , where if grid
location is part of the th block, and a booleanisation of .
• Variables to represent the location of each of the rectangles. A rectangle can be
represented by an x&y co-ordinate for it’s lower-left position, a width and a height, for example.
To begin, write small MIP programs which implements the following constraints. You may submit your
implementation of these building blocks if you have trouble modelling the whole puzzle, to show your
progress, but otherwise you do not need to submit them.
1. The width and height of block[i], multiplied together, are blocksize[i].
2. If Mb[i,j,k] is 1, then the location i,j is inside block k (as represented by it’s x&y co-ordinate, width
and height, or however else you represented).
Ensure you test these building blocks carefully. You can test by write a function to build a model, and
then add extra constraints to force variables to be a given value, and see if the model has a solution.
Hint: When you put together your full solution, if these parts are not right, you are likely to just get told
‘no solution’, and it will be hard to figure out why, so be sure they work!
Use the functionality you built in part A to write a complete solver for Stitch in MIP.
You should convince yourself that the constraints you built in Part 1, along with setting the ‘startx,starty’
locations to the approriate block, is sufficient to force the solutions to the puzzle.
Hint: Write some simple levels to check your implementation, such as a 1x1 level with just one block,
and a 2x1 level with two 1x1 blocks.
Submit your implementation of ‘Stitch’, which can be given any level, and any levels you created for
testing.
Coding Part 2
Now we can solve existing levels of the ‘stitch’ puzzle, we will create new ‘Stitch’ levels.
Your model for creating ‘stich’ level should assume you are still given ‘width’, ‘height’, and ‘numblocks’,
as specified in the puzzle specification. Change your model so that the arrays ‘startx’, ‘starty’ and
A - Important Building Blocks
M[height, width] {0, 1,… , numblocks − 1} M[i, j] = k
i, j k Mb[height, width, numblocks] M
numblock
B - Modelling ‘Stitch’‘blocksize’ are variables which can be assigned by the MIP solver.
Now when you solve the puzzle, you should get values for ‘width’, ‘height’, and ‘numblocks’, and also
the solution to the puzzle.
Hint: Depending on how your original model works, you may need to add some extra constraints on
‘width’, ‘height’ and ‘numblocks’ to ensure the puzzles are correct. Try generating some puzzles and
seeing if the solutions make sense.
Extension: While you can now make levels, you may find the levels are not very interesting (for example,
they all look very similar, and are not interesting to play). Investigate how you can make more
interesting levels, by adding new constraints, and changing the optimisation function. Discuss what you
consider to be ‘interesting’, and how you implemented that.
You should submit a zip file containing:
• Your code for parts A and B (submit seperate code for both parts), and any other files (including
levels you created)
• Your report, non-specialist audience
One grade point per day late (meaning if a submission is one day late and marked as a C2, it will receive
a C3 grade). A day is defined as each 24-hour period following the submission deadline, including
weekends and holidays. Assignments submitted more than 5 days after the agreed deadline will receive
a zero mark (AB).
You are allowed to use AI in this assignment only for:
• General Python questions
• Help improving your grammar or writing structure of the report.
You must be transparent in acknowledging, describing and referencing how you have used AI. This must
be included in a use of AI declaration at the end of your report. Failure to do so is academic misconduct.
Plagiarism means using someone else’s work without giving them proper credit. In academic writing,
plagiarising involves using words, ideas, or information from a source without citing it correctly. You
must provide full citations in the references for all sources used in this assignment. Failure to do so is
academic misconduct.
See the policy at: https://www.dundee.ac.uk/corporate-information/code-practice-academicmisconduct-students
to learn more about academic misconduct and the punishments for committing
these offences.
Handin Method
Penalty for Late Submission
Academic Misconduct• Code 60%
◦ Implement solving an existing stitch level 20%
◦ Implement a basic puzzle creator for stitch levels 20%
◦ Implement interesting puzzle creator for stitch levels 20%
• Report 40%
◦ Report explains your MIP models 20%
◦ Report explaining how MIP could be used by a puzzle game company 20%
Marking Criteria: