sokoban-solver

COMS W4701 Artificial Intelligence
Fall 2013
Assignment 2: Sokoban Search Algorithm
James Hyun Seung Hong (hh2473)

Purpose

The purpose of this project is to solve a Sokoban puzzle using different search methods.

More information on Sokoban puzzle: http://www.sokobano.de/wiki/index.php?title=Main_Page

Implementation

Search methods that I have implemented are:

• Breadth-first search (http://en.wikipedia.org/wiki/Breadth-first_search)
• Depth-first search (http://en.wikipedia.org/wiki/Depth-first_search)
• Uniform-cost search (http://en.wikipedia.org/wiki/Uniform-cost_search)
• Greedy best-first search (http://en.wikipedia.org/wiki/Best-first_search#Greedy_BFS)
• A* search (http://en.wikipedia.org/wiki/A*_search)

For greedy and A* search algorithms, I used 4 different heuristic functions: - Manhattan distance (http://en.wikipedia.org/wiki/Taxicab_geometry) - Euclidean distance (http://en.wikipedia.org/wiki/Euclidean_distance) - Hungarian algorithm (http://en.wikipedia.org/wiki/Hungarian_algorithm) - Max{manhattan, euclidean, hungarian}

Hungarian algorithm is adapted from https://github.com/KevinStern/software-and-algorithms/blob/master/src/main/java/blogspot/software_and_algorithms/stern_library/optimization/HungarianAlgorithm.java

Instructions

.java files should be placed in same directory as img folder and examples folder for the program to locate the images properly.

Usage

To compile files:

cd src
javac *.java

To run the program:

java SokobanTester

Input

The Sokoban files must be in the following format:

[Number of columns]
[Number of rows]
[Rest of the puzzle]

Puzzle should be expressed using the following ASCII characters:

#   (hash)      Wall 
.	(period)	Empty goal 
@	(at)    	Player on floor 
+	(plus)		Player on goal 
$	(dollar)	Box on floor 
*	(asterisk)	Box on goal 

Output

The output is in the following format:

1. Search method used to solve the problem
2. Move solution (or fail message if no solution found)
3. Total number of steps taken
4. Number of nodes generated
5. Number of nodes containing states that were generated previously
6. Number of nodes on the explored list (if there is one) when termination occurs
7. The actual run time of the algorithm, expressed in milliseconds

The output is also printed out in the "Answer" section of the GUI frame.

Screenshots

Initial screen when the program starts. Select the search method from the left to start.

Select the search method and enter the file path with filename. If necessary, choose the heuristic method (only for greedy and A*).

When a user presses start, the output is printed in the "Answer" section of the GUI frame, which prints the solution steps and the puzzle. A step-by-step solution to the puzzle can be shown by pressing "Previous" or "Next" button.