Fifteen puzzle modifications algorithm

Question

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.

Answer 1

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.

Answer 2

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.