Ideone.com

fork download

copy

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <stdint.h>
 
typedef uint32_t uint;
 
 
#define ROWS 4
#define COLUMNS ROWS
#define SIZE (ROWS * COLUMNS)
#define BLANK_VALUE (SIZE - 1)
 
typedef uint Cost;
typedef uint64_t Board;
 
typedef struct {
    Board tiles;
    int blank;
} State;
 
typedef struct {
    State *ptr;
    uint length;
} StateArray;
 
typedef struct {
    State *ptr;
    uint length, capacity;
} StateVector;
 
typedef struct {
    State state;
    Cost cost;
} Move;
 
typedef struct {
    StateVector solution;
    bool solved;
    Cost f_limit;
} Solver;
 
 
Cost manhattan[SIZE][SIZE];
 
 
int abs(const int x) {
    return x >= 0 ? x : -x;
}
 
 
void StateVector_append(StateVector *self, const State *x) {
    if (self->length >= self->capacity) {
        if (self->capacity > 0)
            self->capacity *= 2;
        else
            self->capacity = 4;
        self->ptr = realloc(self->ptr, self->capacity * sizeof(State));
        if (self->ptr == NULL)
            exit(1);
    }
    self->ptr[self->length++] = *x;
}
 
StateArray StateVector_slice(StateVector *self) {
    return (StateArray){self->ptr, self->length};
}
 
 
int Board_get(const Board data, const size_t i) {
    return (data >> (i * 4)) & 0xFU;
}
 
void Board_set(Board *data, const size_t i, const size_t value) {
    (*data) &= ~(0xFULL << (i * 4));
    (*data) |= ((Board)value) << (i * 4);
}
 
 
Cost State_h(const State *self) {
    Cost cost = 0;
    for (int i = 0; i < SIZE; i++)
        if (i != self->blank)
            cost += manhattan[i][Board_get(self->tiles, i)];
    return cost;
}
 
 
bool State_is_goal(const State *self) {
    return self->tiles == 18364758544493064720ULL;
}
 
 
bool contains(const StateArray solution, const State *state) {
    for (int i = solution.length - 1; i >= 0; i--)
        if (solution.ptr[i].tiles == state->tiles)
            return true;
    return false;
}
 
 
uint State_successors(const State *self, const StateArray solution, Move moves[4]) {
    uint moves_len = 0;
 
   if ((self->blank + 1) % COLUMNS != 0) {
        State s = {self->tiles, self->blank + 1};
        Board_set(&s.tiles, self->blank, Board_get(self->tiles, self->blank + 1));
        Board_set(&s.tiles, self->blank + 1, BLANK_VALUE);
        if (!contains(solution, &s))
            moves[moves_len++] = (Move){s, 1U};
    }
 
    if ((self->blank - COLUMNS) >= 0) {
        State s = {self->tiles, self->blank - COLUMNS};
        Board_set(&s.tiles, self->blank, Board_get(self->tiles, self->blank - COLUMNS));
        Board_set(&s.tiles, self->blank - COLUMNS, BLANK_VALUE);
        if (!contains(solution, &s))
            moves[moves_len++] = (Move){s, 1U};
    }
 
    if (self->blank % COLUMNS != 0) {
        State s = {self->tiles, self->blank - 1};
        Board_set(&s.tiles, self->blank, Board_get(self->tiles, self->blank - 1));
        Board_set(&s.tiles, self->blank - 1, BLANK_VALUE);
        if (!contains(solution, &s))
            moves[moves_len++] = (Move){s, 1U};
    }
 
    if ((self->blank + COLUMNS) < SIZE) {
        State s = {self->tiles, self->blank + COLUMNS};
        Board_set(&s.tiles, self->blank, Board_get(self->tiles, self->blank + COLUMNS));
        Board_set(&s.tiles, self->blank + COLUMNS, BLANK_VALUE);
        if (!contains(solution, &s))
            moves[moves_len++] = (Move){s, 1U};
    }
 
    return moves_len;
}
 
 
void State_show(const State *self) {
    const char *horiz = "+----+----+----+----+";
    for (int r = 0; r < ROWS; r++) {
        puts(horiz);
        for (int c = 0; c < COLUMNS; c++) {
            const int t = Board_get(self->tiles, r * COLUMNS + c);
            if (t == BLANK_VALUE)
                printf("|    ");
            else
                printf("| %2d ", t);
        }
        printf("|\n");
    }
    puts(horiz);
    puts("");
}
 
 
#define Solver_inf UINT32_MAX
 
