Solve "fifteen puzzle" of size M*N in O((M+N)*M*N) time and determine solveability in O(M*N) time. Originally started for an EIO task.

fifteenpuzzle.c

#include <stdio.h>
#include <string.h>
#include <stdbool.h>
#include <malloc.h>

// input file is named pusle.sis and on the first row there should be
// dimensions of the puzzle, then all tiles should follow (separated by whitespace)
// Example:
// 2 3
// 1 2 3
// 0 4 5

#define SWAP(A, B) {struct memt { char C[sizeof(A)];} mem;\
    mem = *( struct memt*) &A;\
    *( struct memt*) &A = *( struct memt*) &B;\
    *( struct memt*) &B = mem;}

int M, N; // board size: vertical and horisontal size
unsigned int** board; // global array used to store the current configuration
bool** locked; // 1 if the tile should not be moved implicitly
unsigned int* X; // X[i] is the x (vertical) location of tile i
unsigned int* Y; // Y[i] is the y (vertical) location of tile i
FILE* valf; // globallly accessible file where the solving sequence will be written

bool is_odd(unsigned int sequence[],unsigned int len) {
	// check whether of a permutation of numbers 0..len-1 is odd or even
    // each number must occur exactly once, segfault/infinite loop otherwise
	unsigned int seq[len];
	memcpy(seq,sequence,sizeof(unsigned int)*len);
	bool ret = 0; // calculations wrap mod 2, we could also count swaps.
	unsigned int i = 0;
	while (i<len) {
		if (i == seq[i]) {
			i++; // if position i has number i, continue
		} else {
            // otherwise put the number in it's place and what is left over to position i
			SWAP(seq[seq[i]],seq[i]);
			ret = !ret;
		}
	}
	return ret;
}
bool issolveable() {
	// check whether the puzzle is solvable. All calculations modulo 2.
	// we just need to know whether the required number of moves 
	// is even or odd - we never can do an odd one.
	// number of moves needed = distance from blank to lower right corner +
	// + number of substitutions needed to sort other numbers +
	// + N*M (to move blank from the beginning to the end after sorting)
	//  If Nsubs is even this is solvable, so return Nsubs XOR 1.
	return (X[0]&1)^(Y[0]&1)^(M&1)^(N&1)^is_odd(board[0],M*N)^(1&M&N);
}

void move(unsigned char command) {
    // Move a tile towards the specified direction onto the blank
	unsigned int x = X[0], y = Y[0]; // location of the tile to be moved
	switch(command) { // derived from the location of the blank and direction
	    case 'W': y++; break;
	    case 'E': y--; break;
		case 'N': x++; break;
		case 'S': x--; break;
	}
	unsigned int n = board[x][y]; // number to be moved
	SWAP(board[x][y],board[X[0]][Y[0]]);
	SWAP(X[0],X[n]); SWAP(Y[0],Y[n]);
	fprintf(valf,"%c",command);
}

void moveseq(char seq[]) { // execute multiple sequential moves
	unsigned int i;
	for (i=0;;i++) {
		if ( (seq[i] == 'N') || (seq[i] == 'S') || (seq[i] == 'E') || (seq[i] == 'W')) {
			move(seq[i]);
		} else break;
	}
}

int sgo(int a) { // 1 with the sign of the argument or 0 for 0
	if (a > 0) return 1;
	if (a < 0) return -1;
	return 0;
}

void moveblank(unsigned int targetx, unsigned int targety) {
    // move the blank "tile" to location (targetx,targety)
    // Assumes that no two tiles are locked side by side in a row below the target
	int vertical, horisontal, s; // remaining distances per direction; reusable sign var
	while ( (targety != Y[0]) || (targetx != X[0]) ) { // not there yet
		while (targety != Y[0]) { // not in the correct column yet
			horisontal = targety - Y[0]; // remaining number of steps to go right
			s = sgo(horisontal); // one if the blank is supposed to move right, -1 if up
			if (locked[X[0]][Y[0]+s]) { // we can not go left or right as needed
				if (X[0] < M-1) move('N'); // move down, if we are not in the lowest row
				else move('S'); // if that also is impossible, go up.
			} // now we can go left or right as needed.
			if (s == 1) move('W');
			else move('E');
		}
		
		while (targetx != X[0]) { // not in correct row yet
			vertical = targetx - X[0]; // remaining number of steps to go down
			s = sgo(vertical); // 1 if the blank has to go down, -1 if up
			if (locked[X[0]+s][Y[0]]) { // we can not go up or down as needd
				if (Y[0] < N-1) move('W'); // go right if we are not in the rightmost column
				else move('E'); // if we are, go left instead
			} // now we can go up or down as needd
			if (s == 1) move('N');
			else move('S');
		}
	}
}

void movetile(unsigned int n, unsigned int targetx, unsigned int targety) {
    // move the tile `n` to location (targetx,targety)
	int vertical, horisontal, s; // again remaining distances and sign
	vertical = targetx - X[n]; // how many more steps down?
	horisontal = targety - Y[n]; // how many more steps right?
	while (horisontal) { // tile not in target column
		s = sgo(horisontal); // 1 when going right, -1 when left
		locked[X[n]][Y[n]] = 1; // do not make the situation worse, lock the tile
		moveblank(X[n],Y[n]+s); // and move the blank to the next position
		locked[X[n]][Y[n]] = 0; // then unlock our tile
		if (s == 1) move('E'); // and move it onto the blank
		else move('W');
		horisontal -= s; // also change the remaining horisontal distance
	}
	while (vertical) { // not in target row
		s = sgo(vertical); // 1 when going down, -1 when up
		locked[X[n]][Y[n]] = 1; // do not move our tile away while
		moveblank(X[n]+s,Y[n]); // moving the blank to our next desired location
		locked[X[n]][Y[n]] = 0; // now we can move the til
		if (s == 1) move('S'); // onto the blank
		else move('N');
		vertical -= s; // we moved `s` steps down, mark it down
	}
}

