// CSC444H1F Solution Code for Assignment 1 (with no input validation).
//  By Prof. Penny, November 8, 2006
//  Release Notes:
//    - Added Manhattan Distance
//        - Sorted the moves in "solve" by closest to solution first.
//            - Reduced run-time to 55% of alternative.
//        - Tried a simpler version using only the Manhattan distance of the blank square
//            - Did surprisingly well (65%) but not better than global distance
//        - Optimized computation of distance
//            - Use a lookup table for individual tile distances
//            - Do incremental changes to distance when moving
//    - Move Undo
//        - Previous release copied board anew before each move.
//        - This release undoes the move.
//        - Reduced run-time to 95%
//    - Distance Optimizations
//        - Since keeping distances, able to perform certain operations more efficiently
//        - isSolved() reduced to one comparison
//        - isSameBoard() checks if distances are the same first.
//        - check for blank row,col the same still speeds things up even with above
//    - Asserts
//        - added copious assertions inspired by tutorial
//        - spotted some nascent defects very early on
//     

#include <memory.h>
#include <stdlib.h>
#include <stdio.h>
#include <malloc.h>
#include <assert.h>

// undefine to enable assertions
#define NDEBUG

const int MaxN     = 99;    // for input validation
const int MaxDepth = 30;    // Would take over 1 day to solve depth 30

int N;                  // Board dimension
int BoardBytes;         // Bytes to allocate for each board structure (below)
int InfiniteDistance;   // No distances are equal to or greater than this

int boardDistance(struct board* b); // forward declarion for use by isValid(board)

// Need to keep track of all boards in the current depth-first search
// in order to both
//  1. remember the sequence of moves
//  2. ensure we are not loooping
struct board {
    int move;       // Index into "moveDirections" for next move for this board
    int distance;   // Manhattan distance to solution
    int blankRow;   // 0..N-1
    int blankCol;   // 0..N-1
    int tiles[1];   // indexed as tiles[row*N+col] - will allocate sufficient storage for NxN
} *boards[MaxDepth+1];


// Return true iff "b" is a valid board.
// Ignore the stored distance if "otherThanDistance" is true.
bool isValid(struct board *b, bool otherThanDistance = false ) {
    bool *found = (bool*)malloc(sizeof(bool)*N*N);
    for(int i=0; i < N*N; i++) found[i] = false;

    for(int row = 0; row < N; row++)
        for(int col = 0; col < N; col++) {
            int tile = b->tiles[row*N+col];

            // range check tile
            if( tile < 0 || N*N-1 < tile ) return false;

            // check if already appeared
            if( found[tile] ) return false;
            found[tile] = true;

            // check if blank square recorded correctly
            if( tile==0 )
                if( b->blankCol != col || b->blankRow != row ) return false;
        }

    // done if we do not check distance
    if( otherThanDistance ) return true;

    return b->distance == boardDistance(b);
}



// Static array of possible move directions for the blank square
const int NumMoveDirections = 4;
struct MoveDirection {
    int row;            // -1,0,+1
    int col;            // -1,0,+1
    const char *name;   // user-readable name of this move
    int opposite;       // 0-3 the move that undoes this move
} moveDirections[NumMoveDirections] =
{ {-1,0,"up",1}, {+1,0,"down",0}, {0,-1,"left",3}, {0,+1,"right",2} };


// Stores pre-computed distances for the various tiles in the various locations.
// See "tileDistance()" below for how to index this array
int *tiledist; // array of integers of dimension [N*N][N][N]

// Return the number of moves required to move "tile" from "row,col"
// to its correct final destination.
int tileDistance(int tile, int row, int col) {
    assert(0<=tile && tile<N*N && 0<=row && row<N && 0<=col && col<N);
    return tiledist[(tile*N + row)*N + col];
}

// Initialize the "tiledist" array
void initDistance() {
    tiledist = (int*)malloc(N*N*N*N*sizeof(int));

    // Iterate through each tile
    for(int trow = 0; trow < N; trow++)
        for(int tcol = 0; tcol < N; tcol++) {
            int tile = trow*N+tcol+1;
            if( tile == N*N ) tile = 0;

            // "trow,tcol" is where "tile" is in the solution.
            // Iterate through each location it could be in.
            for(int row = 0; row < N; row++)
                for(int col = 0; col < N; col++) {
                    // if row,col is where tile is, distance is as follows
                    tiledist[ (tile*N + row)*N + col ] = abs(tcol-col) + abs(trow-row);
                }
        }

    // N*N tiles, max distance of each tile is N-1 in each of the 2 dimensions.
    InfiniteDistance = N*N * 2*(N-1) + 1;
}

