Rush hour game algorithm
I was playing a game called rush hour: http://www.freegames.ws/games/freegames/cargames/rushhour.htm
And wrote a computer program to solve it. The algorithm was easy enough:
1. pick a car randomly
2. move it randomly.
3. check if the rad car can exit
4. back to step 1.
This solution of course solves the problem. However, the solution is far from being efficient.
I added some modifications to make it more efficient:
1. For each position I scan for other exact same position, and remove all those between them.
2. If the car moves twice or more in a row, it squeezes it to one move.
These modifications cut off the number of moves substantially. However, I am still far from the optimal solution.
Any suggestions?
[788 byte] By [
cnaanta] at [2007-10-3 5:51:31]
A simple recursive solution should work for small grids like the one in the URL you have.
Keep track of which cars you can move and which cars you cannot move at each iteration. Then pick one of the cars that can move. Recurse on "move that car" and "don't move that car" (and if you have multiple choices for moving, recurse on all of them). Do this for each movable car. This should give you all solutions to the problem. Pick the one which uses the least number of steps.
I think a recursive solution wouldn't work. Let's say cars A and B are the first cars that can be moved. A recursive solution that would go over all the possible solution would move Car A, then Move Car B then Move Car A again etc. Since there can be numerous moves that would not necessarily lead to a dead-end, it takes a lot more than a simple recursive function to solve it.
> Since there can be> numerous moves that would not necessarily lead to a> dead-end, it takes a lot more than a simple recursive> function to solve it.Yep, a simple recursive method will not work here.
> > Since there can be
> > numerous moves that would not necessarily lead to
> a dead-end, it takes a lot more than a simple
> recursive function to solve it.
This URL claims that their solver works using breadth first recursion for small boards.
http://www.theiling.de/projects/rushhour.html
I guess you can do it using a recursive function together with a Set, making sure you wouldn't Add the same position twice. I'll try to do it that way. I will let you know how it worked out.
A standard approach for sliding block problems like this is to observe that there is an underlying graph.
A single node in the graph is a single board position. An edge on the graph is a connection between two positions, where you can get from one position to the other.
Since you can slide cars in either directions (if two positions are related you can get from either one to the other) this is an undirected graph.
If you had the graph, the solution is just a path in this graph from the initial state to the solved state (the one where the red car is off the board, or, if you don't want states with cars off the board, solution is the state where red car is adjacent to the exit hole)
Generating the graph consists of taking a node (and you do start with one node, being the initial board position), looking a each single move that can be made (a single move for rush hour consists of sliding a single car a single step. Do not join them together if you can slide the car 2 steps in the same direction, those are two different board states. Well, actually you can join them if you want, but those are two differnt edges because you get two different board states. Joining them just complicates the enumeration of the moves.)
Each legal move generates a new board position. Well, in truth they are not all new, some of these board positions you have seen before. If you have seen the board position before you can throw it out. If you have not seen it before, add it to the growing list of possible board states. When you store a board state, in the growing list, since that new board position came from applying a single move to a previous position, you can remember that move, or remember the ancestor position that led to this new position. (this way you are not only generating the graph of states, you are also at the same time generating the minimum length path from the initial state to any possible position)
Clearly, if the solution state shows up at any time in this process, you have just generated the path to the solution.
So in psuedo code what you are doing is this
ArrayList boardPositions() = new ArrayList();
ArrayList previousPosition() = new ArrayList();
HashSet positionSet() = new HashSet();
void solve(BoardPosition initialPosition){
boardPositions.add(initialPosition);
previousPosition.add(initialPosition); // no previous position for Eden
i = 0;
boolean done = false;
while(i<boardPositions.size() && ! done){
done = boardPositions.addNewPositions((BoardPosition) boardPositions.get(i))
i++;
}
if(done)emitSolution(); else System.out.println("No Solution Exists.");
}
boolean addNewPositions(BoardPosition bp){
boolean foundSolution = false;
Iterator moves = bp.moveIterator();
while(moves.hasNext()){
Move m = (Move) moves.next();
newbp = bp.makeMove(m);
if(!positionSet.contains(newbp)){
positionSet.add(newbp);
boardPosition.add(newbp);
}
if(bp.solvedState()) {foundSolution = true; break;}
}
return foundSolution;
}
Lastly, Since there are potentially a lot of board positions in the complete graph, it is useful to do some work to keep the representation of any single position small. One useful observation for rush hour is that all cars span at least two squares. This means that a single two square car crosses over the single edge that separates those two squares. You can represent that car on the board by setting a single bit for the edge meaning that that edge is covered by a car. Similarly a 3 square long truck will by itself cover 2 adjacent edges. Between any two cars there must be at least one uncovered edge.
Since the standard board is 6 by 6 squares. The number of vertical edges is a 5 by 6 array (30 bits) and the number of horizontal edges is the same (another 30 bits) This fits into two integers with 4 bits to spare. The red car can be in any of 5 positions and 3 bits is enough to represent a number from 1 to 5. Entire board state can be packed into two 32 bit ints.
For grins, once you have a working solver that generates minimum path solutions when they exist and exhaustively proves that an intitial state has no solution, and given a very compact representation for board states. You can create a gene pool of random board positions, evaluate each one for how difficult the solution is, and run a genetic algorithm, breeding initial states to try to find the most difficult problems.
Just in case you were wondering how the folks that build puzzles do it.
Enjoy!>
thx for the input.
I just finished my Recursive solution which works similar to the graph solution. What I am doing is running over all the possibilities of moves for each car, adding it to a Map that counts how many moves did I use to get there, and at the same time creating an ArrayList of board positions and moves. This is the code for the recursive function:
public void solveRec(int level, Board b) {
if(level==0) {
positions = new HashMap();
boards = new ArrayList();
}
if(checkFinished(b)) {
if(best == null || best.size() > boards.size())
best = (ArrayList)boards.clone();
return;
}
Object o = positions.get(b);
if(o != null) {
int i = ((Integer)o).intValue();
if(i<level)
return;
}
positions.put(b, new Integer(level));
for(int i=1; i><=Car.getCounter(); i++) {
int ar[] = b.getPossibleMoves(b.getCar(i));
for(int a=ar[0]; a <= ar[1]; a++) {
if(a == 0)
continue;
Board b2 = (Board)b.clone();
b2.moveCar(b2.getCar(i), a);
Move m = new Move(b2.getCar(i),a);
BoardAndMove bAndM = new BoardAndMove(b, m);
boards.add(bAndM);
solveRec(level+1, b2);
boards.remove(boards.size()-1);
}
}
}
This however takes a lot of time to run. The program is now running for 15 minutes, and only got to solve the first level in 450 moves. Is this so much different from the graph solution? Will the graph solution improve the preformance substaintially?
Solved it with a graph.
It is actually easier to write than the recursive function. Took me 30 minutes to write, and took the program less than half a second to solve the level 12 problem. The code:
public Board solveGraph(){
positions = new HashMap();
curLevel = new ArrayList();
prevLevel = new ArrayList();
prevLevel.add(board);
positions.put(board, null);
while(prevLevel.size() > 0) {
for(int x=0; x<prevLevel.size(); x++) {
Board b = (Board)prevLevel.get(x);
for(int i=1; i><=Car.getCounter(); i++) {
int ar[] = b.getPossibleMoves(b.getCar(i));
for(int a=ar[0]; a <= ar[1]; a++) {
if(a == 0)
continue;
Board b2 = (Board)b.clone();
b2.moveCar(b2.getCar(i), a);
if(positions.containsKey(b2))
continue;
positions.put(b2, b);
curLevel.add(b2);
if(checkFinished(b2))
return b2;
}
}
}
prevLevel = (ArrayList) curLevel.clone();
curLevel.clear();
}
return null;
}
> It is actually easier to write than the recursive
> function. Took me 30 minutes to write, and took the
> program less than half a second to solve the level 12
And that, sir, is the beauty of algorithms.
Your solver needs to be blazingly fast if you want to use it as a component of a problem generator.
I'd like to see the entire source code of graph solution - would it be possible?thanks in advance
