Skip to content

Instantly share code, notes, and snippets.

@alierdogan7
Created March 17, 2017 14:42
Embed
What would you like to do?
EightPuzzleSolver
from random import shuffle
import heapq
def main():
# puzzles = []
# while len(puzzles) < 100:
# puzzles.append(generate_solvable_puzzle())
node = Node(generate_solvable_puzzle(), None)
print(node)
n1 = node.move_up()
print('Moving up')
print(Node(n1, None))
# n = Node([2, 1, 4, 5, 0, 6, 7, 8, 3])
# print(n)
n2 = node.move_down()
print('Moving down')
print(Node(n2, None))
n3 = node.move_right()
print('Moving right')
print(Node(n3, None))
n4 = node.move_left()
print('Moving left')
print(Node(n4, None))
class Node:
goal = [1, 2, 3, 4, 5, 6, 7, 8, 0]
def __init__(self, state, parent=None):
self.state = state # state is None if illegal state
self.parent = parent
def __str__(self):
pattern = '[%s %s %s]\n[%s %s %s]\n[%s %s %s]'
values = [str(x) if x != 0 else ' ' for x in self.state]
return pattern % tuple(values)
def __repr__(self):
return str(self)
def __eq__(self, other): # for comparing the nodes and detecting repeated states
return self.state == other.state
def children(self):
children = [Node(self.move_up(), self), Node(self.move_down(), self), Node(self.move_left(), self),
Node(self.move_right(), self)] # GENERATE ALL POSSIBLE STATES
children = [node if node.state is not None for node in children] # eliminate illegal states
return children
def search(self):
# http://aima.cs.berkeley.edu/python/search.html
'''
Best-First-Search( Maze m )
Insert( m.StartNode )
Until PriorityQueue is empty
c <- PriorityQueue.DeleteMin
If c is the goal
Exit
Else
Foreach neighbor n of c
If n "Unvisited"
Mark n "Visited"
Insert( n )
Mark c "Examined"
End procedure
'''
closed = {}
fringe.append(Node(problem.initial))
while fringe:
node = fringe.pop()
if problem.goal_test(node.state):
return node
if node.state not in closed:
closed[node.state] = True
fringe.extend(node.expand(problem))
return None
def num_of_misplaced_tiles(self):
misplaced = 0
for index, tile in enumerate(self.state):
if tile != 0 and index + 1 != tile:
misplaced += 1
return misplaced
def move_up(self):
blank_position = self.state.index(0)
if blank_position < 6: # means that blank is not on the last row
puzzle = self.state.copy()
puzzle[blank_position], puzzle[blank_position + 3] = puzzle[blank_position + 3], puzzle[blank_position]
return puzzle
else: # if illegal state
return None
def move_down(self):
blank_position = self.state.index(0)
if blank_position > 2: # means that blank is not on the first row
puzzle = self.state.copy()
puzzle[blank_position], puzzle[blank_position - 3] = puzzle[blank_position - 3], puzzle[blank_position]
return puzzle
else: # if illegal state
return None
def move_right(self):
blank_position = self.state.index(0)
if blank_position not in [0, 3, 6]: # means that blank is not on the first column
puzzle = self.state.copy()
puzzle[blank_position], puzzle[blank_position - 1] = puzzle[blank_position - 1], puzzle[blank_position]
return puzzle
else: # if illegal state
return None
def move_left(self):
blank_position = self.state.index(0)
if blank_position not in [2, 5, 8]: # means that blank is not on the last row
puzzle = self.state.copy()
puzzle[blank_position], puzzle[blank_position + 1] = puzzle[blank_position + 1], puzzle[blank_position]
return puzzle
else: # if illegal state
return None
class PriorityQueue:
# Initialize the instance
def __init__(self):
# Create a list to use as the queue
self._queue = []
# Create an index to use as ordering
self._index = 0
# Create a function to add a task to the queue
def append(self, item, priority):
# Push the arguments to the _queue using a heap
heapq.heappush(self._queue, (-priority, self._index, item))
# Add one to the index
self._index += 1
# Create a function to get the next item from the queue
def pop(self):
# Return the next item in the queue
return heapq.heappop(self._queue)[-1]
def __str__(self):
return str(self._queue)
def generate_solvable_puzzle():
while True:
puzzle = [1, 2, 3, 4, 5, 6, 7, 8, 0]
shuffle(puzzle)
# print(puzzle)
inversions = 0
for i in range(len(puzzle)):
for j in range(i+1, len(puzzle)):
if puzzle[j] > puzzle[i]:
inversions += 1
if inversions % 2 == 0:
return puzzle
else:
print('Generated an unsolvable puzzle, trying again')
if __name__ == '__main__':
main()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment