Abstract

Usage and demonstration of the performance and effectiveness of essential data structures, generics, collections, and elementary sorting algorithms

Table of Contents

Resources

Programming Assignment

There are a few micro optimizations available to bring the score up from 98 to 100 but I decided not to pursue them at this time.

Board

Implemented Manhattan and Hamming priority functions to support the A* algorithmic implementation of the solver class. In addition, I created a twin to determine the solvability of a board and a neighbors function to assist, again, with the A* implementation.

Solver

Solver utilizes a Minimum Priority Queue coupled with a SearchNode internal class with a priority (utilized in compareTo) function based on the path cost (moves thus far) and a heuristic (Manhattan with hamming as the tie breaker) to implement the A* algorithm. Solvability was determined by making a twin of the game board and concurrently solving both boards.

Results

Priority Queues Grade

Solver Test

Board Test