import core.stdc.stdlib: abs;
//import std.math: abs;

struct State {
    ulong board;
    short score;
    ubyte emptyPos, lastMoved;
}

struct Solution {
    char[100] sol = void;
    uint len = 0;
}

uint getValue(in ulong board, in uint index) pure nothrow {
    return (((0xfUL << index * 4) & board) >> index * 4) & 0xf;
}

void setValue(ref ulong board, in uint index, in ulong value) pure nothrow {
    board |= value << index * 4;
}

void clearValue(ref ulong board, in uint index) pure nothrow {
    board &= ~(0xfUL << index * 4);
}

uint getTargetPos(in uint c) pure nothrow {
    if (c == 0)
        return 15;
    return c - 1;
}

bool createMove(ref State newState, in ref State lastState,
                in uint maxScore, in int toMove) pure nothrow {
    if (getValue(lastState.board, toMove) == lastState.lastMoved)
        return false;

    newState = lastState;
    newState.emptyPos = cast(ubyte)toMove;
    newState.lastMoved = cast(ubyte)newState.board.getValue(toMove);
    newState.board.clearValue(toMove);
    setValue(newState.board, lastState.emptyPos, newState.lastMoved);
    immutable uint targetPos = getTargetPos(newState.lastMoved);
    immutable uint targetRow = targetPos >> 2;
    immutable int targetCol = targetPos & 0x3;

    if (abs((toMove & 0x3) - targetCol) + abs((toMove >> 2) - targetRow) <
        abs((lastState.emptyPos & 0x3) - targetCol) +
        abs((lastState.emptyPos >> 2) - targetRow)) {
        newState.score++;
    }

    return newState.score <= maxScore;
}

bool dfsSolve(in ref State state, in uint maxScore, ref Solution result) pure nothrow {
    immutable static char[] digits = "0123456789ABCDEF";

    if (state.score > maxScore)
        return false;

    if (state.board == 0x0FEDCBA987654321UL) {
        return true;
    }

    State newState;
    if ((state.emptyPos & 0x3) != 0) {
        if (createMove(newState, state, maxScore, state.emptyPos - 1)) {
            result.sol[result.len++] = digits[newState.lastMoved];
            if (dfsSolve(newState, maxScore, result))
                return true;

            result.len--;
        }
    }

    if ((state.emptyPos & 0x3) != 3) {
        if (createMove(newState, state, maxScore, state.emptyPos + 1)) {
            result.sol[result.len++] = digits[newState.lastMoved];
            if (dfsSolve(newState, maxScore, result))
                return true;

            result.len--;
        }
    }

    if ((state.emptyPos >> 2) != 0) {
        if (createMove(newState, state, maxScore, state.emptyPos - 4)) {
            result.sol[result.len++] = digits[newState.lastMoved];
            if (dfsSolve(newState, maxScore, result))
                return true;

            result.len--;
        }
    }

    if ((state.emptyPos >> 2) != 3) {
        if (createMove(newState, state, maxScore, state.emptyPos + 4)) {
            result.sol[result.len++] = digits[newState.lastMoved];
            if (dfsSolve(newState, maxScore, result))
                return true;

            result.len--;
        }
    }

    return false;
}

void idasSolve(in ref char[16] initialBoard, ref Solution solution) pure nothrow {
    State initialState;

    foreach (immutable i, immutable c; initialBoard) {
        if (c <= '9')
            initialState.board.setValue(i, c - '0');
        else
            initialState.board.setValue(i, c - 'A' + 10);
        if (c == '0')
            initialState.emptyPos = cast(ubyte)i;
    }

    solution.len = 0;
    uint maxScore = 0;
    while (!dfsSolve(initialState, maxScore, solution))
        maxScore++;
}

