#include <stdio.h>
#include <stdlib.h>

typedef struct node
{
  int matrix[3][3];
  int distance_depth;
  struct node *next;
}node ;

node *glob;

int CountDist(int matrix[3][3]){
int distance,i,j,help,a,b;

distance=0;
for (i=0;i<3;i++)
    for (j=0;j<3;j++){
            if (matrix[i][j] != 9){
        help = matrix[i][j];
        b = ((help-1) % 3);
        a = ((help-1) / 3);
        distance += abs(a-i) + abs(b-j);
       // printf ("I: %d, J: %d, A: %d, B: %d, distance: %d \n",i,j,a,b,distance);
    }
    }
return distance;
}

void add_to_sorted(int matrix[3][3],int depth){
int i,j,value=0;
    node *curr=NULL,*next,*newnode=(node*)malloc(sizeof(node));

    for (i=0;i<3;i++)
        for (j=0;j<3;j++)
            newnode -> matrix[i][j] = matrix[i][j];

    newnode->distance_depth = CountDist(matrix)+depth;

    newnode->next= NULL;
    if (glob == NULL){
        glob = newnode;
    }
    else{
            curr=glob;
            next = glob->next;
      if (curr->distance_depth >= newnode->distance_depth){
            newnode->next = curr;
            glob = newnode;
            return;
      }/*
        while (curr -> next != NULL && value==0){
            if ((curr->distance_depth<= newnode->distance_depth) && (next->distance_depth >= newnode->distance_depth)){
                curr->next = newnode;
                newnode->next=next;
                value = 1;
                break;
            }

            next=next->next;
            curr = curr->next;
        }
            if (value==0){
            curr->next=newnode;
            newnode->next=next;
            }*/
        }
}

}
int main(){

node *curr,*next;
glob = NULL;
glob_history = NULL;
int newarray[3][3],value=0,i,j,array[3][3] = {{1,2,3},
                                              {4,9,5},
                                              {7,8,6}};//4+0
int goal[3][3] = {{1,2,3},
                  {4,5,6},
                  {7,8,9}};//0+1
int array2[3][3] = {{1,2,4},
                                              {4,9,5},
                                              {7,8,6}};//7+0

int array3[3][3] = {{1,2,8},
                                              {4,9,5},
                                              {7,8,6}};//7+1
curr = glob;
  add_to_sorted(goal,1); //1
  add_to_sorted(array3,1);//6
  //add_to_sorted(array2,0);
 // add_to_sorted(array2,4);

    while(curr != NULL){
        for (i=0;i<3;i++){
                printf("\n");
            for (j=0;j<3;j++)
                printf("%d ", curr->matrix[i][j]);
        }
        printf(" x ");
    curr = curr->next;

    }

return 0;
}