Solving the 15 Puzzle
A solution for the 15 puzzle.
Solution
""" 15_puzzle.py """
# usage: python3 15_puzzle.py
import collections
import math
import random
import time
random.seed()
def edge(data):
""" size of puzzle edge """
return int(math.sqrt(len(data)))
def new(size=4):
""" size x size puzzle """
return tuple(i + 1 if i < size * size - 1 else 0
for i in range(size * size))
def pretty(data, clear=False):
""" pretty print """
size = edge(data)
output = '\033[2J\033[H\n' if clear else ''
for i in range(size):
row = [f'{j:4}' for j in data[i * size:(i + 1) * size]]
output += ''.join(row + ['\n'])
return output
def move(way, data):
""" move blank this way """
size = edge(data)
output = list(data)
blank = output.index(0)
match way:
case 'up':
if blank < size:
raise ValueError
output[blank] = output[blank - size]
output[blank - size] = 0
case 'right':
if (blank + 1) % size == 0:
raise ValueError
output[blank] = output[blank + 1]
output[blank + 1] = 0
case 'down':
if blank + size > size * size - 1:
raise ValueError
output[blank] = output[blank + size]
output[blank + size] = 0
case 'left':
if blank % size == 0:
raise ValueError
output[blank] = output[blank - 1]
output[blank - 1] = 0
case _:
raise ValueError
return tuple(output)
def scramble(data, count=36):
""" scramble puzzle """
output = data
i = count
while i > 0:
c = random.choice(['up', 'right', 'down', 'left'])
try:
output = move(c, output)
except ValueError:
continue
else:
i -= 1
return output
def moves(data):
""" what moves are possible """
output = []
for c in ['up', 'right', 'down', 'left']:
try:
m = move(c, data)
except ValueError:
continue
else:
output.append(m)
return output
def solve(data):
""" steps to solve puzzle """
state = data
goal = new(size=edge(state))
history = {state: None}
explore = collections.deque([state])
c = state
solved = state == goal
while not solved:
state = explore.pop()
choices = moves(state)
for c in choices:
if c == goal:
solved = True
history[c] = state
break
if c not in history:
explore.appendleft(c)
history[c] = state
output = collections.deque([c])
while c != data:
c = history[c]
output.appendleft(c)
return output
if __name__ == '__main__':
puzzle = scramble(new())
clr = False
for move in solve(puzzle):
print(pretty(move, clear=clr))
if clr:
time.sleep(0.5)
permalink