请设计并实现一个数字华容道（如 3×3）的求解器：给定初始棋盘布局，输出到达目标状态的最少步数及路径。请说明你的算法思路和复杂度。

回答思路

1. 将棋盘状态编码为唯一键并正确建模相邻移动
2. 选择 BFS 或 A* 并说明启发式函数选择依据
3. 正确处理无解情况和曼哈顿距离等启发函数
4. 分析时间与空间复杂度并给出优化思路