Skip to content

Instantly share code, notes, and snippets.

@danong
Last active September 21, 2023 14:24
Show Gist options
  • Save danong/96e0ffa0fcb06c459787 to your computer and use it in GitHub Desktop.
Save danong/96e0ffa0fcb06c459787 to your computer and use it in GitHub Desktop.
# 8 Tile Solver
# Written by Daniel Ong for COEN 166: Artificial Intelligence
#
# A comparison of the real time taken to solve an n tile puzzle using:
# 1. Iterative deepening depth-first search
# 2. Depth-first search
# 3. Breadth-first search
# Tested on the 8 tile puzzle
# Some code adapted from Edd Mann's blog post: http://eddmann.com/posts/using-iterative-deepening-depth-first-search-in-python/
import itertools
import random
import time
def id_dfs(puzzle, goal, get_moves):
def idfs(path, depth):
# unable to search when depth is 0
if depth == 0:
return
# check if goal has been reached
if path[-1] == goal:
return path
# iterate through possible moves
for move in get_moves(path[-1]):
# run this function on unvisited nodes, decrementing depth
if move not in path:
next_path = idfs(path + [move], depth - 1)
if next_path:
return next_path
# runs dfs up to a limit of depth
# depth increases until goal is found
for depth in itertools.count():
path = idfs([puzzle], depth)
if path:
return path
def num_matrix(rows, cols, steps=25):
# fill default puzzle
nums = list(range(1, rows * cols)) + [0]
goal = [ nums[i:i+rows] for i in range(0, len(nums), rows) ]
get_moves = num_moves(rows, cols)
puzzle = goal
# shuffle puzzle
for steps in range(steps):
puzzle = random.choice(get_moves(puzzle))
return puzzle, goal
def num_moves(rows, cols):
def get_moves(subject):
moves = []
zrow, zcol = next((r, c)
for r, l in enumerate(subject)
for c, v in enumerate(l) if v == 0)
def swap(row, col):
import copy
s = copy.deepcopy(subject)
s[zrow][zcol], s[row][col] = s[row][col], s[zrow][zcol]
return s
# north
if zrow > 0:
moves.append(swap(zrow - 1, zcol))
# east
if zcol < cols - 1:
moves.append(swap(zrow, zcol + 1))
# south
if zrow < rows - 1:
moves.append(swap(zrow + 1, zcol))
# west
if zcol > 0:
moves.append(swap(zrow, zcol - 1))
return moves
return get_moves
def dfs(puzzle, goal, get_moves):
# maintain a stack of paths
stack = []
# push the first path into the stack
stack.append([puzzle])
while stack:
# get the first path from the stack
path = stack.pop(0)
# get the last node from the path
node = path[-1]
# path found
if node == goal:
return path
# enumerate all adjacent nodes, construct a new path and push it into the stack
for adjacent in get_moves(node):
if adjacent not in path:
new_path = list(path)
new_path.append(adjacent)
stack.append(new_path)
def bfs(puzzle, goal, get_moves):
# maintain a queue of paths
queue = []
# push the first path into the queue
queue.append([puzzle])
while queue:
# get the first path from the queue
path = queue.pop(0)
# get the last node from the path
node = path[-1]
# path found
if node == goal:
return path
# enumerate all adjacent nodes, construct a new path and push it into the queue
for adjacent in (get_moves(node)):
if adjacent not in path:
new_path = list(path)
new_path.append(adjacent)
queue.append(new_path)
if __name__ == '__main__':
reps = 25
print('Average solution times: ')
# Iterative depth first search
total_time = 0
for i in range(reps):
puzzle, goal = num_matrix(3, 3)
t0 = time.time()
solution = id_dfs(puzzle, goal, num_moves(3, 3))
t1 = time.time()
total_time += t1 - t0
total_time /= reps
print('Puzzle solved using iterative depth first search in', total_time, 'seconds.') # 0.20 seconds
# Depth first search
total_time = 0
for i in range(reps):
puzzle, goal = num_matrix(3, 3)
t0 = time.time()
solution = id_dfs(puzzle, goal, num_moves(3, 3))
t1 = time.time()
total_time += t1 - t0
total_time /= reps
print('Puzzle solved using depth first search in', total_time, 'seconds.') # 0.37 seconds
# Breadth first search
total_time = 0
for i in range(reps):
puzzle, goal = num_matrix(3, 3)
t0 = time.time()
solution = bfs(puzzle, goal, num_moves(3, 3))
t1 = time.time()
total_time += t1 - t0
total_time /= reps
print('Puzzle solved using breadth depth first search in', total_time, 'seconds.') # 0.04 seconds
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment