This part of the assignment is concerned with the sizes of state spaces for search problems. The so-called "combinatorial explosion" can manifest itself in a variety of ways. Understanding how some states may be double counted by simple enumeration techniques can be important in applying state-space search. For example, if a large proportion of states get double counted, it may be worth implementing functionality to eliminate the double counting.

1. "Tic-Tac-Toe" (5 points)

   How many distinct states are possible in a game of Tic-Tac-Toe after 7 moves have been made (4 Xs and 3 Os)? Consider two states to be distinct even if rotating the board by 90 degrees or 180 degrees, or flipping the board vertically or horizontally, turns one state into the other. However if the same arrangement of the board can be reached by multiple move sequences, still consider that to be just one state. In this exercise, ignore the fact that the game should end as soon as a player gets three in a row; if X's first three moves result in three in a row, X still plays a fourth move.

2. "Tric-Trac-Toe" (10 points)

   Let us define the game of Tric-Trac-Toe as a game for 3 players, X, Y, and Z. The object is to get 3 in a row. However, they play on a 3D board that is 4 by 4 by 4. They take turns in a round-robin protocol. Give an expression for the number of distinct states that can be achieved after 6 moves and evaluate it to a number. Such a state should have 2 X's, 2 Y's, and 2 Z's on the board, filling six of the 64 available voxels. You may assume that 2 states are distinct even if one can be matched to another by some rotation of the cube.

3. Husky Paperweights (Optional, for 5 points of extra credit)

   The Husky Paperweight Company sells a line of paperweights that come in the following sizes: 3 cm by 3 cm, 5 cm by 5 cm, 7 cm by 7 cm, etc. Thus a typical paperweight is of size n by n, measured in centimeters. Its design is an array of purple and gold squares each of size 1 centimeter on a size. The underside is just black felt, with no pattern.

   The company promotes the paperweights by explaining how great a variety of patterns they come in, because the arrangements of purple vs. gold in the grid positions are more or less random. Give a formula for the number of distinct paperweights having size n by n. This formula should consider the possibility of various symmetries and double-counting situations, and it should not do any double counting.

   Hints: (1) patterns with 4-way (90-degree) rotational symmetry are not double counted; patterns with 2-way (180-degree) rotational symmetry, but not 4-way symmetry, are double counted; other patterns are quadruple counted. (2) try working out all the patterns for n=1 and some of the patterns for n=3 and use those as a check on your formulas.

1. Breadth-First Search (10 points).

   Using ItrDFS.py as a guide, and starting from the skeleton code ItrBreadthFS.py that uses breadth-first search rather than depth-first search to solve the Tower of Hanoi puzzle. Show the states on a shortest solution path for the Towers of Hanoi puzzle with 4 disks. Hint: the path should have length 15.

2. Basic 8 Puzzle Formulation (25 points).

   Create a file BasicEightPuzzle.py that provides the same kinds of problem elements that the TowerOfHanoi.py file provides: metadata, initial state, operators, and a few utility functions for states, including __hash__() and __eq__(s), as well as __copy__() and the __str()__ function. The first two of these will allow your state objects to be used as keys in dictionaries, and the third gives a way to construct deep copies. The last one controls how your states will appear when the print function is called on them.

   Here is some additional explanation of these methods. __hash__() returns an int representing the result of a hash function on the state object. __eq__(s) returns True if the object is equal to another object given by s. __copy__() returns a deep copy of the state object. __str__() returns a string the represents all the important details of the state object.

   # goal:
   CREATE_GOAL_STATE = lambda: State([0, 1, 2, 3, 4, 5, 6, 7, 8])
   

   Show that it (Breadth-First Search) can solve some easy instances of the puzzle, such as instances requiring only three or four moves. Here are four instances to try. Note that puzzle0 is the most trivial version possible.

   # puzzle0:
   CREATE_INITIAL_STATE = lambda: State([0, 1, 2, 3, 4, 5, 6, 7, 8])
   # puzzle1a:
   CREATE_INITIAL_STATE = lambda: State([1, 0, 2, 3, 4, 5, 6, 7, 8])
   # puzzle2a:
   CREATE_INITIAL_STATE = lambda: State([3, 1, 2, 4, 0, 5, 6, 7, 8])
   # puzzle4a:
   CREATE_INITIAL_STATE = lambda: State([1, 4, 2, 3, 7, 0, 6, 8, 5])
   

