State space search question

From: Dave (better_cs_now_at_yahoo.com)
Date: 05/31/04 

Date: Mon, 31 May 2004 11:17:03 -0700

Hello all,

I have a question regarding state space search. I've written a generic
library to perform state space searches, and, to test it, I have also
written a sample client application that solves the eight puzzle problem. I
am seeing some unexpected behavior, but I'm not so sure that it is a bug.
I'm wondering if what I am seeing is an interaction between limiting the
search depth and the supression of the generation of repeated states. Allow
me to elaborate...

I am performing a depth-limited search. For the initial puzzle
configuration I have, the optimal solution has length 30 (I verified this
with an A* search). So, to test my depth-limited search, I set the depth
limit to 30 and let it go. It did not find a solution. However, I also
have some functionality in place to supress the generation of repeated
states. I am wondering if all of the states immediately preceeding the goal
were reached at a depth of 30 (due to a non-optimal path to them) and this
prevented them from being seen later at a depth of 29 leading to the goal at
30.

Does this make sense? Does anybody have experience in this area and can
tell me if there is an interaction between depth limit and repeated state
supression? Or is there some other valid reason for the observed behavior?
Or do I just flat-out have a bug?

Thanks!
Dave