Python 中的 8 拼图问题

17 Mar 2025 | 6 分钟阅读

本文介绍了 8 拼图问题的解决方案。提供一个3x3 的棋盘，上面有 8 个数字块（每个块的数字从 1 到 8）和一个单独的空格。目标是利用空白格将数字块排列成目标状态。可以将相邻的四个（左、右、上、下）数字块移动到空位。

例如，

1. DFS (深度优先搜索，穷举法)

我们可以在状态空间树（一个特定问题的状态集合，即从初始状态可以到达的所有状态）上执行深度优先搜索。

图：8 拼图的状态空间树

在此解决方案中，进一步的移动可能并不总是让我们更接近目标，反而会让我们远离。无论初始状态如何，状态空间树都会沿着根节点的左侧路径搜索。使用此方法，可能永远找不到目标节点。

2. BFS (广度优先搜索，穷举法)

我们可以使用广度优先方法搜索状态空间树。它总是能找到最接近根的目标状态。但是，该算法无论初始状态如何，都会尝试与 DFS相同的移动序列。

3. 分支限界法

通过避免搜索不包含目标节点的子树，一个“智能”的评估函数，也称为近似成本函数，可以经常加速查找目标节点的过程。然而，它不使用回溯法，而是执行类似 BFS 的搜索。

基本上，分支限界法涉及三种不同类型的节点。

活节点是已生成但其子节点尚未生成的节点。
E 节点（一个活节点）的后继节点正在被检查。换句话说，E 节点是当前正在扩展的节点。
死节点是指已生成但不再进一步开发或检查的节点。死节点已经扩展了其所有后继节点。

成本函数

在搜索树中，每个节点 Y 都有一个相应的成本。下一个E 节点可以通过成本函数找到。具有最低成本的 E 节点是下一个。该函数可以定义为：

C(Y) = g(Y) + h(Y) 
where
   g(Y) = the costs of reaching to the current node 
          from the root.
   h(Y) = the costs of reaching to an answer node from the Y.

8 拼图算法的最佳成本函数是：

我们假设将一块数字块向任何方向移动将花费一个单位。基于此，我们为 8 拼图算法创建以下成本函数：

c(y) = f(y) + h(y) 
where
   f(y) = the path's total length from the root y. 
   and
   h(y) = the amount of the non-blank tiles which are not in 
        their final goal position (misplaced tiles).

To change state y into a desired state, there are at least h(y) movements required.

有一个算法可以估计 h(y) 的未知值，该算法是可用的。

最终算法

为了维护活节点列表，算法LCSearch 使用Least() 和Add() 函数。
Least() 识别一个具有最小 c(y) 的活节点，将其从列表中移除，然后返回。
Add(y) 将y 添加到活节点列表中。
Add(y) 将活节点列表实现为最小堆。

上述算法从提供的 8 拼图起始配置到达最终配置所走的路径如下图所示。请注意，只有成本函数值最低的节点才会被扩展。

代码

# Python code to display the way from the root
# node to the final destination node for N*N-1 puzzle
# algorithm by the help of Branch and Bound technique
# The answer assumes that the instance of the
# puzzle can be solved

# Importing the 'copy' for deepcopy method
import copy

# Importing the heap methods from the python
# library for the Priority Queue
from heapq import heappush, heappop

# This particular var can be changed to transform
# the program from 8 puzzle(n=3) into 15
# puzzle(n=4) and so on ...
n = 3

# bottom, left, top, right
rows = [ 1, 0, -1, 0 ]
cols = [ 0, -1, 0, 1 ]

# creating a class for the Priority Queue
class priorityQueue:
	
	# Constructor for initializing a
	# Priority Queue
	def __init__(self):
		self.heap = []

	# Inserting a new key 'key'
	def push(self, key):
		heappush(self.heap, key)

	# funct to remove the element that is minimum,
	# from the Priority Queue
	def pop(self):
		return heappop(self.heap)

	# funct to check if the Queue is empty or not
	def empty(self):
		if not self.heap:
			return True
		else:
			return False

# structure of the node
class nodes:
	
	def __init__(self, parent, mats, empty_tile_posi,
				costs, levels):
					
		# This will store the parent node to the
		# current node And helps in tracing the
		# path when the solution is visible
		self.parent = parent

		# Useful for Storing the matrix
		self.mats = mats

		# useful for Storing the position where the
		# empty space tile is already existing in the matrix
		self.empty_tile_posi = empty_tile_posi

		# Store no. of misplaced tiles
		self.costs = costs

		# Store no. of moves so far
		self.levels = levels

	# This func is used in order to form the
	# priority queue based on
	# the costs var of objects
	def __lt__(self, nxt):
		return self.costs < nxt.costs

