I'm trying to solve the N-Puzzle problem using IDA* algorithm with a Manhattan heuristic. I already implemented the algorithm from the pseudocode in this Wikipedia page (link).
Here's my code so far :
class Node():
def __init__(self, state, manhattan):
self.state = state
self.heuristic = manhattan
def __str__(self):
return f"state=\n{self.state}\nheuristic={int(self.heuristic)}"
def __eq__(self, other):
return np.array_equal(self.state, other.state)
def customSort(node):
return node.heuristic
def nextnodes(node):
zero = np.where(node.state == 0)
y,x = zero
y = int(y)
x = int(x)
directions = []
if y > 0:
directions.append((y - 1, x))
if x > 0:
directions.append((y, x - 1))
if y < constant.SIZE2 - 1:
directions.append((y + 1, x))
if x < constant.SIZE2 - 1:
directions.append((y, x + 1))
arr = []
for direction in directions:
tmp = np.copy(node.state)
goal = np.where(constant.GOAL_STATE == tmp[direction])
tmp[direction], tmp[zero] = tmp[zero], tmp[direction]
tile1_score = manhattan_distance(direction, goal)
tile2_score = manhattan_distance(zero, goal)
arr.append(Node(tmp, node.heuristic - tile1_score + tile2_score))
arr.sort(key=customSort)
return arr
def manhattan_distance(a, b):
return abs(b[0] - a[0]) + abs(b[1] - a[1])
def count_distance(number, state1, state2):
position1 = np.where(state1 == number)
position2 = np.where(state2 == number)
return manhattan_distance(position1, position2)
def manhattan_heuristic(state):
distances = [count_distance(num, state, constant.GOAL_STATE) for num in constant.SIZE]
return sum(distances)
def search(path, g, threshold):
node = path[-1]
f = g + node.heuristic
if f > threshold:
return f
if np.array_equal(node.state, constant.GOAL_STATE):
return True
minimum = float('inf')
for n in nextnodes(node):
if n not in path:
path.append(n)
tmp = search(path, g + 1, threshold)
if tmp == True:
return True
if tmp < minimum:
minimum = tmp
path.pop()
return minimum
def solve(initial_state):path = solve(initial_state)
initial_node = Node(initial_state, manhattan_heuristic(initial_state))
threshold = initial_node.heuristic
path = [initial_node]
while 1:
tmp = search(path, 0, threshold)
if tmp == True:
print(f"GOOD!")
return path
elif tmp == float('inf'):
print(f"WRONG!")
return False
threshold = tmp
You can call the solve() function (and create some needed global variables) like this:
def define_goal_state(n):
global GOAL_STATE
global SIZE
global SIZE2
global ZERO
m = [[0] * n for i in range(n)]
dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]
x, y, c = 0, -1, 1
for i in range(n + n - 2):
for j in range((n + n - i) // 2):
x += dx[i % 4]
y += dy[i % 4]
m[x][y] = c
c += 1
GOAL_STATE = np.array(m)
SIZE = range(1, len(GOAL_STATE) ** 2)
SIZE2 = len(GOAL_STATE)
ZERO = np.where(GOAL_STATE == 0)
initial_state = np.array([8 7 3],[4 1 2],[0 5 6])
define_goal_state(len(initial_state))
path = solve(initial_state)
My implementation of the Wikipedia pseudocode is working and I get pretty fast results in a 8-Puzzle problem. But it gets really slow with a 15-Puzzle problem and above.
Regarding the solve() and the search() functions I think I respect almost identically the pseudocode. I also optimized my nextnodes() function to count only the tile that has been moved, not all tiles every time. Should be good here.
So where's the catch ? Why is my implementation taking so long ? Does anyone have a clue ?
