HashSet confusion

[BaronB]

Hi all, I'm writing a program to solve sliding block puzzles like these and while I think I've more or less figured it out, I have one problem before I start coding it.

During execution, the program will take the possible moves that can be performed on an board position, perform them, and add the new boards to a HashSet if they aren't in there already until a board that satisifies a solution is found. The trouble is I've never used a HashSet before so I'm not exactly sure how to go about this. Now with HashMaps, when you're putting something in it you clearly pass it a key and a value, but looking at HashSet on the API, you just pass it one object. So, what do you do when adding something to a HashSet? I plan on having it so a move in the HashSet will be a key to the board it generates. What would my HashSet.add() call look like?

Also, when I'm retrieving the solution I'm going to need the series of moves taken to arrive at it... this is also a bit confusing. I'm not entirely sure, but I think I would do this by looking at the key to the solution, but the problem is how do I go from that key (move) to the value (board) that it was executed on? I.e. how do I work my way backwards? Please, if you can help with this, only tell me in pseudo-code or English, I wouldn't want to commit any academic offenses.

Thanks much!

[JosAH]

If you want a board configuration to be the key in a Map, and all the possible
moves to be the values of that entry, I'd say that you encode a board position.
The possible moves can be implemented as a Set of other board positions.

As a first thought (given the board position in your link), I'd say you can encode
that board position as follows:

2 4 4 2
2 4 4 2 
2 3 3 2
2 1 1 2
1 0 0 1

Consider this a number in radix 5 and do the (simple) math. A board configuration
ends up as a number with a list of numbers as the possible moves given that number.

Can you take it from there?

kind regards,

Jos

ps. Use a HashMap instead of a HashTable; it's more 'en vogue'.

[BaronB]

First, let me say thank you for the response :) Though those aren't actually my problems.

From the starting code for the assignment, trays will be encoded into 2-d arrays of integers, where each value at a row/col will be either -1 for empty or the id of an instance of Block in the tray. Mea culpa for not mentioning that in the OP. There's already a possibleMoves method too, which returns a SortedSet of instances of the class Move.

My problem is with adding things to a HashSet and then retrieving them. It makes me feel very stupid but I just can't grasp how I can add keys and values to a HashSet, and then later use them and retrieve a path of boards leading to moves. The code for finding a solution will look broadly like this

boolean foundSolution = false;
  Iterator moves = bp.moveIterator();
  while(moves.hasNext()){
    Move m = (Move) moves.next();
    newbp = bp.makeMove(m);
    if(!positionSet.contains(newbp)){
      positionSet.add(newbp);
      boardPosition.add(newbp);
    }
    if(bp.solvedState()) {foundSolution = true; break;}
  }
  return foundSolution;

It's retrieving the actual path to the solution that is the biggest issue. I can't quite think how to do it - working backwards from the solution -> move that begot the solution -> board that move was applied to -> the move that made that board -> etc etc etc all the way back to the intial configuration seems like the easiest way but I don't know how to make that work with a HashSet.

Thank you again and my apologies for inadvertently omitting relevant information from the OP.

[JosAH]

You're mixing up two disjunct problems:

1) how to find a solution to the puzzle
2) (much simpler) how to use a board configuration as a key to a Map.

I just answered 2) now what is your problem?

kind regards,

Jos

[BaronB]

Er, ok, I guess I am. Well I suppose my problem is that I don't know how I could keep track of the moves that eventually lead to the solution when actually trying all the possible moves. I don't suppose a nudge in the right direction would be out of the question / morally unacceptable?

Thanks

[JosAH]

Er, ok, I guess I am. Well I suppose my problem is that I don't know how I could keep track of the moves that eventually lead to the solution when actually trying all the possible moves. I don't suppose a nudge in the right direction would be out of the question / morally unacceptable?

Thanks

For every possible board configuration you have to keep track of 'where it came from',
i.e. the board configuration before you made the move. Basically you're building a
tree of board configurations on the nodes and the moves on the edges; remembering
where the board configuration 'came from' is a pointer pointing upwards to the root:
it points to the parent node.

kind regards,

Jos