Automatically Generating Solutions for Sokoban Maps

Honors College Thesis

Public Deposited

Citeable URL: https://ir.library.oregonstate.edu/concern/honors_college_theses/9g54xk71g

Descriptions

Attribute Name	Values
Creator	Greco, Jason Aaron
Abstract	Generating solutions to Sokoban levels is an NP-hard problem that is difficult for even modern day computers to solve due to its complexity. This project explores the creation of a Sokoban solver by eliminating as many potential moves as possible to greatly limit the overall search space. This reduction is achieved through abstracting out moves that don’t involve a box push and also through removing any deadlocked states where the problem is in a state that makes it unsolvable. The result is a Sokoban solver that shows substantial improvement over a standard exhaustive approach.
License	All rights reserved
Resource Type	Honors College Thesis
Date Available	2010-09-13T23:42:53+00:00
Date Issued	2010-08-19
Degree Level	Bachelor's
Degree Name	Honors Bachelor of Science (H.B.S.)
Degree Field	Computer Science
Degree Grantor	Oregon State University
Commencement Year	2011
Advisor	Fern, Alan
Committee Member	Bailey, Mike
Non-Academic Affiliation	Oregon State University. Honors College
Rights Statement	In Copyright
Publisher	Oregon State University
Peer Reviewed	No
Language	English [eng]
Replaces	http://hdl.handle.net/1957/18381

Parents:

This work has no parents.

In Collection:

Thumbnail	Title	Date Uploaded	Visibility	Actions
	Greco_Honors_Thesis.pdf	2017-07-29	Public	Download