Solving the Water-Sort-Puzzle Learning objective: Development of a complex, modular program with GUI Content: Class modelling of the game-state, techniques to structure the task into modules and operation, using a predefined class library, extended functionality in sequence processing, elementary graph search algorithms, building a graphical display using 'tkinter' The Water-Sort-Puzzle Water-Sort-Puzzle is a fun and addictive puzzle game. The objective is to sort segments of colored water in the glass tubes until all colors are in the same glass by filling a segment of color from one glass into another. A challenging problem when the number of tubes and colors increases. JUTU Figure 3: Start of game given a color configuration in 4 tubes Figure 2: After moving color pink from first tube to second The student's task is to write a Python computer program that solves this puzzle. The solution is a sequence of moves filling color from one tube into another. JUJU Figure 1: The target configuration to be achieved Defining a space of states Represent this problem in terms of states and transitions. In our case, each state represents the configuration of the colors within the water tubes. Define a suitable class whose objects describe such a game state. Use immutable objects. So, a state cannot be changed and care must be taken by defining the equal operation and corresponding hash-calculation (see example in figure 4). UUUU Figure 4: These two game states should be regarded to be equal The coding of colors can be done in many ways. But keep in mind: the colors are enumerable. The arrangement of colors as stack within a single tube and several tubes side by side result in a two-dimensional data-structure to represent a color configuration. Again, there are many possible ways to realize this; I don't want to see just one implementation copied by all students. Implementing possible moves of a game state The moves - filling colored water from one tube into another change the color configuration. A move is a transition from one state to another state. The complete state space of this game can be represented by a graph whose vertices are the states and the directed edges are the possible moves. www www Start wwww www wwww www www www www Goal Figure 5: A complete graph given a start state and all transitions towards a goal Identify all possible moves or transitions from the current state (parent) to neighbouring states (children). In the context of the water-sort-puzzle, this means generating all valid moves that can be applied to the current tube configuration. Searching for a solution used to find a solution. The solution is a sequence of transitions Common graph search algorithms can from state to state that begins in start state and ends in the goal state. Two search methods are already implemented: breadth first search (BFS) and depth first search (DFS). Only BFS obtains an optimal solution that means: you reach the goal in a minimum number of transitions. But complex games can only be solved by DFS. To use these search functions your class of a game state must implement some operations - see given code snippets in 'state.py". Graphical display of states A graphical display of a game state is also already implemented and can be used within your Python projects. The display class is based on a 'tkinter' Canvas (see example in this document). Also, a main program exists that shows a solution step by step. To use this display class your state class must provide some elementary operations to access the color configuration. The display is so far limited to 16 different colors. Your Task Compulsory part: You have to implement the missing operations of class state and combine all parts into a running main application that shows the solution of any game. Write a test module that tests your state implementation. Improve the main module that the parameters of the game (number of tubes and colors) should be adjustable by command line arguments in the following way: >>> watercolor tubes-12 colors-10 size-5 Currently these parameters are fixed as constants within the main program. Freestyle part: If you are aiming for an A grade you should do some more, e.g. one of these: Improve the searching algorithm by implementing some heuristics that informed search strategies can be used (like A*), or improve the main GUI so that the game parameters can be selected by graphical input, or add some interactive elements that the game can be played by a user too, or animate a move using a physical simulation of filling water from one tube into another (difficult), or any other additional functions related to the water-sort-puzzle.