// Return the distance of the board "b" from the solution.
// Only ever used once for the initial input board.
int boardDistance(struct board* b) {
    assert( isValid(b,true) );
    int d = 0;
    for(int row=0; row < N; row++)
        for(int col=0; col < N; col++)
            d += tileDistance(b->tiles[row*N+col],row,col);
    return d;
}

// Return the new distance if we moved the blank in board "b" in direction "md".
// Return InfiniteDistance if the move is not possible.
int moveDistance(struct board* b, int md) {
    assert( isValid(b) && 0<=md && md<NumMoveDirections );

    // Compute new blank positions and return InfiniteDistance if out of range
    int blankRow = b->blankRow + moveDirections[md].row;
    if( blankRow < 0 || blankRow >= N ) return InfiniteDistance;
    int blankCol = b->blankCol + moveDirections[md].col;
    if( blankCol < 0 || blankCol >= N ) return InfiniteDistance;

    // The tile that will move
    int tile = b->tiles[blankRow*N+blankCol];

    // The new distance is the old, subtract out the two places that changed
    // in the old board, add in the two places that changed in the new board.
    //   tile at blankRow,blankCol is moving to b->blankRow,b->blankCol
    //   blank (0) at b->blankRow,b->blankCol is moving to blankRow,blankCol
    return b->distance
        - tileDistance(0,b->blankRow,b->blankCol) - tileDistance(tile,blankRow,blankCol)
        + tileDistance(tile,b->blankRow,b->blankCol) + tileDistance(0,blankRow,blankCol);
}


// Apply the move in direction "md" to the board "b".
// Set distance to the previously computed "newDistance".
void move(struct board* b, int md, int newDistance ) {
    assert( isValid(b) && 0<=md && md<NumMoveDirections && moveDistance(b,md)!=InfiniteDistance);

    // Compute new blank position.
    int blankRow = b->blankRow + moveDirections[md].row;
    int blankCol = b->blankCol + moveDirections[md].col;

    // Tile at new blank position is moving to old.
    b->tiles[b->blankRow*N+b->blankCol] = b->tiles[blankRow*N+blankCol];

    // Record new blank position.
    b->blankCol = blankCol;
    b->blankRow = blankRow;

    // Move the blank tile (required for efficient isSameBoard() and easy printing).
    b->tiles[blankRow*N+blankCol] = 0;

    // Stach the new distance
    b->distance = newDistance;

    assert( isValid(b) );
}


// Return if the board "b" is in the correct final position or not.
bool isSolved(struct board *b) {
    assert( isValid(b) );
    return b->distance == 0;
}


// Return if board "b1" is the same configuration as board "b2" or not.
bool isSameBoard(struct board *b1, struct board *b2) {
    assert( isValid(b1) && isValid(b2) );

    // Not the same if different distances.
    if( b1->distance != b2->distance ) return false;

    // Not the same if different blank square,
    if(b1->blankCol != b2->blankCol || b1->blankRow != b2->blankRow ) return false;

    // Different if any tile is different.
    for(int i=0; i < N*N; i++) if( b1->tiles[i] != b2->tiles[i] ) return false;

    // Otherwise must be the same.
    return true;
}


// Dump board "b" to stdout for debug purposes.
// Indent 2*level spaces.
void prBoard(int level, struct board *b) {
    printf("\n");
    for(int row = 0; row < N; row++) {
        for(int i = 0; i < level*2; i++) printf(" ");
        for(int col = 0; col < N; col++) printf("%02d ",b->tiles[row*N+col]);
        if( row == N-1 ) printf(" d=%d", b->distance );
        printf("\n");
    }
}


