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.

1. 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),
('h

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

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

-
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.

-
Use fewer 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

-
Use less intermediary variables. And remove unused 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[0]

 # Good
 pos, _ = priority[0]

 # Best
 pos = priority[0][0]

-
Use less whitespace. In the Python community whitespace is pretty important.
The language itself 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)
     ]
 )

-
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.

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

-
inversions can make use of sum to reduce noise.

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

-
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 contents 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[0][0]
priority = np.delete(priority, 0, 0)
board = state[pos][0]
gn = state[pos][2] + 1
loc = int(np.where(board == 0)[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([

StackExchange Code Review Q#110429, answer score: 4