Eight Digital Puzzle: A Pathfinding Problem
The Eight Digital Puzzle, also known as the Nine-Palace, is a classic problem in the field of pathfinding. The goal is to find the minimum number of steps required to move a set of eight pieces, each marked with a number from 1 to 8, from an initial state to a target state on a 3x3 checkerboard. The pieces cannot be moved to a space adjacent to the target space, and the same numbers cannot be present on different pieces.
Problem Statement
Given an initial state and a target state, find the minimum number of steps required to move a pawn from the initial state to the target state.
Approach
To solve this problem, we can use a backtracking algorithm. We start with the initial state and iteratively explore all possible moves until we reach the target state. We use a stack to store the current state and its parent state, and we keep track of the number of steps taken.
Implementation
We use the NumPy library to represent the states as arrays and to perform array operations. We define a class eightPuzzle to encapsulate the state and its properties.
import numpy as np
class eightPuzzle(object):
directions = ['up', 'down', 'left', 'right']
max = 7
def __init__(self, arr, cost=0, parent=None):
self.arr = arr
self.cost = cost
self.parent = parent
def getCost(self):
return self.cost
def calc(self, state):
final = np.array([[1, 2, 3], [8, 0, 4], [7, 6, 5]])
position = np.where(state.arr == final)
return len(state.arr[position])
def showInfo(self):
for i in range(3):
for j in range(3):
print(self.arr[i, j], end='')
print("\n")
def calc2(self, state1, stop):
for x in stop:
position = np.where(state1.arr == x.arr)
if len(state1.arr[position]) == 9:
return True
return False
def SubStates(self):
subStates = []
row, col = np.where(self.arr == 0)
for direction in self.directions:
if 'left' == direction and col > 0:
s = self.arr.copy()
s[row, col], s[row, col - 1] = s[row, col - 1], s[row, col]
new = eightPuzzle(s, self.cost + 1, self)
subStates.append(new)
if 'up' == direction and row > 0:
s = self.arr.copy()
s[row, col], s[row - 1, col] = s[row - 1, col], s[row, col]
new = eightPuzzle(s, self.cost + 1, self)
subStates.append(new)
if 'down' == direction and row < 2:
s = self.arr.copy()
s[row, col], s[row + 1, col] = s[row + 1, col], s[row, col]
new = eightPuzzle(s, self.cost + 1, self)
subStates.append(new)
if 'right' == direction and col < 2:
s = self.arr.copy()
s[row, col], s[row, col + 1] = s[row, col + 1], s[row, col]
new = eightPuzzle(s, self.cost + 1, self)
subStates.append(new)
return subStates
def DFS(self):
stack = []
stop = []
stack.append(self)
count = -1
while True:
if not stack:
return False, count, None
count += 1
node = stack.pop()
stop.append(node)
node.showInfo()
if self.calc(node) == 9:
return True, count, node
subStates = node.SubStates()
if subStates:
res = sorted(subStates, key=self.calc)
for x in res:
if (x.cost + 9 - self.calc(x)) < eightPuzzle.max:
if self.calc2(x, stop):
continue
stack.append(x)
Main Function
The main function creates an instance of the eightPuzzle class with the initial state and calls the DFS method to find the minimum number of steps required to move the pawn from the initial state to the target state.
def main():
start = np.array([[2, 8, 3], [1, 0, 4], [7, 6, 5]])
p = eightPuzzle(start)
res, count, node = p.DFS()
result = []
if res:
print('%d times after the end of conversion' % count)
while node:
result.append(node)
node = node.parent
result.reverse()
for node in result:
node.showInfo()
else:
print('not found a suitable path within a predetermined range, the cutoff value may be increased')
if __name__ == '__main__':
main()
Output
The output of the program is the minimum number of steps required to move the pawn from the initial state to the target state, along with the sequence of states that lead to the solution.