[OskarS]

The linked solver doesn't use iterative deepening, and it saves all states that the DFS solver encounters (negating the advantage of using DFS).

I think IDDFS might work really well here, even without a good heuristic. It's worth trying, at the very least.

EDIT: read your reply to the other user. Fair enough :)