Klotski Adventure — Part 2

If you want play and feel klotski. www.schoolarchimedes.com
Now,to get shortest solution is no brainer, just use BFS.

start_time = time.time()
vis = set()
par = {b: None}
q = [b]
vis.add(b.eff_key())
sol_found = False
cur_board = None
while len(q) > 0:
    cur_board = q[0]
    q = q[1:]
    next_boards = cur_board.all_boards(vis)
    for board in next_boards:
        if board.eff_key() not in vis:
            q.append(board)
            vis.add(board.eff_key())
            par[board] = cur_board
            if board.solved():
                cur_board = board
                sol_found = True
                break
    if sol_found:
        break


solution = []
if sol_found:
    while cur_board != None:
        solution.append(cur_board)
        cur_board = par[cur_board]
    solution.reverse()
    for sol in solution:
        sol.print_grid()
    print("found in ",len(solution)," steps")

print("done in ", time.time() - start_time)

shortest solution found in 116 steps 🤔
done in 7.02 sec 🤦‍♂️
What,Why is shortest solution is 116 steps? BFS can’t be wrong.
Quick search reveals that 81 step solution cheats by moving 1 or more in single move.

Now, that shortest solution is achieved. what the hell happened with time execution time.
1 choke point is obvious

• all_boards method in Board class,all the pieces are checked if they can moved, only pieces around empty squares can be checked.
  But i don’t want to change it, as it there will be more empty squares in MoveIt.
  This is Plain BFS, let me try A* search with H-score as Manhattan Distance of red piece(2x2 piece) and target location.

#Showing Diff for Brevity
class Board:
    def __init__(self, pieces=None):
        ...
        piece = self.piece_map[0]
        self.dist = abs(piece.srow-3) + abs(piece.scol - 1)
    
    #auxillary functions for Heap  
    def __lt__(self, other):
        return self.dist < other.dist

    def __gt__(self, other):
        return self.dist > other.dist
        
#BFS Changes
while len(q) > 0:
    cur_board = heapq.heappop(q)
    ...
        if board.eff_key() not in vis:
            heapq.heappush(q,board)
    ...

G-score if i take the 1 for each step, It is as slow as plain BFS. So, I got rid of G-score 🤞
solution found in 381 steps 🤦‍♂️
done in 1.62 🤦‍♂️
This is not good,I din’t get shortest solution and time is worse than DFS for similar step solution.
I tried a bunch of G&H-scores but nothing gave shortest solution but time fluctuated around 1–2 sec, Will see if any other optimization comes to mind later.
I will close this Part with few puzzles solved,
Before solving,Height,Width target location should be made global,Piece class needs to be modified so that it can support the variety of pieces in MoveIt game
Now piece has a grid of it own.so weird shapes(even with holes/cuts in it like below) can be taken care of.

all the same types of pieces are assigned a number/id, so different pieces of same type swapped can be treated as single board

Before getting into solution.Here’s how app looks

Now,lets solve few puzzles i found with bigger board size(since bigger grid are more time complex)

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

with these board configurations, I tried following approaches
DFS/Backtracking, but nothing found, python dead with recursion limit
Plain BFS, solved with target steps for 1st puzzle in 6 min 💀 kma, 2nd puzzle not even in done in 10 min
A* search, solved both of them in 1–2 sec not with target solution but reasonable ~100 step solution
Not good enough but OK.
Lets see if I can get to that target solution with some G-H-score for A* search or better approach than brute force in the next adventure.