无需O(n²)时间复杂度的8-puzzle问题可解性校验方案探究

当然有，8-puzzle逆序性校验的本质是计算滑块序列的逆序数，逆序数统计完全可以做到**O(n log n)**的时间复杂度，不需要依赖你现在用的双层for循环的O(n²)实现，常用的两种实现方案如下：

• 归并排序改造法
  归并排序的合并阶段可以直接统计跨左右子序列的逆序数：合并两个升序子序列时，只要右子序列当前元素小于左子序列当前元素，那么左子序列剩下的所有元素都和当前右元素构成逆序对，直接累加对应数量即可。整体复杂度和归并排序完全一致，为O(n log n)，如果要拓展到15-puzzle、24-puzzle等更大规模的滑块拼图，性能提升会非常明显。
  简单的Python示例核心逻辑参考：

  def count_inversion(arr):
      if len(arr) <= 1:
          return arr, 0
      mid = len(arr) // 2
      left, inv_left = count_inversion(arr[:mid])
      right, inv_right = count_inversion(arr[mid:])
      merged, inv_cross = merge(left, right)
      return merged, inv_left + inv_right + inv_cross
  

• 树状数组（Fenwick Tree）法
  因为8-puzzle的滑块值都是1~8的小范围整数（空格值为0，统计逆序数时直接忽略即可），不需要额外做离散化处理：从后往前遍历序列，每遍历到一个元素就查询树状数组中小于当前元素的数的总个数（即为当前元素贡献的逆序数），再把当前元素更新到树状数组中。整体复杂度同样为O(n log n)，代码实现更简洁，空间开销也更低。

补充注意：8-puzzle可解性判断不能只看逆序数奇偶性，3×3规格下还需要叠加空格从下往上数的行号的奇偶性，二者奇偶性一致时问题才是可解的。

内容的提问来源于stack exchange，提问作者Akcore