Cost Solver_dfs(Solver *self, const State *s, const Cost g) {
    const Cost f1 = g + State_h(s);
    if (f1 > self->f_limit)
        return f1;
    StateVector_append(&self->solution, s);
    if (State_is_goal(s)) {
        self->solved = true;
        return f1;
    }
    Cost f_min = Solver_inf;
 
    Move moves[4];
    const uint moves_len = State_successors(s, StateVector_slice(&self->solution), moves);
 
    for (int i = 0; i < moves_len; i++) {
        const Cost f2 = Solver_dfs(self, &moves[i].state, g + moves[i].cost);
        if (self->solved)
            return f2;
        if (f2 < f_min)
            f_min = f2;
    }
    self->solution.length--;
    return f_min;
}
 
StateArray IDA_star_solve(const State s) {
    Solver solver;
    solver.solution.ptr = NULL;
    solver.solution.length = 0;
    solver.solution.capacity = 0;
    solver.solved = false;
    solver.f_limit = State_h(&s);
 
    while (!solver.solved && solver.f_limit < Solver_inf)
        solver.f_limit = Solver_dfs(&solver, &s, 0);
    return StateVector_slice(&solver.solution);
}
 
 
int main(int argc, char** argv) {
    for (int r = 0; r < SIZE; r++)
        for (int c = 0; c < SIZE; c++)
            manhattan[r][c] = abs(r / COLUMNS - c / COLUMNS) +
                              abs(r % COLUMNS - c % COLUMNS);
 
    const char *input = (argc == 2) ? argv[1] : "0FD1C3B648952A7E";
    Board tiles = 0;
    for (int i = 0; i < strlen(input); i++) {
        const char c = input[i];
        if (c >= '0' && c <= '9')
            Board_set(&tiles, i, c - '0');
        else if (c >= 'A' && c <= 'F')
            Board_set(&tiles, i, c - 'A' + 10);
        else if (c >= 'a' && c <= 'f')
            Board_set(&tiles, i, c - 'a' + 10);
        else
            exit(1);
    }
 
    int blank = 0;
    for (int i = 0; i < SIZE; i++)
        if (Board_get(tiles, i) == BLANK_VALUE) {
            blank = i;
            break;
        }
 
    const StateArray path = IDA_star_solve((State){tiles, blank});
 
    if (path.length == 0) {
        puts("No solutions found.");
    } else {
        printf("Solution in %u moves.\n\n", path.length - 1);
        for (int i = 0; i < path.length; i++)
            State_show(&path.ptr[i]);
    }
 
    return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdGRsaWIuaD4KI2luY2x1ZGUgPHN0ZGJvb2wuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgojaW5jbHVkZSA8c3RkaW50Lmg+Cgp0eXBlZGVmIHVpbnQzMl90IHVpbnQ7CgoKI2RlZmluZSBST1dTIDQKI2RlZmluZSBDT0xVTU5TIFJPV1MKI2RlZmluZSBTSVpFIChST1dTICogQ09MVU1OUykKI2RlZmluZSBCTEFOS19WQUxVRSAoU0laRSAtIDEpCgp0eXBlZGVmIHVpbnQgQ29zdDsKdHlwZWRlZiB1aW50NjRfdCBCb2FyZDsKCnR5cGVkZWYgc3RydWN0IHsKICAgIEJvYXJkIHRpbGVzOwogICAgaW50IGJsYW5rOwp9IFN0YXRlOwoKdHlwZWRlZiBzdHJ1Y3QgewogICAgU3RhdGUgKnB0cjsKICAgIHVpbnQgbGVuZ3RoOwp9IFN0YXRlQXJyYXk7Cgp0eXBlZGVmIHN0cnVjdCB7CiAgICBTdGF0ZSAqcHRyOwogICAgdWludCBsZW5ndGgsIGNhcGFjaXR5Owp9IFN0YXRlVmVjdG9yOwoKdHlwZWRlZiBzdHJ1Y3QgewogICAgU3RhdGUgc3RhdGU7CiAgICBDb3N0IGNvc3Q7Cn0gTW92ZTsKCnR5cGVkZWYgc3RydWN0IHsKICAgIFN0YXRlVmVjdG9yIHNvbHV0aW9uOwogICAgYm9vbCBzb2x2ZWQ7CiAgICBDb3N0IGZfbGltaXQ7Cn0gU29sdmVyOwoKCkNvc3QgbWFuaGF0dGFuW1NJWkVdW1NJWkVdOwoKCmludCBhYnMoY29uc3QgaW50IHgpIHsKICAgIHJldHVybiB4ID49IDAgPyB4IDogLXg7Cn0KCgp2b2lkIFN0YXRlVmVjdG9yX2FwcGVuZChTdGF0ZVZlY3RvciAqc2VsZiwgY29uc3QgU3RhdGUgKngpIHsKICAgIGlmIChzZWxmLT5sZW5ndGggPj0gc2VsZi0+Y2FwYWNpdHkpIHsKICAgICAgICBpZiAoc2VsZi0+Y2FwYWNpdHkgPiAwKQogICAgICAgICAgICBzZWxmLT5jYXBhY2l0eSAqPSAyOwogICAgICAgIGVsc2UKICAgICAgICAgICAgc2VsZi0+Y2FwYWNpdHkgPSA0OwogICAgICAgIHNlbGYtPnB0ciA9IHJlYWxsb2Moc2VsZi0+cHRyLCBzZWxmLT5jYXBhY2l0eSAqIHNpemVvZihTdGF0ZSkpOwogICAgICAgIGlmIChzZWxmLT5wdHIgPT0gTlVMTCkKICAgICAgICAgICAgZXhpdCgxKTsKICAgIH0KICAgIHNlbGYtPnB0cltzZWxmLT5sZW5ndGgrK10gPSAqeDsKfQoKU3RhdGVBcnJheSBTdGF0ZVZlY3Rvcl9zbGljZShTdGF0ZVZlY3RvciAqc2VsZikgewogICAgcmV0dXJuIChTdGF0ZUFycmF5KXtzZWxmLT5wdHIsIHNlbGYtPmxlbmd0aH07Cn0KCgppbnQgQm9hcmRfZ2V0KGNvbnN0IEJvYXJkIGRhdGEsIGNvbnN0IHNpemVfdCBpKSB7CiAgICByZXR1cm4gKGRhdGEgPj4gKGkgKiA0KSkgJiAweEZVOwp9Cgp2b2lkIEJvYXJkX3NldChCb2FyZCAqZGF0YSwgY29uc3Qgc2l6ZV90IGksIGNvbnN0IHNpemVfdCB2YWx1ZSkgewogICAgKCpkYXRhKSAmPSB+KDB4RlVMTCA8PCAoaSAqIDQpKTsKICAgICgqZGF0YSkgfD0gKChCb2FyZCl2YWx1ZSkgPDwgKGkgKiA0KTsKfQoKCkNvc3QgU3RhdGVfaChjb25zdCBTdGF0ZSAqc2VsZikgewogICAgQ29zdCBjb3N0ID0gMDsKICAgIGZvciAoaW50IGkgPSAwOyBpIDwgU0laRTsgaSsrKQogICAgICAgIGlmIChpICE9IHNlbGYtPmJsYW5rKQogICAgICAgICAgICBjb3N0ICs9IG1hbmhhdHRhbltpXVtCb2FyZF9nZXQoc2VsZi0+dGlsZXMsIGkpXTsKICAgIHJldHVybiBjb3N0Owp9CgoKYm9vbCBTdGF0ZV9pc19nb2FsKGNvbnN0IFN0YXRlICpzZWxmKSB7CiAgICByZXR1cm4gc2VsZi0+dGlsZXMgPT0gMTgzNjQ3NTg1NDQ0OTMwNjQ3MjBVTEw7Cn0KCgpib29sIGNvbnRhaW5zKGNvbnN0IFN0YXRlQXJyYXkgc29sdXRpb24sIGNvbnN0IFN0YXRlICpzdGF0ZSkgewogICAgZm9yIChpbnQgaSA9IHNvbHV0aW9uLmxlbmd0aCAtIDE7IGkgPj0gMDsgaS0tKQogICAgICAgIGlmIChzb2x1dGlvbi5wdHJbaV0udGlsZXMgPT0gc3RhdGUtPnRpbGVzKQogICAgICAgICAgICByZXR1cm4gdHJ1ZTsKICAgIHJldHVybiBmYWxzZTsKfQoKCnVpbnQgU3RhdGVfc3VjY2Vzc29ycyhjb25zdCBTdGF0ZSAqc2VsZiwgY29uc3QgU3RhdGVBcnJheSBzb2x1dGlvbiwgTW92ZSBtb3Zlc1s0XSkgewogICAgdWludCBtb3Zlc19sZW4gPSAwOwoKICAgaWYgKChzZWxmLT5ibGFuayArIDEpICUgQ09MVU1OUyAhPSAwKSB7CiAgICAgICAgU3RhdGUgcyA9IHtzZWxmLT50aWxlcywgc2VsZi0+YmxhbmsgKyAxfTsKICAgICAgICBCb2FyZF9zZXQoJnMudGlsZXMsIHNlbGYtPmJsYW5rLCBCb2FyZF9nZXQoc2VsZi0+dGlsZXMsIHNlbGYtPmJsYW5rICsgMSkpOwogICAgICAgIEJvYXJkX3NldCgmcy50aWxlcywgc2VsZi0+YmxhbmsgKyAxLCBCTEFOS19WQUxVRSk7CiAgICAgICAgaWYgKCFjb250YWlucyhzb2x1dGlvbiwgJnMpKQogICAgICAgICAgICBtb3Zlc1ttb3Zlc19sZW4rK10gPSAoTW92ZSl7cywgMVV9OwogICAgfQoKICAgIGlmICgoc2VsZi0+YmxhbmsgLSBDT0xVTU5TKSA+PSAwKSB7CiAgICAgICAgU3RhdGUgcyA9IHtzZWxmLT50aWxlcywgc2VsZi0+YmxhbmsgLSBDT0xVTU5TfTsKICAgICAgICBCb2FyZF9zZXQoJnMudGlsZXMsIHNlbGYtPmJsYW5rLCBCb2FyZF9nZXQoc2VsZi0+dGlsZXMsIHNlbGYtPmJsYW5rIC0gQ09MVU1OUykpOwogICAgICAgIEJvYXJkX3NldCgmcy50aWxlcywgc2VsZi0+YmxhbmsgLSBDT0xVTU5TLCBCTEFOS19WQUxVRSk7CiAgICAgICAgaWYgKCFjb250YWlucyhzb2x1dGlvbiwgJnMpKQogICAgICAgICAgICBtb3Zlc1ttb3Zlc19sZW4rK10gPSAoTW92ZSl7cywgMVV9OwogICAgfQoKICAgIGlmIChzZWxmLT5ibGFuayAlIENPTFVNTlMgIT0gMCkgewogICAgICAgIFN0YXRlIHMgPSB7c2VsZi0+dGlsZXMsIHNlbGYtPmJsYW5rIC0gMX07CiAgICAgICAgQm9hcmRfc2V0KCZzLnRpbGVzLCBzZWxmLT5ibGFuaywgQm9hcmRfZ2V0KHNlbGYtPnRpbGVzLCBzZWxmLT5ibGFuayAtIDEpKTsKICAgICAgICBCb2FyZF9zZXQoJnMudGlsZXMsIHNlbGYtPmJsYW5rIC0gMSwgQkxBTktfVkFMVUUpOwogICAgICAgIGlmICghY29udGFpbnMoc29sdXRpb24sICZzKSkKICAgICAgICAgICAgbW92ZXNbbW92ZXNfbGVuKytdID0gKE1vdmUpe3MsIDFVfTsKICAgIH0KCiAgICBpZiAoKHNlbGYtPmJsYW5rICsgQ09MVU1OUykgPCBTSVpFKSB7CiAgICAgICAgU3RhdGUgcyA9IHtzZWxmLT50aWxlcywgc2VsZi0+YmxhbmsgKyBDT0xVTU5TfTsKICAgICAgICBCb2FyZF9zZXQoJnMudGlsZXMsIHNlbGYtPmJsYW5rLCBCb2FyZF9nZXQoc2VsZi0+dGlsZXMsIHNlbGYtPmJsYW5rICsgQ09MVU1OUykpOwogICAgICAgIEJvYXJkX3NldCgmcy50aWxlcywgc2VsZi0+YmxhbmsgKyBDT0xVTU5TLCBCTEFOS19WQUxVRSk7CiAgICAgICAgaWYgKCFjb250YWlucyhzb2x1dGlvbiwgJnMpKQogICAgICAgICAgICBtb3Zlc1ttb3Zlc19sZW4rK10gPSAoTW92ZSl7cywgMVV9OwogICAgfQoKICAgIHJldHVybiBtb3Zlc19sZW47Cn0KCgp2b2lkIFN0YXRlX3Nob3coY29uc3QgU3RhdGUgKnNlbGYpIHsKICAgIGNvbnN0IGNoYXIgKmhvcml6ID0gIistLS0tKy0tLS0rLS0tLSstLS0tKyI7CiAgICBmb3IgKGludCByID0gMDsgciA8IFJPV1M7IHIrKykgewogICAgICAgIHB1dHMoaG9yaXopOwogICAgICAgIGZvciAoaW50IGMgPSAwOyBjIDwgQ09MVU1OUzsgYysrKSB7CiAgICAgICAgICAgIGNvbnN0IGludCB0ID0gQm9hcmRfZ2V0KHNlbGYtPnRpbGVzLCByICogQ09MVU1OUyArIGMpOwogICAgICAgICAgICBpZiAodCA9PSBCTEFOS19WQUxVRSkKICAgICAgICAgICAgICAgIHByaW50ZigifCAgICAiKTsKICAgICAgICAgICAgZWxzZQogICAgICAgICAgICAgICAgcHJpbnRmKCJ8ICUyZCAiLCB0KTsKICAgICAgICB9CiAgICAgICAgcHJpbnRmKCJ8XG4iKTsKICAgIH0KICAgIHB1dHMoaG9yaXopOwogICAgcHV0cygiIik7Cn0KCgojZGVmaW5lIFNvbHZlcl9pbmYgVUlOVDMyX01BWAoKQ29zdCBTb2x2ZXJfZGZzKFNvbHZlciAqc2VsZiwgY29uc3QgU3RhdGUgKnMsIGNvbnN0IENvc3QgZykgewogICAgY29uc3QgQ29zdCBmMSA9IGcgKyBTdGF0ZV9oKHMpOwogICAgaWYgKGYxID4gc2VsZi0+Zl9saW1pdCkKICAgICAgICByZXR1cm4gZjE7CiAgICBTdGF0ZVZlY3Rvcl9hcHBlbmQoJnNlbGYtPnNvbHV0aW9uLCBzKTsKICAgIGlmIChTdGF0ZV9pc19nb2FsKHMpKSB7CiAgICAgICAgc2VsZi0+c29sdmVkID0gdHJ1ZTsKICAgICAgICByZXR1cm4gZjE7CiAgICB9CiAgICBDb3N0IGZfbWluID0gU29sdmVyX2luZjsKCiAgICBNb3ZlIG1vdmVzWzRdOwogICAgY29uc3QgdWludCBtb3Zlc19sZW4gPSBTdGF0ZV9zdWNjZXNzb3JzKHMsIFN0YXRlVmVjdG9yX3NsaWNlKCZzZWxmLT5zb2x1dGlvbiksIG1vdmVzKTsKCiAgICBmb3IgKGludCBpID0gMDsgaSA8IG1vdmVzX2xlbjsgaSsrKSB7CiAgICAgICAgY29uc3QgQ29zdCBmMiA9IFNvbHZlcl9kZnMoc2VsZiwgJm1vdmVzW2ldLnN0YXRlLCBnICsgbW92ZXNbaV0uY29zdCk7CiAgICAgICAgaWYgKHNlbGYtPnNvbHZlZCkKICAgICAgICAgICAgcmV0dXJuIGYyOwogICAgICAgIGlmIChmMiA8IGZfbWluKQogICAgICAgICAgICBmX21pbiA9IGYyOwogICAgfQogICAgc2VsZi0+c29sdXRpb24ubGVuZ3RoLS07CiAgICByZXR1cm4gZl9taW47Cn0KClN0YXRlQXJyYXkgSURBX3N0YXJfc29sdmUoY29uc3QgU3RhdGUgcykgewogICAgU29sdmVyIHNvbHZlcjsKICAgIHNvbHZlci5zb2x1dGlvbi5wdHIgPSBOVUxMOwogICAgc29sdmVyLnNvbHV0aW9uLmxlbmd0aCA9IDA7CiAgICBzb2x2ZXIuc29sdXRpb24uY2FwYWNpdHkgPSAwOwogICAgc29sdmVyLnNvbHZlZCA9IGZhbHNlOwogICAgc29sdmVyLmZfbGltaXQgPSBTdGF0ZV9oKCZzKTsKCiAgICB3aGlsZSAoIXNvbHZlci5zb2x2ZWQgJiYgc29sdmVyLmZfbGltaXQgPCBTb2x2ZXJfaW5mKQogICAgICAgIHNvbHZlci5mX2xpbWl0ID0gU29sdmVyX2Rmcygmc29sdmVyLCAmcywgMCk7CiAgICByZXR1cm4gU3RhdGVWZWN0b3Jfc2xpY2UoJnNvbHZlci5zb2x1dGlvbik7Cn0KCgppbnQgbWFpbihpbnQgYXJnYywgY2hhcioqIGFyZ3YpIHsKICAgIGZvciAoaW50IHIgPSAwOyByIDwgU0laRTsgcisrKQogICAgICAgIGZvciAoaW50IGMgPSAwOyBjIDwgU0laRTsgYysrKQogICAgICAgICAgICBtYW5oYXR0YW5bcl1bY10gPSBhYnMociAvIENPTFVNTlMgLSBjIC8gQ09MVU1OUykgKwogICAgICAgICAgICAgICAgICAgICAgICAgICAgICBhYnMociAlIENPTFVNTlMgLSBjICUgQ09MVU1OUyk7CgogICAgY29uc3QgY2hhciAqaW5wdXQgPSAoYXJnYyA9PSAyKSA/IGFyZ3ZbMV0gOiAiMEZEMUMzQjY0ODk1MkE3RSI7CiAgICBCb2FyZCB0aWxlcyA9IDA7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IHN0cmxlbihpbnB1dCk7IGkrKykgewogICAgICAgIGNvbnN0IGNoYXIgYyA9IGlucHV0W2ldOwogICAgICAgIGlmIChjID49ICcwJyAmJiBjIDw9ICc5JykKICAgICAgICAgICAgQm9hcmRfc2V0KCZ0aWxlcywgaSwgYyAtICcwJyk7CiAgICAgICAgZWxzZSBpZiAoYyA+PSAnQScgJiYgYyA8PSAnRicpCiAgICAgICAgICAgIEJvYXJkX3NldCgmdGlsZXMsIGksIGMgLSAnQScgKyAxMCk7CiAgICAgICAgZWxzZSBpZiAoYyA+PSAnYScgJiYgYyA8PSAnZicpCiAgICAgICAgICAgIEJvYXJkX3NldCgmdGlsZXMsIGksIGMgLSAnYScgKyAxMCk7CiAgICAgICAgZWxzZQogICAgICAgICAgICBleGl0KDEpOwogICAgfQoKICAgIGludCBibGFuayA9IDA7CiAgICBmb3IgKGludCBpID0gMDsgaSA8IFNJWkU7IGkrKykKICAgICAgICBpZiAoQm9hcmRfZ2V0KHRpbGVzLCBpKSA9PSBCTEFOS19WQUxVRSkgewogICAgICAgICAgICBibGFuayA9IGk7CiAgICAgICAgICAgIGJyZWFrOwogICAgICAgIH0KCiAgICBjb25zdCBTdGF0ZUFycmF5IHBhdGggPSBJREFfc3Rhcl9zb2x2ZSgoU3RhdGUpe3RpbGVzLCBibGFua30pOwoKICAgIGlmIChwYXRoLmxlbmd0aCA9PSAwKSB7CiAgICAgICAgcHV0cygiTm8gc29sdXRpb25zIGZvdW5kLiIpOwogICAgfSBlbHNlIHsKICAgICAgICBwcmludGYoIlNvbHV0aW9uIGluICV1IG1vdmVzLlxuXG4iLCBwYXRoLmxlbmd0aCAtIDEpOwogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgcGF0aC5sZW5ndGg7IGkrKykKICAgICAgICAgICAgU3RhdGVfc2hvdygmcGF0aC5wdHJbaV0pOwogICAgfQoKICAgIHJldHVybiAwOwp9

Success #stdin #stdout 1.03s 1856KB

stdin

copy

Standard input is empty

stdout

copy

Solution in 45 moves.

+----+----+----+----+
|  0 |    | 13 |  1 |
+----+----+----+----+
| 12 |  3 | 11 |  6 |
+----+----+----+----+
|  4 |  8 |  9 |  5 |
+----+----+----+----+
|  2 | 10 |  7 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 | 13 |    |  1 |
+----+----+----+----+
| 12 |  3 | 11 |  6 |
+----+----+----+----+
|  4 |  8 |  9 |  5 |
+----+----+----+----+
|  2 | 10 |  7 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 | 13 |  1 |    |
+----+----+----+----+
| 12 |  3 | 11 |  6 |
+----+----+----+----+
|  4 |  8 |  9 |  5 |
+----+----+----+----+
|  2 | 10 |  7 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 | 13 |  1 |  6 |
+----+----+----+----+
| 12 |  3 | 11 |    |
+----+----+----+----+
|  4 |  8 |  9 |  5 |
+----+----+----+----+
|  2 | 10 |  7 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 | 13 |  1 |  6 |
+----+----+----+----+
| 12 |  3 |    | 11 |
+----+----+----+----+
|  4 |  8 |  9 |  5 |
+----+----+----+----+
|  2 | 10 |  7 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 | 13 |  1 |  6 |
+----+----+----+----+
| 12 |    |  3 | 11 |
+----+----+----+----+
|  4 |  8 |  9 |  5 |
+----+----+----+----+
|  2 | 10 |  7 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 | 13 |  1 |  6 |
+----+----+----+----+
|    | 12 |  3 | 11 |
+----+----+----+----+
|  4 |  8 |  9 |  5 |
+----+----+----+----+
|  2 | 10 |  7 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 | 13 |  1 |  6 |
+----+----+----+----+
|  4 | 12 |  3 | 11 |
+----+----+----+----+
|    |  8 |  9 |  5 |
+----+----+----+----+
|  2 | 10 |  7 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 | 13 |  1 |  6 |
+----+----+----+----+
|  4 | 12 |  3 | 11 |
+----+----+----+----+
|  8 |    |  9 |  5 |
+----+----+----+----+
|  2 | 10 |  7 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 | 13 |  1 |  6 |
+----+----+----+----+
|  4 |    |  3 | 11 |
+----+----+----+----+
|  8 | 12 |  9 |  5 |
+----+----+----+----+
|  2 | 10 |  7 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |    |  1 |  6 |
+----+----+----+----+
|  4 | 13 |  3 | 11 |
+----+----+----+----+
|  8 | 12 |  9 |  5 |
+----+----+----+----+
|  2 | 10 |  7 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |    |  6 |
+----+----+----+----+
|  4 | 13 |  3 | 11 |
+----+----+----+----+
|  8 | 12 |  9 |  5 |
+----+----+----+----+
|  2 | 10 |  7 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  4 | 13 |    | 11 |
+----+----+----+----+
|  8 | 12 |  9 |  5 |
+----+----+----+----+
|  2 | 10 |  7 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  4 | 13 |  9 | 11 |
+----+----+----+----+
|  8 | 12 |    |  5 |
+----+----+----+----+
|  2 | 10 |  7 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  4 | 13 |  9 | 11 |
+----+----+----+----+
|  8 | 12 |  7 |  5 |
+----+----+----+----+
|  2 | 10 |    | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  4 | 13 |  9 | 11 |
+----+----+----+----+
|  8 | 12 |  7 |  5 |
+----+----+----+----+
|  2 |    | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  4 | 13 |  9 | 11 |
+----+----+----+----+
|  8 |    |  7 |  5 |
+----+----+----+----+
|  2 | 12 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  4 |    |  9 | 11 |
+----+----+----+----+
|  8 | 13 |  7 |  5 |
+----+----+----+----+
|  2 | 12 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|    |  4 |  9 | 11 |
+----+----+----+----+
|  8 | 13 |  7 |  5 |
+----+----+----+----+
|  2 | 12 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  8 |  4 |  9 | 11 |
+----+----+----+----+
|    | 13 |  7 |  5 |
+----+----+----+----+
|  2 | 12 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  8 |  4 |  9 | 11 |
+----+----+----+----+
|  2 | 13 |  7 |  5 |
+----+----+----+----+
|    | 12 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  8 |  4 |  9 | 11 |
+----+----+----+----+
|  2 | 13 |  7 |  5 |
+----+----+----+----+
| 12 |    | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  8 |  4 |  9 | 11 |
+----+----+----+----+
|  2 |    |  7 |  5 |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  8 |  4 |  9 | 11 |
+----+----+----+----+
|    |  2 |  7 |  5 |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|    |  4 |  9 | 11 |
+----+----+----+----+
|  8 |  2 |  7 |  5 |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  4 |    |  9 | 11 |
+----+----+----+----+
|  8 |  2 |  7 |  5 |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  4 |  9 |    | 11 |
+----+----+----+----+
|  8 |  2 |  7 |  5 |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  4 |  9 |  7 | 11 |
+----+----+----+----+
|  8 |  2 |    |  5 |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  4 |  9 |  7 | 11 |
+----+----+----+----+
|  8 |  2 |  5 |    |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  4 |  9 |  7 |    |
+----+----+----+----+
|  8 |  2 |  5 | 11 |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  4 |  9 |    |  7 |
+----+----+----+----+
|  8 |  2 |  5 | 11 |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  4 |  9 |  5 |  7 |
+----+----+----+----+
|  8 |  2 |    | 11 |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  4 |  9 |  5 |  7 |
+----+----+----+----+
|  8 |    |  2 | 11 |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  4 |    |  5 |  7 |
+----+----+----+----+
|  8 |  9 |  2 | 11 |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  4 |  5 |    |  7 |
+----+----+----+----+
|  8 |  9 |  2 | 11 |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  4 |  5 |  2 |  7 |
+----+----+----+----+
|  8 |  9 |    | 11 |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  4 |  5 |  2 |  7 |
+----+----+----+----+
|  8 |  9 | 11 |    |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |  6 |
+----+----+----+----+
|  4 |  5 |  2 |    |
+----+----+----+----+
|  8 |  9 | 11 |  7 |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  3 |    |
+----+----+----+----+
|  4 |  5 |  2 |  6 |
+----+----+----+----+
|  8 |  9 | 11 |  7 |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |    |  3 |
+----+----+----+----+
|  4 |  5 |  2 |  6 |
+----+----+----+----+
|  8 |  9 | 11 |  7 |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  2 |  3 |
+----+----+----+----+
|  4 |  5 |    |  6 |
+----+----+----+----+
|  8 |  9 | 11 |  7 |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  2 |  3 |
+----+----+----+----+
|  4 |  5 |  6 |    |
+----+----+----+----+
|  8 |  9 | 11 |  7 |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  2 |  3 |
+----+----+----+----+
|  4 |  5 |  6 |  7 |
+----+----+----+----+
|  8 |  9 | 11 |    |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  2 |  3 |
+----+----+----+----+
|  4 |  5 |  6 |  7 |
+----+----+----+----+
|  8 |  9 |    | 11 |
+----+----+----+----+
| 12 | 13 | 10 | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  2 |  3 |
+----+----+----+----+
|  4 |  5 |  6 |  7 |
+----+----+----+----+
|  8 |  9 | 10 | 11 |
+----+----+----+----+
| 12 | 13 |    | 14 |
+----+----+----+----+

+----+----+----+----+
|  0 |  1 |  2 |  3 |
+----+----+----+----+
|  4 |  5 |  6 |  7 |
+----+----+----+----+
|  8 |  9 | 10 | 11 |
+----+----+----+----+
| 12 | 13 | 14 |    |
+----+----+----+----+

https://ideone.com/hqm1u

language:

C99 (gcc 8.3)

created:

visibility:

secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language