Project 2:
Problem Formulation in Python

CSE 190D, University of Washington, Spring 2017


 

Overview

This project should be done in partnerships of two. You should first form a partnership with another member of the class. Then arrange to meet and/or communicate by email at certain times to coordinate progress on this project.

You will then choose a particular problem from a list of suggested problems. However, you may suggest an alternative problem and get clearance from the instructor to base your work around that problem.

Purposes

There are two main purposes for doing this project. First is to get more practice with the Python language, and whatever IDE or editor you may be using with Python. The second purpose is to develop some feeling for the process of "operationalizing" a problem -- creating something that a user (a solver) can actually operate and do something with.

Choosing a Problem

This project focuses more on the coding phase of problem formulation rather than pre-formulation or posing. Consequently, you should choose a fairly well-defined problem or define something yourself that is simple. Here is a list of suggestions.

  1. Instant Insanity. This is the 4-cube puzzle that requires arranging a given set of colored cubes into a tower such that on each of the four sides of the tower, there is one face of each of the four colors.
  2. Rubik's Cube. This is well-known. It's not the easiest puzzle to formulate, but some teams may wish to try it.
  3. "Single-player Tic-Tac-Toe". This is not a standard puzzle or game, but you can make up the rules. One approach would be to have the single player play X's and O's in alternating turns, except that the objective is to maximize a score by creating patterns, rather than simply getting three in a row. For example, each occurrence of the pattern XOX in any direction might be worth 5 points, and each occurrence of a 2x2 block of Os might be worth 10 points, etc.
  4. A simple linear equation solving problem. Each state will be a formula such as "3 + 7 - 2*x = 0". The operators might be "subtract 3 from both sides", or "divide both sides by 2", etc. Rather than having operators for every possible value, limit the values to potentially relevant ones or ones that depend on the formula: "subtract the first constant from both sides." Etc.

Formulation of the Problem

First develop a formulation that can be operated using the Text_SOLUZION_Client.py program. You can debug your state representation and your operators here, in a relatively efficient manner.

Then create a version that works with the BRIFL framework, specifically, the Flask_SOLUZION_Client_Server.py program. Ideally, this will have an SVG visualization that makes the user experience somewhat nicer than the textual interface does.

Description File and Turn-in

Create a file P2-Description.pdf that answers the following questions. (1) What is the problem you have formulated? If this is not a well-known problem, explain what the problem is and any rules you have made up. (2) What is your state representation and why? (3) What operators do you provide? Did you face a choice when you designed your operators, and if so, what is another possibility that you considered? Why did you go with the choice you made? (4) Did you provide a visualization in your formulation? Briefly, how does that work? (5) Describe how you and your partner divided up the work of the project. (6) Describe any particular challenges you had with this project.

Submit your code files and description file via Catalyst CollectIt.

Files needed: 

your problem formulation file, named appropriately.
your visualization file, named appropriately.
P2-Description.pdf