• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Eight Puzzle Algorithm Help

 
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi all, I'm working on an assignment and want to make sure I'm going in the right direction. Any help or tips would be greatly appreciated. (I don't want answers just guidance)
These are the two classes I'm working on now. One thing I don't understand is how to "reference parent BoardState" in the BoardState class.
And for the Manhattan method I don't understand how I would begin to implement the distance between board states.

Thanks in advance.



Screen-Shot-2016-07-24-at-9.10.55-PM.png
[Thumbnail for Screen-Shot-2016-07-24-at-9.10.55-PM.png]
 
Bartender
Posts: 1845
10
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi!  Welcome to the ranch.  
Just one little administrative thing.  A subject of "Help" isn't really that useful.  I've changed it to a more meaningful subject line of "Eight Puzzle Algorithm Help" for you.
For context I googled this page:  https://www.cs.princeton.edu/courses/archive/spr10/cos226/assignments/8puzzle.html

It might be your actual assignment, or just one similar.
However it explains the "EightPuzzle" and the "Manhattan method" you are asking about.

Your questions:  
1 - How to reference "parent board state"

I think that just means you need a variable of type : "BoardState" which represents the state of the board just before the last move.  
Keeping track of that prevents you from just "undoing" the move you just made.
You can check if two BoardState variables represent the same state using the "equals" method - which I presume you need to implement.

2 - "Manhattan method"
This is defined as:
"The sum of the distances (sum of the vertical and horizontal distance) from the blocks to their goal positions, plus the number of moves made so far to get to the state."

My suggestion: break the problem down.
Can you work out how far a block is from its "target position" ?
So if you have '1' in position '1' and it should be in position '4' - how many vertical/horizontal moves is it away from its target position
Draw a picture :-)
Once you figure THAT out, the rest should be easy.

 
sunglasses are a type of coolness prosthetic. Check out the sunglasses on this tiny ad:
a bit of art, as a gift, that will fit in a stocking
https://gardener-gift.com
reply
    Bookmark Topic Watch Topic
  • New Topic