# method to calc. the no. of
# misplaced tiles, that is the no. of non-blank
# tiles not in their final posi
def calculateCosts(mats, final) -> int:
	
	count = 0
	for i in range(n):
		for j in range(n):
			if ((mats[i][j]) and
				(mats[i][j] != final[i][j])):
				count += 1
				
	return count

def newNodes(mats, empty_tile_posi, new_empty_tile_posi,
			levels, parent, final) -> nodes:
				
	# Copying data from the parent matrixes to the present matrixes
	new_mats = copy.deepcopy(mats)

	# Moving the tile by 1 position
	x1 = empty_tile_posi[0]
	y1 = empty_tile_posi[1]
	x2 = new_empty_tile_posi[0]
	y2 = new_empty_tile_posi[1]
	new_mats[x1][y1], new_mats[x2][y2] = new_mats[x2][y2], new_mats[x1][y1]

	# Setting the no. of misplaced tiles
	costs = calculateCosts(new_mats, final)

	new_nodes = nodes(parent, new_mats, new_empty_tile_posi,
					costs, levels)
	return new_nodes

# func to print the N by N matrix
def printMatsrix(mats):
	
	for i in range(n):
		for j in range(n):
			print("%d " % (mats[i][j]), end = " ")
			
		print()

# func to know if (x, y) is a valid or invalid
# matrix coordinates
def isSafe(x, y):
	
	return x >= 0 and x < n and y >= 0 and y < n

# Printing the path from the root node to the final node
def printPath(root):
	
	if root == None:
		return
	
	printPath(root.parent)
	printMatsrix(root.mats)
	print()

# method for solving N*N - 1 puzzle algo
# by utilizing the Branch and Bound technique. empty_tile_posi is
# the blank tile position initially.
def solve(initial, empty_tile_posi, final):
	
	# Creating a priority queue for storing the live
	# nodes of the search tree
	pq = priorityQueue()

	# Creating the root node
	costs = calculateCosts(initial, final)
	root = nodes(None, initial,
				empty_tile_posi, costs, 0)

	# Adding root to the list of live nodes
	pq.push(root)

	# Discovering a live node with min. costs,
	# and adding its children to the list of live
	# nodes and finally deleting it from
	# the list.
	while not pq.empty():

		# Finding a live node with min. estimatsed
		# costs and deleting it form the list of the
		# live nodes
		minimum = pq.pop()

		# If the min. is ans node
		if minimum.costs == 0:
			
			# Printing the path from the root to
			# destination;
			printPath(minimum)
			return

		# Generating all feasible children
		for i in range(n):
			new_tile_posi = [
				minimum.empty_tile_posi[0] + rows[i],
				minimum.empty_tile_posi[1] + cols[i], ]
				
			if isSafe(new_tile_posi[0], new_tile_posi[1]):
				
				# Creating a child node
				child = newNodes(minimum.mats,
								minimum.empty_tile_posi,
								new_tile_posi,
								minimum.levels + 1,
								minimum, final,)

				# Adding the child to the list of live nodes
				pq.push(child)

# Main Code

# Initial configuration
# Value 0 is taken here as an empty space
initial = [ [ 1, 2, 3 ],
			[ 5, 6, 0 ],
			[ 7, 8, 4 ] ]

# Final configuration that can be solved
# Value 0 is taken as an empty space
final = [ [ 1, 2, 3 ],
		[ 5, 8, 6 ],
		[ 0, 7, 4 ] ]

# Blank tile coordinates in the 
# initial configuration
empty_tile_posi = [ 1, 2 ]

# Method call for solving the puzzle
solve(initial, empty_tile_posi, final)

输出

下一主题Sklearn 中的 accuracy_score

Python 中的 8 拼图问题

1. DFS (深度优先搜索，穷举法)

2. BFS (广度优先搜索，穷举法)

3. 分支限界法

成本函数

最终算法

代码

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

Python 问题

Python 中的 8 拼图问题

1. DFS (深度优先搜索，穷举法)

2. BFS (广度优先搜索，穷举法)

3. 分支限界法

成本函数

最终算法

代码

相关帖子

是否应该更新 Python 的最新版本错误修复

如何在 Python 中使用 LightGBM

如何在 Windows 上安装 Python

Python 程序接受包含所有元音的字符串

Python 程序旋转图像

使用 Matplotlib 在 Python 中进行 3D 快速排序可视化

Python 程序制作猜词游戏

Python 描述符

Python SNMP 模块

Python FlashText 模块

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器