Automatically Generating Solutions for Sokoban Maps Public Deposited

http://ir.library.oregonstate.edu/concern/undergraduate_thesis_or_projects/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.
Resource Type
Date Available
Date Issued
Degree Level
Degree Name
Degree Grantor
Advisor
Committee Member
Non-Academic Affiliation
Keyword
Rights Statement
Language
Replaces
Additional Information
  • description.provenance : Submitted by Heather Boren (heather.boren@oregonstate.edu) on 2010-09-13T23:42:52Z No. of bitstreams: 1 Greco Honors Thesis.pdf: 516152 bytes, checksum: 003f7cd5ff4e6caeab21f1f86764830d (MD5)
  • description.provenance : Made available in DSpace on 2010-09-13T23:42:53Z (GMT). No. of bitstreams: 1 Greco Honors Thesis.pdf: 516152 bytes, checksum: 003f7cd5ff4e6caeab21f1f86764830d (MD5)

Relationships

In Administrative Set:
Last modified: 07/27/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items