回溯算法求解智能拼图最少步数

文章结构概述

• 课题说明
  • 探讨
  • 程序的完整编写过程

题目描述

需提供拼图的起始状态，系统将计算并返回完成拼图所需的最少步骤数，例如：

    初始状态：
    1 2 3
    4 5 6
    7 0 8
    成功的状态
    1 2 3
    4 5 6
    7 8 0
    
    输出步数 ： 1
    
    
      
      
      
      
      
      
      
      
      
      
    

0号能够与相邻的数字进行位置互换，最终需使0号处于右下角的位置，而其他数字则应按照既定的顺序依次排列

分析

这与我们平时所见的迷宫求解问题存在一定的差异，因为在迷宫求解过程中，通常可以通过标记已走过的路径来避免重复操作，但在此情形下却无法采用这一方式。这是因为为了抵达最终目标状态，某些位置可能需要多次经过才能实现成功。尽管无法对拼图中的单个位置进行标记，但可以将整个地图的状态记录下来。当0位置发生变动时，我们首先判断新的拼图状态是否曾经出现过，若已存在，则不进行改变；反之，则允许其发生变动。

![在这里插入图片描述](https://ad.itadn.com/c/weblog/blog-img/images/20