Estou trabalhando para encontrar as etapas da solução para um "quebra-cabeça 15" gerado aleatoriamente. Então me diga qual é o melhor algoritmo a ser usado para resolvê-lo rapidamente. Forneça-me uma abordagem para fazê-lo.

Estou criando uma árvore de nós contendo matriz 4 * 4 e percorrendo todos os nós que ainda não foram processados e, quando eu recebo a solução, paro a iteração.

No viewcontroller, tenho algum código como

- (IBAction)getSolution:(id)sender {
while (!appDelegate.isResultFound) {
    TreeNode *node=[self nodeWithLowestCostAndUnproceessedInRootNode];
    [node expandNodeToChilds];
    //break;
}
NSLog(@"Result Found");
if([appDelegate.result isEqualToString:@""])
    NSLog(@"No move required");
else
    NSLog(@"%@",appDelegate.result);

}

-(TreeNode*)nodeWithLowestCostAndUnproceessedInRootNode{
TreeNode *node1;
int lowestCost=200;
for (TreeNode *node in appDelegate.treeNodes) {
    if([node myHeuristicsFunction]<lowestCost&&node.isProcessed==NO){
        node1=node;
        lowestCost=[node.cost intValue];
    }
}
return node1;}

e na classe do nó, estou expandindo o nó como (exceto a movimentação usada pelo pai)

-(void)expandNodeToChilds{
[self checkMovesForEmptyPlace];

if(top.x>=0){
    [self addPuzzleBoxToTreeBySwapingPoint:top withMove:@"Bottom"];
}
if(right.y<=3){
    [self addPuzzleBoxToTreeBySwapingPoint:right withMove:@"Left"];
}
if(bottom.x<=3){
    [self addPuzzleBoxToTreeBySwapingPoint:bottom withMove:@"Top"];
}
if(left.y>=0){
    [self addPuzzleBoxToTreeBySwapingPoint:left withMove:@"Right"];
}
self.isProcessed=true;}

Atualmente, estou usando a distância de manhattan com A *, mas não obtendo o resultado em tempo significativo, a memória do aplicativo aumenta para 1 GB e o aplicativo trava.