# 12819 - 15 Puzzle
>author: Utin
###### tags: `Heuristic`

---

## Brief
See the code below

## Solution 0

#include <bits/stdc++.h>

enum dir {
    DOWN, UP, LEFT, RIGHT, NA
};

class State {
    public:
        int puzzle[4][4];
        int past;
        int score;
        int ex, ey;
        dir pre_move;

        State(int pu[4][4], dir p, int x, int y);
        bool operator< (const State &rhs) const;
        void setScore();
        void Update(int newX, int newY, dir preMove);
};

const int GoalX[16] = {3, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3};
const int GoalY[16] = {3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2, 3, 0, 1, 2};
const int ns[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

std::priority_queue<State> process;

int main() {
    int init[4][4], e_x, e_y;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            std::cin >> init[i][j];
            if (init[i][j] == 0) {
                e_x = i;
                e_y = j;
            }
        }
    }

    // initial state
    process.push(State(init, NA, e_x, e_y));

    while (process.size()) {
        State curr = process.top();
        if (curr.score == 0) {
            std::cout << curr.past << '\n';
            return 0;
        }
        process.pop();
        for (int i = 0; i < 4; i++) {

            // next empty position
            int newX = curr.ex + ns[i][0];
            int newY = curr.ey + ns[i][1];

            // outside the map
            if (newX < 0 || newX > 3 || newY < 0 || newY > 3) continue;

            // prevent from moving backward
            if (i == DOWN && curr.pre_move == UP) continue;
            if (i == UP && curr.pre_move == DOWN) continue;
            if (i == LEFT && curr.pre_move == RIGHT) continue;
            if (i == RIGHT && curr.pre_move == LEFT) continue;

            // construct the next State
            State nextState = curr;
            nextState.Update(newX, newY, (dir)i);
            process.push(nextState);
        }
    }
    std::cout << -1 << '\n';
}

// construct a new State
State::State(int pu[4][4], dir p, int x, int y)
: puzzle(), pre_move(p), past(), score(), ex(x), ey(y) {
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            puzzle[i][j] = pu[i][j];
        }
    }
    setScore();
}

// sort from the largest to the smallest
bool State::operator< (const State &rhs) const {
    return this->score + this->past > rhs.score + rhs.past;
}

void State::setScore() {
    int s = 0;
    int goalX, goalY;
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {

            // empty
            if (puzzle[i][j] == 0) continue;

            // future path
            goalX = GoalX[puzzle[i][j]];
            goalY = GoalY[puzzle[i][j]];
            s += abs(i - goalX) + abs(j - goalY);

            // linear conflict
            if (i == goalX) {
                for (int k = j; k < 4; k++) {
                    if (puzzle[i][k] > 0 && GoalX[puzzle[i][k]] == i && puzzle[i][j] > puzzle[i][k]) {
                        s += 2;
                    }
                }
            }
            if (j == goalY) {
                for (int k = i; k < 4; k++) {
                    if (puzzle[k][j] > 0 && GoalY[puzzle[k][j]] == j && puzzle[i][j] > puzzle[k][j]) {
                        s += 2;
                    }
                }
            }
        }
    }
    this->score = s;
}

void State::Update(int newX, int newY, dir preMove) {
    pre_move = preMove;
    puzzle[ex][ey] = puzzle[newX][newY];
    puzzle[newX][newY] = 0;
    ex = newX, ey = newY;
    past++;
    setScore();
}

// By Utin

## Reference