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.
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.
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
Done a DFS/backtracking with board as state to traverse and identifying boards with eff_key method.
first solution found in 950 steps
done in 0.52 sec NOT BAD.
Can be done better.
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.