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

// Only value necessary to change between 8-puzzle and 15-puzzle
#define N 3                     // N x N puzzle size
#define MAXMOVES 4              // potential number of valid tile moves
#define MAXPATH 128             // for N = 3, 31 is worst case

int nodes;                      // Nodes generated to reach solution
int length;                     // Solution length
int path[MAXPATH];              // Solution path

typedef struct                  // Coordinates of a single tile
{
    int i;
    int j;
} Position;


void Initialize(int a[N][N]);
void Scramble(int a[N][N]);
void TranslateMove(int m, int *u, int *v);
void RedirectMove(int *m, int r, int bi, int bj, int *mi, int *mj);
void GenerateMoveList(int a[N][N], int m[MAXMOVES]);
void MakeMove(int a[N][N], int m);
void UndoMove(int a[N][N], int m);
void FindBlank(int a[N][N], int *u, int *v);
void SwapTiles(int a[N][N], Position b, Position c);
void Print(int a[N][N]);
void PrintMove(int move);
int Ida(int a[N][N], int s[MAXPATH]);
int Heuristic(int a[N][N]);
int Search(int a[N][N], int g, int c);


int main(int argc, char **argv)
{
    int i, j, tvalue;
    int puzzle[N][N], trace[N][N];

    tvalue = time(NULL);
    srand(tvalue);
    nodes = 0;
    length = 0;
        
    // Initialize N x N puzzle: 
    Initialize(puzzle);

    for (i = 0; i < MAXPATH; i++)
        path[i] = -1;
            
    // Scramble puzzle to random position
    Scramble(puzzle);
        
    // print intial scrambled state
    printf("Initial random puzzle:\n");
    Print(puzzle);
    
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            trace[i][j] = puzzle[i][j];
    
    // determine optimal solution length
    length = Ida(puzzle, path);
        
    // print solution to solved puzzle
    if (length == 0)
        printf("Already solved!");
    else
    {
        printf("Solution length = %d\n", length);
        printf("Nodes generated = %d\n", nodes);
        printf("Solution path is\n");
                
        for (i = 0; i < length; i++)
        {
            Print(trace);
            printf("Move ");
	    PrintMove(path[i]);
	    printf("\n");
            MakeMove(trace, path[i]);
        }
        Print(trace);
    }    

    return(0);
}


void PrintMove(int move)
{
   switch(move)
   {
      case 0: { printf("Up"); break; }
      case 1: { printf("Right"); break; }
      case 2: { printf("Down"); break; }
      case 3: { printf("Left"); break; }
      default: { printf("End"); break; }
   }
}


// perform IDA* on puzzle
int Ida(int a[N][N], int s[MAXPATH])
{
    int cutoff;
    int cost = 0;

    printf("Processing...\n");
    
    // Calculate heuristic for root
    cutoff = Heuristic(a);
        
    // Search move tree
    // For the tile problem the cutoff increases by two each iteration
    while (Search(a, cost, cutoff) == 0)
        cutoff += 2;
    
    // Return cutoff of optimal solution found
    return(cutoff);
}


int Search(int a[N][N], int g, int c)
{
    int i, h;
    int movelist[MAXMOVES];

    nodes++;
    
    h = Heuristic(a);
                
    if (g + h <= c)     /* f value is below cutoff */
    {
        if (h == 0)
            return(1);
        else
        {    
        
            // Initialize legal moves
            for (i = 0; i < MAXMOVES; i++)
                movelist[i] = 0;
            
            // Determine which moves are legal
            GenerateMoveList(a, movelist);            
            
            // Search each move recursively
            for (i = 0; i < MAXMOVES; i++)
                if (movelist[i] == 1)
                {
                    MakeMove(a, i);
                    
                    if (Search(a, g + 1, c) == 1)
                    {
                        path[g] = i;
                        return(1);
                    }    
                    
                    UndoMove(a, i);
                }
        }                
    }

    return(0);
}


void MakeMove(int a[N][N], int m)
{    
    Position blank, number;
    int u, v;

    // Find the blank's position
    FindBlank(a, &(blank.i), &(blank.j));
        
    TranslateMove(m, &u, &v);
    number.i = blank.i + u;
    number.j = blank.j + v;        

    SwapTiles(a, blank, number);    
}


void UndoMove(int a[N][N], int m)
{    
    Position blank, number;
    int u, v;

    // Find the blank's position
    FindBlank(a, &(blank.i), &(blank.j));
    
    // Find inverse of move m
    m -= 2;
    if (m < 0)
        m += 4;
      
    TranslateMove(m, &u, &v);
    number.i = blank.i + u;
    number.j = blank.j + v;        
    
    SwapTiles(a, blank, number);
}


