Automatically Generating Solutions for Sokoban Maps Public

http://ir.library.oregonstate.edu/concern/honors_college_theses/9g54xk71g

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • 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
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Field
Degree Grantor
Commencement Year
Advisor
Committee Member
Non-Academic Affiliation
Rights Statement
Publisher
Peer Reviewed
Language
Replaces
Additional Information
  • description.provenance : Submitted by Heather Boren (heather.boren@oregonstate.edu) on 2010-09-13T23:42:52ZNo. of bitstreams: 1Greco Honors Thesis.pdf: 516152 bytes, checksum: 003f7cd5ff4e6caeab21f1f86764830d (MD5)
  • description.provenance : Made available in DSpace on 2010-09-13T23:42:53Z (GMT). No. of bitstreams: 1Greco Honors Thesis.pdf: 516152 bytes, checksum: 003f7cd5ff4e6caeab21f1f86764830d (MD5)

Relationships

Parents:

This work has no parents.

Last modified

Downloadable Content

Download PDF

Items