The optimal solution is not always provided

[wvenialbo]

In most of my test cases, the optimal solution is not found. I guess it is a hashing issue. By excluding duplicate and mirror entries in the search tree, there is an implicit assumption that a branch represents an equal or longer solution, however, that is not always the case. Some solutions with more individual steps could be associated to one with less moves, as shown in the figure below.

The figure shows the provided solution in the upper branch and the optimal solution in the lower branch. The firs image in the upper row is the problem setup. The first step in both branches are mirrored states, whereas the step 3 in the provided solution is a duplicate state of the step 5 in the optimal solution, as are the two last steps shown in both branches.

A possible workaround is to keep a separate list of already computed states, to avoid compute duplicate states in the corresponding subtree, and a full tree of solutions, with a mechanism to avoid recursive tree traversing, since a state can have more than one parent.