# Npuzzle¶

## Question¶

Implement an N-Puzzle solver in Python.

## Solution¶

```#!/usr/bin/python
# -*- coding: utf-8 -*-
# vim: ts=4 sw=4 et ai ff=unix ft=python nowrap
#
# Program: npuzzle.py
#
# Description: Solves the N-Puzzle Sliding Block Problem.
#
# Usage: python npuzzle.py.
#
# License: GNU GPL Version 2.0. Please refer www.gnu.org.

import random

class State:

def __init__(self, nsize):
"""Initialze the n-puzzle problem, with n-size value, tsize the total nodes and initial the goal state from n.
"""

self.nsize = nsize
self.tsize = pow(self.nsize, 2)
self.goal = list(range(1, self.tsize))
self.goal.append(0)

def printst(self, st):
"""Print the list in a Matrix Format."""

for (index, value) in enumerate(st):
print(' %s ' % value, end=' ')
if index in [x for x in range(self.nsize - 1, self.tsize,
self.nsize)]:
print()
print()

def getvalues(self, key):
"""Utility function to gather the Free Motions at various key positions in the Matrix."""

values = [1, -1, self.nsize, -self.nsize]
valid = []
for x in values:
if 0 <= key + x < self.tsize:
if x == 1 and key in range(self.nsize - 1, self.tsize,
self.nsize):
continue
if x == -1 and key in range(0, self.tsize, self.nsize):
continue
valid.append(x)
return valid

def expand(self, st):
"""Provide the list of next possible states from current state."""

pexpands = {}
for key in range(self.tsize):
pexpands[key] = self.getvalues(key)
pos = st.index(0)
moves = pexpands[pos]
expstates = []
for mv in moves:
nstate = st[:]
(nstate[pos + mv], nstate[pos]) = (nstate[pos], nstate[pos +
mv])
expstates.append(nstate)
return expstates

def one_of_poss(self, st):
"""Choose one of the possible states."""

exp_sts = self.expand(st)
rand_st = random.choice(exp_sts)
return rand_st

def start_state(self, seed=1000):
"""Determine the Start State of the Problem."""

start_st = (self.goal)[:]
for sts in range(seed):
start_st = self.one_of_poss(start_st)
return start_st

def goal_reached(self, st):
"""Check if the Goal Reached or Not."""

return st == self.goal

def manhattan_distance(self, st):
"""Calculate the Manhattan Distances of the particular State.
Manhattan distances are calculated as Total number of Horizontal and Vertical moves required by the values in the current state to reach their position in the Goal State.
"""

mdist = 0
for node in st:
if node != 0:
gdist = abs(self.goal.index(node) - st.index(node))
(jumps, steps) = (gdist // self.nsize, gdist % self.nsize)
mdist += jumps + steps
return mdist

def huristic_next_state(self, st):
"""This is the Huristic Function. It determines the next state to follow and uses Mahattan distances method as the huristics. This this determined way, a A* approach for path finding is used.
If more than one path have same manhattan distance, then a random choice of one of them is analyzed and carried forward. If not best path, randomness to providethe other choice is relied upon. No Depth First search is Used."""

exp_sts = self.expand(st)
mdists = []
for st in exp_sts:
mdists.append(self.manhattan_distance(st))
mdists.sort()
short_path = mdists
if mdists.count(short_path) > 1:
least_paths = [st for st in exp_sts if self.manhattan_distance(st) == short_path]
return random.choice(least_paths)
else:
for st in exp_sts:
if self.manhattan_distance(st) == short_path:
return st

def solve_it(self, st):
while not self.goal_reached(st):
st = self.huristic_next_state(st)
self.printst(st)

if __name__ == '__main__':
print('N-Puzzle Solver!')
print(10 * '-')
state = State(3)
print('The Starting State is:')
start = state.start_state(5)
state.printst(start)
print('The Goal State should be:')
state.printst(state.goal)
print('Here it Goes:')
state.printst(start)
state.solve_it(start)

```