Thank God You aren’t a Math Major
For those of you who are curious as to why I haven’t posted anything during the last few days, here’s the reason.
Name: Sliding Puzzle Madness
Problem Definition: Solve an n x p rectangular sliding puzzle, where n and p are integers such that n > 1 and p > 1.
Goals: Alert the user if a puzzle is invalid or unsolvable. Use graphics to redisplay the puzzle after each move.
Sources of Information: The user will enter a two-dimensional n x p array of the integers 1, 2, …, (n x p) – 1 in a random order to represent a rectangular sliding puzzle game board (the blank space will be denoted by nil). This will be done at the command line.
Solution Strategy:
Step (1)
Test to see if the puzzle is valid. All indices must contain either nil or an integer value i such that 1< i < (n x p) – 1. Moreover, the puzzle must not include duplicates of any value, including nil.
Step (2)
If the puzzle is valid, then test to see if it is solvable. String the rows together as a list such that each row is appended to the end of the previous row. Use a recursive algorithm to select the first unselected index (until there are no more unselected indices) and then count the number of proceeding indices containing values less than that contained by the now selected index (ignore the index containing nil). Add these counts together to obtain the number of inversions (pairs of indices a and b such that a precedes b, but the value of a is greater than that of b). If p is odd, and the number of inversions is even, then the puzzle is solvable. If p is even, and the blank space is positioned on an even row in the original puzzle, and the number of inversions is odd, then the puzzle is solvable. If p is even, and the blank space is positioned on an odd row in the original puzzle, and the number of inversions is even, then the puzzle is solvable. In all other cases, the puzzle is unsolvable.
Step (3)
If the puzzle is solvable, then use a hill-climbing search with a look-ahead of ten moves to find a relatively efficient solution path. Expand the game-tree to a depth of ten levels, assigning each node a heuristic value immediately upon generation. If any node has a heuristic value of zero, stop the expansion process and move from the game-tree’s root to that node (recording each intermediate move). Otherwise, move from the game-tree’s root to the leaf node whose heuristic value is lowest (recording each intermediate move; if two or more leaves have equal heuristic values, then choose the first one). Repeat Step (3) until a solution path is found, using this leaf-node as the root of the new game-tree.
Step (4)
Utilizing graphics, display each intermediate move recorded in Step (3). This will allow the user to visualize the solution path.
Individual Responsibilities: This is not applicable because I am working alone.
Therefore, if you’re having difficulties counting your blessings, start by thanking God you aren’t a math major.
