Jump to content


Photo

Solving 5 X 5 Sliding Puzzle


  • This topic is locked This topic is locked
2 replies to this topic

#1 Tuz

Tuz

    GMC Member

  • New Member
  • 106 posts

Posted 26 March 2010 - 12:29 AM

Is there any reasonable way to code gamemaker program that can solve randomized 5 x 5 sliding puzzle step by step?
I mean puzzle like this (its 4 x 4 i know)
Posted Image
i herd somewhere that a-star algorithm can be used somehow with this but i have no idea how..

any tips? :think:
  • 0

#2 OpticalLiam

OpticalLiam

    GMC Member

  • New Member
  • 782 posts

Posted 26 March 2010 - 01:07 AM

The classic way to solve a sliding puzzle is by using a state-based search. You represent the grid as a state, define the possible operations (e.g. slide left, slide right...) and then generate all of the successors of the state (by applying all of the operators in all possible ways) and then generate the successors of those and so on until you find a goal state. Then to find the solution you must backtrack up the tree. This could be done in GM, but would end up be pretty slow (especially for a 5x5) unless you heavily optimise (use A* and things like alpha-beta pruning for example).

Edited by OpticalLiam, 26 March 2010 - 01:09 AM.

  • 0

#3 brac37

brac37

    GMC Member

  • GMC Member
  • 808 posts
  • Version:GM7

Posted 27 March 2010 - 02:43 AM

The 4x4 has 653837184000*16 positions. That is more than the number of bits in your computer's memory. Writing an optimal solver for the 4x4 is attainable, though, but the 5x5 is too much, I think. You can still solve like a human would do. Or solve the first row and first column like a human and next solve the rest optimally.

Edited by brac37, 27 March 2010 - 09:17 PM.

  • 0




0 user(s) are reading this topic

0 members, 0 guests, 0 anonymous users