void main() {
    import std.stdio, std.string;

    const problems = split("9534D168A2CFE7B0
                           364815270EDCA9FB
                           13725604AB8C9DEF
                           237456DE10AF9CB8
                           5123D78406AB9FEC
                           3018592CA74B6DFE
                           23746B8C1DE09AF5
                           5364A018E92CDBF7");

    Solution solution;
    foreach (const line; problems) {
        assert(line.length >= 16);
        immutable char[16] board = line[0 .. 16];
        idasSolve(board, solution);
        writeln(board, " ", solution.sol[0 .. solution.len]);
    }
}


---------------------------

Asm of createMove with core.stdc.stdlib.abs:

_D8puzzle9b10createMoveFNaNbKS8puzzle9b5StateKxS8puzzle9b5StatexkxiZb
...
        call    near ptr _D8puzzle9b12getTargetPosFNaNbxkZk
        mov EDX,030h[ESP]
        and EDX,3
        mov 024h[ESP],EAX
        shr EAX,2
        mov ESI,024h[ESP]
        mov 028h[ESP],EAX
        and ESI,3
        mov 02Ch[ESP],ESI
        sub EDX,02Ch[ESP]
        push    EDX
        call    near ptr _abs
        add ESP,4
        mov ECX,030h[ESP]
        push    EAX
        sub ESP,4
        sar ECX,2
        sub ECX,030h[ESP]
        push    ECX
        call    near ptr _abs
        add ESP,4
        add ESP,4
        mov EBX,EAX
        pop EAX
        add EAX,EBX
        mov EDI,03Ch[ESP]
        push    EAX
        sub ESP,4
        mov DL,0Ah[EDI]
        mov 028h[ESP],EDX
        and EDX,3
        sub EDX,034h[ESP]
        push    EDX
        call    near ptr _abs
        add ESP,4
        mov ESI,EAX
        mov EAX,028h[ESP]
        and EAX,0FFh
        sar EAX,2
        sub EAX,030h[ESP]
        push    EAX
        call    near ptr _abs
        add ESP,4
        add ESP,4
        add ESI,EAX
        pop EAX
        cmp EAX,ESI
        jge L1B4
        inc word ptr 8[EBP]
L1B4:       movsx   ECX,word ptr 8[EBP]
        mov EAX,1
        cmp ECX,038h[ESP]
        jbe L1C5
        xor EAX,EAX
L1C5:       pop EDI
        pop ESI
        pop EBP
        pop EBX
        add ESP,024h
        ret 0Ch

---------------------------

Asm of createMove with std.math.abs:

_D8puzzle9a10createMoveFNaNbKS8puzzle9a5StateKxS8puzzle9a5StatexkxiZb   comdat
...
        call    near ptr _D8puzzle9a12getTargetPosFNaNbxkZk
        mov ESI,030h[ESP]
        and ESI,3
        mov 024h[ESP],EAX
        shr EAX,2
        mov EDX,024h[ESP]
        and EDX,3
        mov ECX,030h[ESP]
        sub ESI,EDX
        mov EBX,ESI
        sar EBX,01Fh
        xor ESI,EBX
        mov 02Ch[ESP],EAX
        sar ECX,2
        sub ESI,EBX
        mov 028h[ESP],EDX
        add ECX,ESI
        mov EAX,03Ch[ESP]
        sub ECX,02Ch[ESP]
        mov DL,0Ah[EAX]
        mov 020h[ESP],EDX
        and EDX,0FFh
        sar EDX,2
        mov EBX,020h[ESP]
        and EBX,3
        sub EBX,028h[ESP]
        mov ESI,EBX
        sar ESI,01Fh
        xor EBX,ESI
        sub EBX,ESI
        add EDX,EBX
        sub EDX,02Ch[ESP]
        cmp ECX,EDX
        jae L18D
        inc word ptr 8[EBP]
L18D:       movsx   ECX,word ptr 8[EBP]
        mov EAX,1
        cmp ECX,038h[ESP]
        jbe L19E
        xor EAX,EAX
L19E:       pop EDI
        pop ESI
        pop EBP
        pop EBX
        add ESP,024h
        ret 0Ch

---------------------------