# 8-Puzzle using A* and Manhattan Distance

I have developed this 8-puzzle solver using A* with manhattan distance. Appreciate if you can help/guide me regarding:
1. Improving the readability and optimization of the code.
2. I am using sort to arrange the priority queue after each state exploration to find the most promising state to explore next. Any way to optimize it.

import numpy as np
from copy import deepcopy
import datetime as dt
import sys

# calculate Manhattan distance for each digit as per goal
def mhd(s, g):
m = abs(s // 3 - g // 3) + abs(s % 3 - g % 3)
return sum(m[1:])

# assign each digit the coordinate to calculate Manhattan distance
def coor(s):
c = np.array(range(9))
for x, y in enumerate(s):
c[y] = x
return c

# checking if the initial state is solvable via inversion calculation
def inversions(s):
k = s[s != 0]
tinv = 0
for i in range(len(k) - 1):
b = np.array(np.where(k[i+1:] < k[i])).reshape(-1)
tinv += len(b)
return tinv

# check user input for correctness
def all(s):
set = '012345678'
return 0 not in [c in s for c in set]

# generate board list as per optimized steps in sequence
def genoptimal(state):
optimal = np.array([], int).reshape(-1, 9)
last = len(state) - 1
while last != -1:
optimal = np.insert(optimal, 0, state[last]['board'], 0)
last = int(state[last]['parent'])
return optimal.reshape(-1, 3, 3)

# solve the board
def solve(board, goal):
#
moves = np.array(   [   ('u', [0, 1, 2], -3),
('d', [6, 7, 8],  3),
('l', [0, 3, 6], -1),
('r', [2, 5, 8],  1)
],
dtype=  [  ('move',  str, 1),
('pos',   list),
('delta', int)
]
)

dtstate = [ ('board',  list),
('parent', int),
('gn',     int),
('hn',     int)
]

goalc = coor(goal)
# initial state values
parent = -1
gn     = 0
hn     = mhd(coor(board), goalc)
state = np.array([(board, parent, gn, hn)], dtstate)

#priority queue initialization
dtpriority = [  ('pos', int),
('fn', int)
]

priority = np.array( [(0, hn)], dtpriority)
#
while True:
priority = np.sort(priority, kind='mergesort', order=['fn', 'pos']) # sort priority queue
pos, fn = priority                   # pick out first from sorted to explore
priority = np.delete(priority, 0, 0)    # remove from queue what we are exploring
board, parent, gn, hn = state[pos]
board = np.array(board)
loc = int(np.where(board == 0))      # locate '0' (blank)
gn = gn + 1                             # increase cost g(n) by 1

for m in moves:
if loc not in m['pos']:
succ = deepcopy(board)          # generate new state as copy of current
succ[loc], succ[loc + m['delta']] = succ[loc + m['delta']], succ[loc]   # do the move

if ~(np.all(list(state['board']) == succ, 1)).any():    # check if new (not repeat)
hn = mhd(coor(succ), goalc)                         # calculate Manhattan distance
q = np.array(   [(succ, pos, gn, hn)], dtstate)     # generate and add new state in the list
state = np.append(state, q, 0)
fn = gn + hn                                        # calculate f(n)
q = np.array([(len(state) - 1, fn)], dtpriority)    # add to priority queue
priority = np.append(priority, q, 0)

if np.array_equal(succ, goal):                      # is this goal state?
print('Goal achieved!')
return state, len(priority)

return state, len(priority)

#################################################
def main():
print()
goal    =  np.array( [1, 2, 3, 4, 5, 6, 7, 8, 0] )
string = input('Enter board: ')

if len(string) != 9 or all(string) == 0:
print('incorrect input')
return

board = np.array(list(map(int, string)))
if (inversions(board) % 2 != 0):
print('not solvable')
return

state, explored = solve(board, goal)
print()
print('Total generated:', len(state))
print('Total explored: ', len(state) - explored)
print()
# generate and show optimized steps
optimal = genoptimal(state)
print('Total optimized steps:', len(optimal) - 1)
print()
print(optimal)
print()

################################################################
# Main Program

if __name__ == '__main__':
main()

• Since all possible $f$ values are from the set $\{ 0, 1, \dots, c \}$, where $c$ is rather small (probably less than 100 for 8-puzzle), you could use so called Dial's heap: basically, you map each $f$ value to the list of nodes with that very value. In order to remove the minimum, scan the array from beginning to end, and return some node of the first non-empty list of nodes. See, for example, diku.dk/PATH05/GoldbergSlides.pdf page 45. – coderodde Nov 11 '15 at 11:28
• What does this do? ~(np.all(list(state['board']) == succ, 1)).any(). I know that (np.all(list(state['board']) == succ, 1)).any() returns a Boolean. So what does ~ do? I bet it's not what you're thinking... – Peilonrayz Nov 11 '15 at 12:19
• @JoeWallis the statement (np.all(list(state['board']) == succ, 1)).any() returns a boolean True if any instance of state contains same values as succ. with ~ it turns to False, meaning if the succ contains a state that is not already in the queue, then add it to the queue. this is what i think it does and this is the functionality that i have implemented. – Abdul Qadir Nov 12 '15 at 3:53
• A* and TTT is equevalent – Artur Mustafin Nov 12 '15 at 10:59
• @ArturMustafin what's TTT? can u pl elaborate – Abdul Qadir Nov 13 '15 at 8:54

## 1 Answer

1. Don't import things you don't use. You can safely remove dt and sys.

2. Don't overwrite builtins. all is already a function, and your implementation is more is_anagram.

3. When using Booleans use things for Booleans.

# What are you on about 0 (the number) is never in.
return 0 not in [c in s for c in set]

# What you should use
return False not in [c in s for c in set]

# This can be better worded as:
# And remove __builtin__ if you stop shadowing all.
return __builtin__.all(c in s for c in set)


But then there is the usage of the bitwise not ~.

>>> bool(~True), ~True
(True, -2)
>>> bool(~False), ~False
(True, -1)
>>> bool(~-1), ~-1
(False, 0)


Yes ~(np.all(list(state['board']) == succ, 1)).any() is always True. Instead use not.

4. Use less comments. And if you are to use comments, use pre-line rather than inline.

# ugly
gn = gn + 1 # increase cost g(n) by 1

# better
# increase cost g(n) by 1
gn = gn + 1

# Best (As we all understand addition.)
gn += 1

5. Use less intermarry variables. And remove un-used ones.

# Bad
m = abs(s // 3 - g // 3) + abs(s % 3 - g % 3)
return sum(m[1:])

# Good
return sum((abs(s // 3 - g // 3) + abs(s % 3 - g % 3))[1:])

# Bad
pos, fn = priority

# Good
pos, _ = priority

# Best
pos = priority

6. Use less whitespace. In the Python community whitespace is pretty important. The language it's self ingrains good practice of well tabbed code. But we also discourage useless whitespace, or whitespace that impairs readability.

# Bad
moves = np.array(   [   ('u', [0, 1, 2], -3),
('d', [6, 7, 8],  3),
('l', [0, 3, 6], -1),
('r', [2, 5, 8],  1)
],
dtype=  [  ('move',  str, 1),
('pos',   list),
('delta', int)
]
)

# Good
moves = np.array(
[
('u', [0, 1, 2], -3),
('d', [6, 7, 8],  3),
('l', [0, 3, 6], -1),
('r', [2, 5, 8],  1)
],
dtype=[
('move',  str, 1),
('pos',   list),
('delta', int)
]
)

7. Pick better variable names. We're not all mathematicians, and even if we were gn is of no help to understand the program. parent on the other hand is a good variable name.

8. The function all should be removed. As an alternate you can also just do an anagram check on it. sorted(a) == sorted(b)

9. inversions can make use of sum to reduce noise.

10. Reduce the amount of un-used items in your arrays, currently the boards parents and hn are never used.

11. You can use a default dict rather than np.all(list(state['board']) == succ, 1).any() to check if you have already used found the board.

This is good as for the input 012345678 you get:

Total generated: 2057
Total explored:  1305

Total optimized steps: 22


With defaultdict you can check the contense in O(1), where you would have to check in O(n) with np.all(...).

So I would use:

import numpy as np
from copy import deepcopy
from collections import defaultdict

def mhd(s, g):
return sum((abs(s // 3 - g // 3) + abs(s % 3 - g % 3))[1:])

def coor(s):
c = np.array(range(9))
for x, y in enumerate(s):
c[y] = x
return c

def solve(board, goal):
moves = np.array(
[
('u', [0, 1, 2], -3),
('d', [6, 7, 8], 3),
('l', [0, 3, 6], -1),
('r', [2, 5, 8], 1)
],
dtype=[
('move', str, 1),
('pos', list),
('delta', int)
]
)

STATE = [
('board', list),
('parent', int),
('gn', int),
('hn', int)
]

PRIORITY = [
('pos', int),
('fn', int)
]

previous_boards = defaultdict(bool)

goalc = coor(goal)
hn = mhd(coor(board), goalc)
state = np.array([(board, -1, 0, hn)], STATE)
priority = np.array( [(0, hn)], PRIORITY)

while True:
priority = np.sort(priority, kind='mergesort', order=['fn', 'pos'])
pos = priority
priority = np.delete(priority, 0, 0)
board = state[pos]
gn = state[pos] + 1
loc = int(np.where(board == 0))

for m in moves:
if loc not in m['pos']:
succ = deepcopy(board)
delta_loc = loc + m['delta']
succ[loc], succ[delta_loc] = succ[delta_loc], succ[loc]
succ_t = tuple(succ)

if previous_boards[succ_t]:
continue

previous_boards[succ_t] = True

hn = mhd(coor(succ_t), goalc)
state = np.append(
state,
np.array([(succ, pos, gn, hn)], STATE),
0
)
priority = np.append(
priority,
np.array([(len(state) - 1, gn + hn)], PRIORITY),
0
)

if np.array_equal(succ, goal):
return state, len(priority)

def inversions(s):
k = s[s != 0]
return sum(
len(np.array(np.where(k[i+1:] < k[i])).reshape(-1))
for i in range(len(k) - 1)
)

def genoptimal(state):
optimal = np.array([], int).reshape(-1, 9)
last = len(state) - 1
while last != -1:
optimal = np.insert(optimal, 0, state[last]['board'], 0)
last = int(state[last]['parent'])
return optimal.reshape(-1, 3, 3)

def main():
print()
goal = np.array([1, 2, 3, 4, 5, 6, 7, 8, 0])
string = input('Enter board: ')
board = np.array(list(map(int, string)))

if sorted(string) != sorted('012345678'):
print('incorrect input')
return
if inversions(board) % 2:
print('not solvable')
return

state, explored = solve(board, goal)
optimal = genoptimal(state)

print((
'Goal achieved!\n'
'\n'
'Total generated: {}\n'
'Total explored:  {}\n'
'\n'
'Total optimized steps: {}\n'
'{}\n'
'\n'
).format(len(state), len(state) - explored, len(optimal) - 1, optimal))

if __name__ == '__main__':
main()

• this is great stuff. taken note of all the points and implemented. only change is i had to put succ = numpy.empty_like(board) inside the moves loop as it was behaving strangely. thanks for highlighting use of ~ (if i had placed the bet would have lost it). is there any improvement u would suggest on the use of sort or the np.all(list(state['board']) == succ, 1).any() check. – Abdul Qadir Nov 13 '15 at 8:54
• @AbdulQadir No problem, I didn't want to mess with NumPy too much as I didn't have a working install of it. (I made the 'bet', as I was going to write an answer, but that one line was well odd). As for those two things, I can look into it, I doubt I can get the sort better, maybe use a different algorithm, and I don't know if it works but np.all(state['board'] == succ, 1).any() is as far as I know the best. I'll get numpy and do some changes, and will update my answer if there's anything good! – Peilonrayz Nov 13 '15 at 9:19
• one thing i was wondering. why have you changed succ = deepcopy(board) to succ = np.empty_like(board) np.copyto(succ, board). is it because of the additional library requirement with deepcopy or some other consideration. – Abdul Qadir Nov 14 '15 at 8:24
• @AbdulQadir I replaced deepcopy solely because IMO you don't need it. If you want to know why I chose those functions, then it was due to this comment: stackoverflow.com/q/6431973 – Peilonrayz Nov 14 '15 at 12:56
• @AbdulQadir I added deepcopy back due to the same reason that you put it there. Without deepcopy my code would frequently raise errors, due to shallow copying. – Peilonrayz Nov 14 '15 at 14:16