# Tag Info

16

Dennis Soemers' answer is correct: you should use a HashSet or a similar structure to keep track of visited states in BFS Graph Search. However, it doesn't quite answer your question. You're right, that in the worst case, BFS will then require you to store 16! nodes. Even though the insertion and check times in the set will be O(1), you'll still need an ...

8

You can use a set (in the mathematical sense of the word, i.e. a collection that cannot contain duplicates) to store states that you have already seen. The operations you'll need to be able to perform on this are: inserting elements testing if elements are already in there Pretty much every programming language should already have support for a data ...

7

While the answers given are generally true, a BFS in the 15-puzzle is not only quite feasible, it was done in 2005! The paper that describes the approach can be found here: http://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf A few key points: In order to do this, external memory was required - that is the BFS used the hard drive for storage instead of RAM....

3

Ironically the answer is "use whatever system you want." A hashSet is a good idea. However, it turns out that your concerns over memory usage are unfounded. BFS is so bad at these sorts of problems, that it resolves this issue for you. Consider that your BFS requires you to keep a stack of unprocessed states. As you progress into the puzzle, the states ...

2

Welcome to AI.SE @GundamOfOasis! Your intuition is right: this is fundamentally a problem for combinatorial search. You're also right that problems are created by the fact that not every move is valid at state. To fix this, you need to add a function that can determine whether a given state is valid or not, in addition to the usual function that checks ...

1

In general, the process of modelling a problem as a search problem consists in creating a graph which contains nodes, which represent the possible states in your problem, and edges, which represent the relations between these states (that is, you will have an edge between nodes $A$ and $B$ if it is possible to go from state $A$ to state $B$, and vice-versa, ...

1

Approaches to the Game It is true that the board has $16!$ possible states. It is also true that using a hash set is what students learn in a first year algorithms courses to avoid redundancy and endless looping when searching a graph that may contain graph cycles. However, those trivial facts are not pertinent if the goal is to complete the puzzle in the ...

1

This is well covered in the corresponding chapters of Russell & Norvig (Ch. 3 & 4). It also depends on the distinction between TREE-SEARCH and GRAPH-SEARCH. First, note that Breadth-first search also can't handle cost functions that vary between nodes! Breath-first search only cares about the number of moves needed to reach a state, not the total ...

Only top voted, non community-wiki answers of a minimum length are eligible