On slider puzzle projects with .NET collection classes: poster session

This poster presentation reports classroom experience using Sam Loyd's Sliding Tile Puzzle for student programming projects which use .NET collection classes both to store game tree nodes, and to support user and computer generated solutions to the puzzle. This project offers the students the opportunity to develop a non-trivial application, to design classes, to reuse data structures developed during the semester, and to leverage existing data structures including several of the .NET collection classes. The sliding tile puzzle has been used extensively for programming projects. A description of the puzzle and a discussion of its history can be found on several websites[1, 2]. The advantages of the puzzle for student projects is that the computational requirements of a module to find a computer-generated solution to a particular puzzle can be controlled by designating the difficulty of the puzzle; i.e., by creating a solvable puzzle by making random valid backwards moves from the original solution state. The students can first implement an application that allows users to solve the puzzle, and then try to develop their own heuristics for generating computer solutions. Then finding a computer solution can be guided by a directed search, such as a best-first search through the generated tree of game states, where the root is the initial tile configuration, and the fringes are the unexplored reachable states. This search requires the students to contain the generated node states in a structure that can be searched efficiently for a node with a particular state and that also allows for quickly finding the most promising state from among the unexplored fringe states. The students are given an outline of the A* search algorithm, and are led through a set of labs which result in a working but minimal version of the program. From this point they need to implement the module for computer solution, exploring various alternatives for storing both the open and closed lists and the implicit tree that is generated as the algorithm progresses. Naive data structure choices lead to implementations that can solve only simple puzzles, whereas using more sophisticated alternatives, if implemented correctly, give better results. Because the description of A* search discusses an open list, a closed list, and a game tree, students frequently start with a very literal interpretation of the algorithm and choose a linear container such as the .NET Collection class ArrayList or the templatized List . Most students quickly realize that if they keep their lists in sorted order they can use a binary search rather than a linear search for a particular element, thus speeding up solution execution. A major goal of the project is to have the students then replace their linear list with either a hashtable or with .NET's Dictionary class which takes two template parameters, one for the type of the item, and one for the type of the key. Using either a hashtable or an instance of the Dictionary class is best supported by implementing the IEquatable interface, in order to allow two different nodes in the game tree, which may have different costs and different parents in the tree but which represent the same tile configuration, to be considered equal. Another goal of the project is to have students use a priority queue to support quickly finding the most promising fringe node to explore next. A related challenge for the students is to link the priority queue with the other data structures, thus leveraging the use of reference variables and exploiting the advantages of both types of structures. Additional issues addressed in the project include file I/O, code instrumentation, using profiling for performance analysis, comparing algorithm analysis with timing results, and user interface design. The choice to develop in .NET lead to a language decision: the projects discussed here were developed in C#. However, the author has used this same project in previous semesters, combining Visual C++ with Standard C++ Library container classes. The poster will compare the two approaches, and will list advantages and disadvantages of each. The website www.codingquest.com lists resources used during the course and links to html-ized versions of the students' slider puzzle project presentations.