// Attempt to solve the board at "board[curlevel]".
// Do not recurse deeper than "maxlevel" in total.
// Return if successful at solving the board within maxlevel moves.
bool solve(int maxlevel, int curlevel) {
    // alias for current board
    struct board *curb = boards[curlevel];
    assert( isValid(curb) );

    // Return solved if this board represents a solution
    if( isSolved(curb) ) return true;

    // Return with no solution if at maximum depth
    if(curlevel == maxlevel) return false;

    // Return with no solution if seen this board before on this descent (a move loop)
    for(int n=curlevel-1; n>=0; n--) if( isSameBoard(curb,boards[n]) ) return false;

    // Pre-compute the distances for each possible next board.
    // Store the distances into "moveDistances".
    // Store InfiniteDistance if the move is not possible.
    // Keep track of the number of possible moves in "numMoves".
    int moveDistances[NumMoveDirections];
    int numMoves = 0;
    for(int md = 0; md < NumMoveDirections; md++)
        if( (moveDistances[md]=moveDistance(curb,md)) < InfiniteDistance ) numMoves++ ;

    // Copy the current board into the next candidate board
    struct board *nextb = boards[curlevel+1];
    memcpy(nextb,curb,BoardBytes);

    // Iterate through all possible moves
    while( numMoves > 0 ) {
        assert( isSameBoard(curb,nextb) );

        // Store the move with the lowest distance into "nextMove".
        int nextMove;
        int lowestSoFar = InfiniteDistance;
        for(int move = 0; move < NumMoveDirections; move++)
            if( moveDistances[move] < lowestSoFar ) {
                nextMove = move;
                lowestSoFar = moveDistances[move];
            }
        assert( lowestSoFar < InfiniteDistance );
        assert( 0 <= nextMove && nextMove < NumMoveDirections );

        // Make the move and store the pre-computed distance.
        move(nextb, nextMove, moveDistances[nextMove]);
        assert( isValid(nextb) );

        // Attempt to solve this new board in one less move.
        if( solve(maxlevel,curlevel+1) ) {
            // Record which move we took and return success.
            curb->move = nextMove;
            return true;
        }

        // Record that we eliminated one  move with the pre-decrement and test if not last.
        if( --numMoves > 0 ) {
            // Still more moves to try.

            // Ensure the last move tried is not chosen again.
            moveDistances[nextMove] = InfiniteDistance;

            // Reset the next board back to "curb" (this is faster than re-copying).
            move(nextb, moveDirections[nextMove].opposite, curb->distance);
        }
    }

    // Could not solve after all legal moves - no solution from the current board.
    return false;
}



// Driver routine.
// Input the dimension of the board followed by the board.
// Output the minimal move sequence.
int main(int argc, char* argv[]) {
    // Read the size of board into "N".
    scanf("%d",&N);
    if( N <= 0 || MaxN < N ) {
        printf("Invalid dimension input\n");
        return 1;
    }

    // Initialize the data strucure used to compute Manhattan distance to solution.
    initDistance();

    // Allocate board "stack" storage.
    BoardBytes = sizeof(struct board) + sizeof(int)*(N*N-1);
    for(int n=0; n<=MaxDepth; n++) boards[n] = (struct board*)malloc(BoardBytes);

    // Input the board into "boards[0]".
    for(int row=0; row<N; row++)
        for(int col=0; col<N; col++) {
            scanf("%d",&(boards[0]->tiles[row*N+col]));
            if( boards[0]->tiles[row*N+col] == 0 ) {
                // this is the blank space
                boards[0]->blankCol = col;
                boards[0]->blankRow = row;
            }
        }
    if( !isValid(boards[0],true) ) {
        printf("Invalid board input\n");
        return 1;
    }

    // Compute the distance of the initial board
    boards[0]->distance = boardDistance(boards[0]);

    // Depeen the search one move at a time
    for(int maxlevel = 0; maxlevel <= MaxDepth; maxlevel++) {
        assert( isValid(boards[0]) );

        // Can we solve within "maxlevel" moves?
        if( solve(maxlevel,0) ) {
            // If yes, print out the move sequence that solves it
            printf("Solved in %d moves\n", maxlevel);
            for(int n=0; n<maxlevel; n++)
                printf("%d - %s\n", boards[n]->distance, moveDirections[boards[n]->move].name);
            return 0;
        }
    }

    // Could not find a solution
    printf("No solution found in %d moves.\n", MaxDepth);
    return 1;
}