A Python program that solves any given n-puzzle
Switch branches/tags
Nothing to show
Clone or download
Latest commit 6117565 Mar 30, 2017
Permalink
Failed to load latest commit information.
.gitignore add gitignore Mar 3, 2017
README.txt add readme Mar 30, 2017
custom_structures.py tidy up Mar 30, 2017
driver.py tidy code Mar 30, 2017
grid.py tidy up Mar 30, 2017
metric.py tidy up Mar 30, 2017
solver.py tidy up Mar 30, 2017

README.txt

n-puzzle solver
Andy Davies
____________________________

A Python program that solves any given n-puzzle.

See https://en.wikipedia.org/wiki/15_puzzle


USEAGE:
--------

In the command line:
$ python driver.py [search_method] [puzzle]

where search_method: 'bfs', 'dfs' or 'ast'
where puzzle is a comma-seperated list of numbers from 0 to n^2-1

eg.
$ python driver.py ast 0,2,5,6,3,4,1,7,8

represents the puzzle
0 2 5
6 3 4
1 7 8
where 0 is the blank space

This implementation treats the goal state as:
1 2 3
4 5 6
7 8 0   (some have the zero at top left)



RETURNS:
----------

path_to_goal
cost_of_path
nodes_expanded
fringe_size
max_fringe_size
search_depth
max_search_depth
running_time
max_ram_usage

or

'solution not possible' (many grids are not solvable eg. 0,1,2,3)




SEARCH METHOD
------------

bfs - breadth-first search
dfs - depth-first search
ast - A* search, in this case using the total Manhattan Distance heuristic

Note: the point of this project was to see the different time and memory useage for each search_method. As such don't be surprised if bfs or dfs takes a very long time. Use A* search for best results.

At a search depth of just 10 (10 moves to solution), bfs takes 3 hours and 10 terabytes of memory!
  


WHY?
-----

1. To learn Python. This is the first thing I've ever made using Python.

2. To start to learn about Artificial Intelligence, in particular the time and space complexities of search algorithms.