Danny ChaiThis post is pretty nerdy, so be forewarned. It prolly won’t even make sense unless you took CS 121 or CS 221 and even then, prolly not interesting.
So I’ve been trying to find a solution for that sliding block puzzle programmatically. Basically doing some brute force search programs. And it’s not as trivial as it seems. I estimated that it has a really low branching factor so it wouldn’t be that hard, but no, it’s significant enough to be difficult.
So anyway, the first thing I tried was just a depth first search. The problem is, you get into these loops that the search never gets out of. I had already put in a check to make sure it doesn’t try to do an immediate backtrack step (more block 1 up then try to move it back) but that wasn’t enough, there seemed to be simple loops.
So the next thing I did was track all visited states. It’s tricky because you only want to reject a state if you’ve seen it before and if you’ve gotten there in less moves. So I started with a vector of states, each state contains the board state and vector of moves so far. On each new examined state, I’d iterate through and check if there was a match and if so, whether it got there in less moves.
But this iterating to compare turned out to be way too slow. I tried using a hash table with the board state but it started using too much memory. I also tried using a greedy search and A* search – not too successful, because there’s no good heuristic (I was using the Manhattan distance of the ‘A’ piece – a terrible heuristic for this puzzle). The A* search was essentially a breadth first search which was using too much memory. So in the end I decided to go with a greedy search. But still needed to deal with tracking already visited states.
So I changed the way I tracked states – it’s a 6×5 puzzle, and there are 14 pieces, so I made a board position be represented by 5 base 15 numbers (1 for the space). That way I could use a hash table to quickly look up whether a table position’s been seen before, with the value being how many moves it took to get there.
Eric then made some suggestions – he pointed out that some of the pieces are identical, so in tracking a board position, I don’t need to have 15 possible values, just 7. So I switched to representing the board with 6 base 8 numbers (base 8 for quick calculation and each number representing 5 positions so it fits into a short int to use less memory).
It was still going pretty slow. Probably would take days to finish. I examined one of the states the problem was the search was considering pretty dumb routes first. Like moves two pieces one way, then moves another piece, then moves those first two pieces back, and keeps going back and forth with the little pieces. So it takes tons of moves to get to a position you could get to in just a few.
So I thought maybe I would use a breadth first search, so it would get to these easy positions quicker so eliminate them from further searches. But even with redundant state checking and all this stuff, it still takes up too much memory. It was getting to 2.5 GB virtual memory size and page swapping to death. Wasn’t working.
So it’s back to greedy search on an overnight run. I’ll let you know if it finds a solution. And if you have suggestions on how to improve the program, let me know.
Wow, that was boring. I’m guessing zero people read the whole thing. Maybe Eric. But yeah, if you made it, you get a special prize.