sokoban for echo phone

sokoban.py

import sys

"""
X = WALL
P = Player
C = Box
E = Emplacement for Box
# = E + P
$ = E + C
"""

def clone_grid(grid):
    return [list(line) for line in grid]

def player_pos(grid):
    for y, line in enumerate(grid):
        for x, v in enumerate(line):
            if v in ('P', '#'):
                return x, y, v

def players_moves(grid):
    px, py, v = player_pos(grid)

    for (dx, dy) in (1, 0), (-1, 0), (0, 1), (0, -1):
        dv = grid[py + dy][px + dx]
        new_grid = clone_grid(grid)
        if dv in (' ', 'E'):
            new_grid[py][px] = ' ' if v == 'P' else 'E'
            new_grid[py + dy][px + dx] = '#' if dv in ('E', '$') else 'P'
            yield new_grid
        if dv in ('C', '$'):
            dv2 = grid[py + dy * 2][px + dx * 2]
            if dv2 in (' ', 'E'):
                new_grid[py][px] = ' ' if v == 'P' else 'E'
                new_grid[py + dy][px + dx] = '#' if dv in ('E', '$') else 'P'
                new_grid[py + dy * 2][px + dx * 2] = 'C' if dv2 == ' ' else '$'
                yield new_grid

def empl_num(grid):
    c = 0
    for y, line in enumerate(grid):
        for x, v in enumerate(line):
            if v in ('E', '#', '$'):
                c += 1
    return c

def finished(grid):
    for y, line in enumerate(grid):
        for x, v in enumerate(line):
            if v in ('E','#'):
                return False
    return True

def print_grid(grid):
    for y, line in enumerate(grid):
        for x, v in enumerate(line):
            print(v, end='')
        print()

def from_str(s):
    return [list(line) for line in s.split('\n') if line]


GRID = from_str("""
XXXXXXXXX
XXXP  XXX
X  CE XXX
X  ECE XX
XXX $C XX
XXX   XXX
XXXXXXXXX
""") # LEVEL 6

#### TESTS ####
grids = list(players_moves(GRID))

assert str(grids[0]) == str(from_str("""
XXXXXXXXX
XXX P XXX
X  CE XXX
X  ECE XX
XXX $C XX
XXX   XXX
XXXXXXXXX
"""))

assert str(grids[1]) == str(from_str("""
XXXXXXXXX
XXX   XXX
X  PE XXX
X  $CE XX
XXX $C XX
XXX   XXX
XXXXXXXXX
"""))


### SOLVE ###

grids_done = set(str(GRID))
grids = [(GRID, None)]

while len(grids) > 0:
    new_grids = []
    print(len(grids), 'grids')
    for todo_grid, prev in grids:
        for grid in players_moves(todo_grid):
            if empl_num(todo_grid) != empl_num(grid):
                print_grid(todo_grid)
                print('-->>')
                print_grid(grid)
                raise AssertionError
            grid_hash = str(grid)
            if grid_hash not in grids_done:
                grids_done.add(grid_hash)
                new_grids.append((grid, (todo_grid, prev)))
            if finished(grid):
                print()
                print('[[FINISHED]]]]')
                print()
                print_grid(grid)
                grid_prev = prev
                while grid_prev:
                    print('<<--')
                    print()
                    print_grid(grid_prev[0])
                    grid_prev = grid_prev[1]
                sys.exit()
    grids = new_grids