CODEWITHSUNDEEP
javasearchgraphartificial-intelligencedepth-first-search
Brejuro
Brejuro

Reputation: 3541

How to model this Depth First Search solution

I have a puzzle game that has a State depending on the arrangement of the pieces in the puzzle. I am trying to solve this puzzle using Depth First Search, however I am confused on how to approach it. From my understanding, Depth First Search will search a graph to find a solution, but my puzzle isn't in graph form. All I know is the current state and the states achievable from that state.

Am I supposed to build this graph as I discover all possible states from the state I am currently at? Wouldn't that defeat the purpose though - first building a graph with every possible state, then search the entire graph for the solution?

I have a method that can explore all the possible states from the current state using a Move, which I'm sure will come in handy except I don't know how to put it to use.

Upvotes: 1

Views: 108

Answers (2)

digitaljoel
digitaljoel

Reputation: 26574

Sounds to me like depth first is the wrong way about it. If you have a state, and you know all states that you can get to from that state, then breadth first may be more appropriate. With BFS you would know that the first solution you come to is the shortest solution.

If you are certain that there is a solution then you wouldn't have to worry about infinite recursion because any paths caught in a loop wouldn't be the shortest in the end anyway, they would just cause unnecessary work.

An iterative solution using a queue would work.

/** pseudocode **/
Queue q = new LinkedList();
q.put(myState)
while ( !q.isEmpty()) {
  State s = q.remove();
  if ( endState.equals(s)) {
    return something;
  }
  for ( State newState : s.getNextStates()) {
    q.add(newState);
  }
}

If you do want to go with a depth first search, then simply change the queue to a stack but then you will have to deal with the cycles.

If your queue item was a wrapper that that contained the path to the current state instead of just the current state then you could easily get to the depth and path that was traversed for the shortest route (or at least, first shortest route discovered if there are multiple routes of the same depth.)

Upvotes: 0

Claudiu
Claudiu

Reputation: 229321

You don't have to explicitly build a graph. You can represent your problem as a graph, conceptually, where the nodes are the states and the edges are the transitions between the states. Depth first search is to follow an edge all the way until you hit an end state, before moving on to another edge. So it would look something like this (pseudocode):

def search(state):
    if is_end_state(state):
        # search down this branch finished, do something
        return something

    for move in possible_moves_from(state):
        search(apply_move(state, move))

You end up implicitly building the graph, via the recursive calls and the stack state, as you go.

Note that if you have cycles (e.g. you can move left, then move right to get back to the exact same state) then you will have to keep track of already-visited states or you'll loop forever. Something like this:

def search(state, seen_states):
    if state in seen_states:
        # already visited, don't visit again
        return 

    seen_states.add(state)

    # same as before:      
    if is_end_state(state):
        return something

    for move in possible_moves_from(state):
        search(apply_move(state, move), seen_states)

In terms of how to implement this, I recommend you have seen_states be a HashSet<State> and you make your State hashable.

Upvotes: 1

Related Questions