Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

What would be a good algorithm for the Fifteen puzzle, if the puzzle is slightly modified in that you only have a small number of pieces that should be placed correctly and these correctly placed pieces can be located anywhere on the board

Say we had the board

1100
1000
0000
000

and we need the shape

111 anywhere in the board so

1110
0000
0000
000

and

0000
0000
0111
000

are winning results.

share|improve this question
    
Do you need a solution, or the fastest possible solution? –  eBusiness Jun 5 '11 at 13:45
    
A clean solution would be acceptable. Doesn't need to be the fastest. –  anonymouse Jun 5 '11 at 17:47
    
Do you need an optimal result? (Maybe this is what eBusiness was asking, but it's not clear if he means fast run time, or shortest solution.) –  user744 Aug 12 '11 at 20:14

2 Answers 2

I propose to solve this with A*. You have your start state, then you get neighbours from this state. Put your neighbours into priorityty queue statesToCheck ( where more valuable is state which has got more pieces on destination places ), also store visited states ( or shortcut from them ) to not visit the same state. Where you have destination state, you must back to start state - you must store information about how this state was created ( for example L - state was created by moving blank piece left ), second you must store "parent state" to know what was previous state in solution. Pseudocode:

Dictionary<StateShortcut, char > moves;
Dictionary<StateShortcut, StateShortcut> previousStates;


solve = false;
queue.Add(startState);
while(queue.count > 0 and solve == false)
{
currentState = queue.top;
Visit(currentState);
if(IsSolverd(currentState))
{
solve = true;
}
else
{
neighbours = GetNotVisitedNeighbours(currentState);
SetNeighboursValues ( for prioritytyqueue)
for(State state in neighbours)
{
previousStates[state] = currentState;
}

queue.add(neighbours);

}

}

This is only psudocode, but I think you can base on it.

share|improve this answer
    
Maybe my grasp of A* isn't that good but I don't quite follow your idea. What is meant with start state? I don't have a start state, all I have is a pattern that can be created anywhere on the board. –  anonymouse Aug 12 '11 at 18:12

There are only 7280 different positions, you could easily make an index of all of them. Then you could build a solution tree, start from the legal solutions, work out all possible previous positions, put the move required in the index, then from these positions work out the previous positions, register the move in the index etc. It is important that when a position already has a registered move you do not overwrite it but instead just drop that branch.

This way your index will contain the optimal move for every possible position.

Assuming that there is plenty space you could solve the "puzzle" by choosing a solution where there is at least a double wide edge of 0's on the bottom and right side of the figure, then you can systematically build it starting from the upper left corner and working you way towards the bottom right.

share|improve this answer
    
The 4x4 grid was just an example grid, I guess storing all possibilities although a solution is not such a viable solution. –  anonymouse Jun 5 '11 at 11:29
    
@anonymouse Then how about you present the actual problem? –  eBusiness Jun 5 '11 at 12:08
    
I guess I mean that 4x4 is not the only grid size that is required. @eBusiness I am not criticizing your answer, I was not clear in my original post. Your answer is certainly a viable solution had my grid only been 4x4. –  anonymouse Jun 5 '11 at 12:25

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.