StyleInCode

""" 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)