Breadth-first tree creation in C

'sup /prog/, I'm trying to create a c-based program to solve tipover (http://www.puzzlebeast.com/crate/) puzzles and generate a file with all the moves for the fastest solution(min number of moves) . So far, I'm thinking of doing a tree with 4 directions (N,S,E,W), a list with temporary boards and a queue with the movements made.

I was thinking of doing it breadth-first, but I'm having trouble coming up with an algorithm for breadth-first GENERATION of the tree (i.e. a level at a time, if it reaches the solution it stops, avoiding having to build the whole tree). Does anybody have any suggestions?

Since the number of possible movements is limited and relatively small I suggest you to use brute force generation of all posibilities, then take the most efficient. Sure is possible to make a better algorithm, but i think it should come as a natural consequence of the brute force algorithm.
Probably using backtracking is a good idea, but i cannot visualize how at this moment.

Have you read your Xarn today?

Yeah the problem is how would I avoid situations for example where I move up, down, left and right indefinitely. Can't seem to find a stop condition.

extra info: I'm using a two-dimensional array for the boards, with an initial and final position. Empty spaces are 0s, and boxes are numbers depending on number of boxes.

Protip: keep a list of visited states. It doesn't have to be a complete list.
And take >>3's advice. Xarn isn't good for much, but he wrote blog posts specifically covering this fairly nicely.

>>1
Use Haskell and exploit laziness and the nondeterminism monad.

Thanks, gonna check it out.

Don't change these.

Name:		Email:
Entire Thread Thread List