Klotski Adventure — Part 1

I was casually watching Computerphile sudoku solver episode
And at the end of the video, Prof. Thorsten Altenkirch drops this puzzle Klotski.
Image for post
this simple looking puzzle(goal is to get the red block to bottom of the board) is very tricky to solve.
He asked to solve this using backtracking.
I started, tried to put a good structure(RIP OOPs 😜) so that I can extend this to solve MoveIt game
Let me define piece,since every piece is rectangular, i can use srow (starting row),erow(ending row) etc.
put_in_grid to place it a boards grid and get_boards to get all different boards that can be achieved after moving the piece.

class Piece:
    def __init__(self, x, y, id, type):
        self.srow = x
        self.scol = y
        self.erow = x + type % 2
        self.ecol = y + type // 2
        self.type = type
        self.id = id

    def put_in_grid(self, grid, replace=None):
        for row in range(self.srow, self.erow + 1):
            for col in range(self.scol, self.ecol + 1):
                grid[row][col] = self.id if replace is None else replace

    def get_boards(self, move_board):
        grid = move_board.grid
        piece_map = move_board.piece_map
        new_board = []
        if self.scol - 1 >= 0 and all(
                [grid[row][col] in [-1, self.id] for row in range(self.srow, self.erow + 1) for col in
                 range(self.scol - 1, self.ecol + 1 - 1)]):
            t_board = Board(pieces=piece_map.values())
            t_board.remove_piece(self)
            t_board.add_piece(Piece(self.srow, self.scol - 1, self.id, self.type))
            new_board.append(t_board)
        if self.ecol + 1 < 4 and all(
                [grid[row][col] in [-1, self.id] for row in range(self.srow, self.erow + 1) for col in
                 range(self.scol + 1, self.ecol + 1 + 1)]):
            t_board = Board(pieces=piece_map.values())
            t_board.remove_piece(self)
            t_board.add_piece(Piece(self.srow, self.scol + 1, self.id, self.type))
            new_board.append(t_board)
        if self.srow - 1 >= 0 and all(
                [grid[row][col] in [-1, self.id] for row in range(self.srow - 1, self.erow + 1 - 1) for col in
                 range(self.scol, self.ecol + 1)]):
            t_board = Board(pieces=piece_map.values())
            t_board.remove_piece(self)
            t_board.add_piece(Piece(self.srow - 1, self.scol, self.id, self.type))
            new_board.append(t_board)
        if self.erow + 1 < 5 and all(
                [grid[row][col] in [-1, self.id] for row in range(self.srow + 1, self.erow + 1 + 1) for col in
                 range(self.scol, self.ecol + 1)]):
            t_board = Board(pieces=piece_map.values())
            t_board.remove_piece(self)
            t_board.add_piece(Piece(self.srow + 1, self.scol, self.id, self.type))
            new_board.append(t_board)
        return new_board

Let me define Board with grid to place pieces,piece_map to access pieces
add_piece/remove_piece explanatory
all_boards to get all boards that can be achieved from current board.
eff_key string representation of board,using it as key/identifier to a board

class Board:
    def __init__(self, pieces=None):
        self.grid = [[-1 for col in range(4)] for row in range(5)]
        self.piece_map = {}
        for piece in pieces:
            self.piece_map[piece.id] = piece
            self.add_piece(piece)

    def add_piece(self, piece):
        piece.put_in_grid(self.grid)
        self.piece_map[piece.id] = piece

    def remove_piece(self, piece):
        piece.put_in_grid(self.grid, -1)
        del self.piece_map[piece.id]

    def print_grid(self):
        for row in range(5):
            for col in range(4):
                print(self.grid[row][col], end=' ')
            print('')
        print('______', end='\n\n')

    def all_boards(self,vis):
        next_boards = []
        for piece in self.piece_map.values():
            boards = piece.get_boards(self)
            next_boards.extend(boards)
        return next_boards

    def solved(self):
        return self.grid[4][1] == 0 and self.grid[4][2] == 0

    def eff_key(self):
        grid = self.grid
        return " ".join([str(grid[i][j]) for i in range(5) for j in range(4)])

Done a DFS/backtracking with board as state to traverse and identifying boards with eff_key method.

b = Board(pieces=[Piece(0, 0, 1, 1), Piece(0, 1, 0, 3), Piece(0, 3, 2, 1), Piece(2, 0, 3, 1), Piece(2, 1, 4, 2),
                      Piece(2, 3, 5, 1), Piece(4, 0, 8, 0), Piece(3, 1, 6, 0), Piece(3, 2, 7, 0), Piece(4, 3, 9, 0)])

start_time = time.time()
vis = set()


def dfs(cur_board, sol, vis):
    if cur_board.solved():
        return 1
    vis.add(cur_board.eff_key())
    next_boards = cur_board.all_boards(vis)
    for board in next_boards:
        if board.eff_key() not in vis:
            sol.append(board)
            if (dfs(board, sol, vis)):
                return 1
            sol.pop()
    return 0


solution = []

if dfs(b, solution, vis):
    for board in solution:
        board.print_grid()
    print("found in ", len(solution), " steps")
else:
    print(len(vis))
    
print("done in ", time.time() - start_time)

first solution found in 950 steps
done in 0.52 sec NOT BAD.
Can be done better.

#### Previous eff_key(string Identifier) for board

def eff_key(self):
    grid = self.grid
    return " ".join([str(grid[i][j]) for i in range(5) for j in range(4)])

#### New eff_key
eff_block = {1: "1", 2: "1", 3: "1", 5: "1", 4: "2", 6: "0", 7: "0", 8: "0", 9: "0", 0: "3", -1: "4"}

def eff_key(self):
    grid = self.grid
    return " ".join([str(eff_block[grid[i][j]]) for i in range(5) for j in range(4)])

with Enhanced eff_key method for board.
I treat all the similar block in swapped positions to be same board, this saves some unnecessary recursion.
first solution found in 398 steps
done in 0.25 sec, better
But wiki for this puzzle says the shortest solution for above layout is 81 steps.
Lets see if I can get to that solution , optimize even more and extend the code to solve freaking AIFactory’s Moveit in next adventure.