void FindBlank(int a[N][N], int *u, int *v)
{
   int i, j;

    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            if (a[i][j] == 0)
            {
                *u = i;
                *v = j;
            }
}

    
void GenerateMoveList(int a[N][N], int m[MAXMOVES])
{
    Position blank;
    
    // Find the blank's position
    FindBlank(a, &(blank.i), &(blank.j));
        
    // Validate the four possible moves
    if (blank.i - 1 >= 0)
        m[0] = 1;
    if (blank.j + 1 < N)
        m[1] = 1;
    if (blank.i + 1 < N)
        m[2] = 1;
    if (blank.j - 1 >= 0)
        m[3] = 1;    
}

    
// Calculate heuristic value for current node
int Heuristic(int a[N][N])
{
    int h = 0;
    int i, j;
    Position target;
    
    // Manhattan distance
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            if (a[i][j] != 0)
            {
                // Calculate current tile's target position
                target.i = a[i][j] / N;
                target.j = a[i][j] % N;
                
                // Add current tile's Manhattan distance to heuristic
                h += abs(target.i - i);
                h += abs(target.j - j);
            }
    
    return h;
}


// Initialize N x N puzzle
void Initialize(int a[N][N])
{
    int i, j;

    // 0 represents the blank
    for (i = 0; i < N; i++)
        for (j = 0; j < N; j++)
            a[i][j] = N * i + j;   
}    


void SwapTiles(int a[N][N], Position b, Position c)
{
    int temp;

    temp = a[b.i][b.j];
    a[b.i][b.j] = a[c.i][c.j];
    a[c.i][c.j] = temp;    
}    


// Scramble the N x N puzzle
void Scramble(int a[N][N])
{
    int m;
    
    // Two positions are stored
    //   1) where the blank currently is
    //   2) where the blank was 1 move ago
    Position blank;
    Position lastBlank;
    
    // 1) move represents which of the 4 directions to move
    // 2) if invalid, we use redirection to rotate clockwise or
    //    counterclockwise until a valid move is obtained
    // 3) we disallow undoing the last move during the scramble
    //    (i.e. blank + move != lastBlank
    int move, lastMove, redirection;
    int mi, mj, pi, pj;
    
    int totalMoves = 100;

    // find the blank's position
    FindBlank(a, &(blank.i), &(blank.j));
    
    // initialize lastBlank position
    lastBlank.i = blank.i;
    lastBlank.j = blank.j;
    
    // random first move
    move = lastMove = 1 + rand() % 2;
    
    // make random moves
    for (m = 0; m < totalMoves; m++)
    {
        // get random move to make
        if (m > 0)
            move = rand() % MAXMOVES;
        
        // translate move into i, j coordinates
        TranslateMove(move, &mi, &mj);
       
        // precalculations of potential new position
        pi = blank.i + mi;
        pj = blank.j + mj;

        // disallow invalid moves and undoing last move
        if (pi < 0 || pi >= N || pj < 0 || pj >= N ||
            abs(move - lastMove) == 2)
        {
            // next move = rotating clockwise or counterclockwise until
           //   valid move found
            redirection = rand() % 2;
            RedirectMove(&move, redirection, blank.i, blank.j, &mi, &mj);
        }

        //update history
        lastMove = move;
        lastBlank.i = blank.i;
        lastBlank.j = blank.j;
        blank.i += mi;
        blank.j += mj;
        
        // update game puzzle
        SwapTiles(a, blank, lastBlank);    
    }
}


// Rotate an invalid move until a valid move is obtained
void RedirectMove(int *m, int r, int bi, int bj, int *mi, int *mj)
{
    // Need a placeholder for the newly rotated position    
    int di, dj;
   
    di = bi + *mi;
    dj = bj + *mj;
    while (di < 0 || di >= N || dj < 0 || dj >= N)
    {
        // Rotate m clockwise (r==0) or counterclockwise (r==1)
        if (r == 0)
            *m += 1;
        else *m -= 1;
        
        // Correct bounds of m (0 to 3) after rotations
        if (*m == -1)
            *m = 3;
        if (*m == 4)
            *m = 0;
        
        // Get new rotated position    
        TranslateMove(*m, mi, mj);
        di = bi + *mi;
        dj = bj + *mj;        
    }
}


// Translate move to i, j coordinates
void TranslateMove(int m, int *u, int *v)
{
    switch(m)
    {
        case 0:       /* Move up */
            *u = -1;
            *v = 0;
            break;
        case 1:       /* Move right */
            *u = 0;
            *v = 1;
            break;
        case 2:       /* Move down */
            *u = 1;
            *v = 0;
            break;
        case 3:       /* Move left */
            *u = 0;
            *v = -1;
            break;
        default:
            *u = 0;
            *v = 0;
            break;
    }
}    


// Print the N x N puzzle
void Print(int a[N][N])
{   
    int i, j, k;

    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N; j++)
            if (a[i][j] > 0)
	    {
		for (k=0; k<N-1; k++)
		    printf(" ");
	        printf("%d", a[i][j]);
	    }
            else
	    {
		for (k=0; k<N-1; k++)
		    printf(" ");
	        printf(" ");
            }
                
	printf("\n");
    }    
    printf("\n");
}