void solve_the_puzzle() {
	int i,j;
	if ( (N > 1) && (M > 1) ) { // puzzle with only one row or column is easy, no special tricks for it.
        for (i=0;i<(M-2);i++) { // all rows except the last twp
            for (j=0;j<(N-1);j++) { // all columns except the last one
                movetile(i*N+j+1,i,j); // just place the rihgt tile in place
                locked[i][j] = 1; // and lock that
            }
            if (board[i][N-1] != (i+1)*N) { // last colmumn (if it happens to have the correct tile, skip on)
                movetile((i+1)*N,i+1,N-1); // move the tile directly below it's target location
                if (board[i][N-1] == 0) { // if the blank ended up in the target location
                    move('N'); // just move the tile there
                } else {
                    locked[i+1][N-1] = 1;
                    moveblank(i+2,N-1); // move the blank directly below the tile, without moving the tile
                    locked[i+1][N-1] = 0;
                    if (board[i][N-1] != (i+1)*N) { // if tile did not end up in the right place by chance
                        locked[i][N-2] = 0; // unlock the location directly left of the location where we want the tile to be
                        moveseq("SESWNESWNNESSWN"); // move the tile in place (teh one ont the left also arrives at the correct location)
                        locked[i][N-2] = 1; 
                    }
                }
            }
            locked[i][N-1] = 1; // lock the last tile of the row
        }
        // last two rows
        for (j=0; j<(N-2); j++) { // all columns except the two rightmost ones
            movetile((M-2)*N+j+1,M-2,j); // fix the j-th tile of the next-to-last row
            locked[M-2][j] = 1; // lock it
            if (board[M-1][j] != (M-1)*N+j+1) { // if the j-th tile of the last row is not correct
                movetile((M-1)*N+j+1,M-1,j+1); // move the correct tile directly to the right of the target location
                if (board[M-1][j] == 0) { // if the blank is in the last row's j-th column,
                    move('W'); // move it right, so the tile ends up in the blank's place
                } else {
                    locked[M-1][j+1] = 1; // lock the tile we just moved
                    moveblank(M-1,j+2); // place the blank directly right of that tile
                    locked[M-1][j+1] = 0; // unlock it
                    locked[M-2][j] = 0; // and the tile in the target column on next-to-last row
                    moveseq("EESWNEWWSEENW"); // move the tile in the last row in place and the one above it back where it was
                }
            }
            locked[M-2][j] = 1; // lock the column of two last rows that we just fixed
            locked[M-1][j] = 1;
        }
        movetile((M-2)*N+(N-1),M-2,N-2); // next-to-last row and column.
    }
    moveblank(M-1,N-1); // no matter how big the board is, the blank has to be in the lower right corner
    // actually we should lock all remaining tiles, but as we are not going to move
    // any tiles anymore, this is not important. We coould unlock all as well.
}

int main(int argc, char **argv) {
	// open the input file and read the metadata
	FILE* sisf = fopen("pusle.sis","r"); // (local variable) input file
	valf = fopen("pusle.val","w+"); // (global variable) output file
	char buf[101]; // buffer for reading file, probably much less is needed
	fgets(buf , 100 , sisf); // first line is size of the board
	if (sscanf(buf, "%d %d", &M, &N) == 1) N = M; // one or two integers
	
	// global data structures defined in the beginning of the file.
	locked = (bool**)			malloc(M * sizeof(bool *));
	board = (unsigned int**)	malloc(M * sizeof(unsigned int *));
	locked[0] = (bool*)			malloc(M*N * sizeof(bool));
	board[0] = (unsigned int *)	malloc(M*N * sizeof(unsigned int));
	X = (unsigned int*)			malloc(M*N * sizeof(unsigned int));
	Y = (unsigned int*)			malloc(M*N * sizeof(unsigned int));
	
	// read initial configuration
	unsigned int i,j;
	for(i = 0; i < M; i++) { // for all rows...
		board[i] = board[0] + i*N; // row pointer
		locked[i] = locked[0] + i*N; // row pointer for locks array
		memset(locked[i],0,N); // no tile locked in the beginning
		for (j=0; j<N; j++) { // and all columns...
			fscanf(sisf, "%s", buf); // read a (space-separated) value
			if (!sscanf(buf,"%d",&board[i][j])) { // if it can be intrepreted as an integer, do so
				if ('A' <= buf[0] && buf[0] <= 'Z') board[i][j] = 10 + buf[0]-'A'; // EIO liked letters instead...
				if (buf[0] == '.') board[i][j] = 0; // the blank can be denoted with '.' in addition to 0
			}
			X[board[i][j]] = i; Y[board[i][j]] = j; // mark down location of the tile just added
		}
	}

	if (issolveable()) solve_the_puzzle(); // magic.
	else fprintf(valf,"EI SAA"); // "EI SAA" is "CANNOT" in Estonian
	fprintf(valf,"\n"); // also add a newline to the sequence of moves or message just output
	fclose(valf);
	return 0;
}