3. A-Star Implementation (20 points).

   Implement an A* search program using the skeleton code in AStar.py that, like ItrDFS.py, will accept as a command-line argument the name of a problem template such as EightPuzzle but also accepts (a) the name of a heuristic evaluation function to use in the AStar search and (b) the name of a puzzle instance file that contains a particular initial state. For example

   python3 AStar.py EightPuzzleWithHeuristics h_euclidean puzzle2a.py
   

   The contents of puzzle2a.py would have this form:

   CREATE_INITIAL_STATE = lambda x: [3, 1, 2, 4, 0, 5, 6, 7, 8]
   

   The AStar.py program imports a priority-queue module that is available here (updated Oct. 20 at 4:03). It uses a package called heapdict, available here.
4. Implementing and Comparing Heuristics (30 points).

   Implement four heuristic evaluation functions for the 8 Puzzle: h_euclidean(s), h_hamming(s), h_manhattan(s), and h_custom(s). The first should compute the euclidean distance for each tile from its location in state s to its location in the goal state. Then it should add up these distances and return that sum. The second function should determine the number of tiles that, in state s, are not where they should end up in the goal state. The third function should find, for each tile, how many rows it is away from its goal state row plus how many columns it is away from its goal state column, and it should add those distances for each of the tiles. When computing these distances, include the empty square as if it were a virtual tile (tile number 0). The fourth heuristic is one that you should design yourself. You should design it to be admissible. Ideally, it will outperform the others. However, it might simply offer a variation or combination of the others.

   Include these in a new version of your 8 puzzle formulation: EightPuzzleWithHeuristics.py. Define the actual functions at the end of the COMMON-CODE section, but create new couple of lines of code at the end of the file as follows.

   HEURISTICS = {'h_euclidean': h_euclidean, 'h_hamming':h_hamming,
       'h_manhattan':h_manhattan, 'h_custom':h_custom}
   

   Compare the performance of these heuristics on each of the example puzzles (given below). For each puzzle-heuristic pair, report whether the puzzle was successfully solved and also report the count of states processed (taken off of OPEN and put on CLOSED). Put this information into a table. If it takes more than 30 seconds to solve a particular problem with a particular heuristic then note that; you may abort such runs.

puzzle10a.py:
CREATE_INITIAL_STATE = lambda: State([4, 5, 0, 1, 2, 3, 6, 7, 8])

puzzle12a.py:
CREATE_INITIAL_STATE = lambda: State([3, 1, 2, 6, 8, 7, 5, 4, 0])

puzzle14a.py:
CREATE_INITIAL_STATE = lambda: State([4, 5, 0, 1, 2, 8, 3, 7, 6])

puzzle16a.py:
CREATE_INITIAL_STATE = lambda: State([0, 8, 2, 1, 7, 4, 3, 6, 5])

Turn in a file A3-PartI.txt and all the files that you create for Part II. Your A3-PartI.txt file should contain your name and the answers to the questions in Part I. Your Python files for Part II should begin with a multiline string that gives, on the first line, your name and UWNetID.

Postponed the deadline to Sunday at midnight, and made a new priority queue module available (Oct 20).

Adjusted the format of the code that creates new states (Oct 17) to be consistent with the new state implementations that use a class State.
Added "(Breadth-First Search)" in "Show that it can solve" to clarify what should be doing the solving there. (Oct. 15).
If necessary, additional updates and corrections will be posted here and/or mentioned in class or on GoPost.

After submitting your solution, please answer this survey