# 15-Puzzle Solver
由於在過去課程曾經學到如何使用A\*演算法來尋找8-Puzzle的最佳解，因此在機緣巧合下決定將原有的程式升級，改成能夠解15-Puzzle的程式。
以下將使用C++作爲範例，完整程式碼可以在 https://github.com/lemtea8/15puzzle 看到。

## 15-Puzzle
*15-Puzzle的範例 (圖片來源: 維基百科)*

## Puzzle Implementation
首先需要一個負責對Puzzle進行移動等等功能的class，15-Puzzle的輸入是一個16個字元的16進位字串，例如: 2348170c56ab9def(空格視爲0)。

Puzzle狀態的儲存可以使用一個字元陣列 `char arr[16];`
但是由於15-Puzzle中每個方格的數值皆小於16，因此可以只使用4個bits來表達每個方格，相比之下char使用了1個byte，有一半的空間都浪費了。
16個方格總共只需要16x4=64個bits，因此剛好可以用一個uint64來儲存。
這個技巧叫做bit board，使用bit board有諸多好處，主要是能夠節省記憶體來加速程式。但缺點是bitwise的操作比較不好理解。
以下使用bit board的技巧來建構Puzzle的功能

先定義Puzzle這個class:

class Puzzle {
  public:
    Puzzle();
    Puzzle(const std::string &input);
    Puzzle(uint64_t bits);

  private:
    uint64_t bits;
};

建構子(爲了實作方便，方格儲存的順序是從低位元到高位元):

// "0" stands for the blank
Puzzle::Puzzle(const std::string &input) {
    this->bits = 0;
    for (int i = 0; i < input.size(); i++) {
        char c = input[i];
        uint64_t num = hex_to_int(c);
        // each cell takes four bits (0~F)
        this->bits |= num << (i * 4);
    }
}

讀取某個特定位置的數值(使用mask將uint64中特定位置的4個bit讀取出來):

uint8_t Puzzle::at(int n) {
    uint64_t mask = uint64_t(0b1111) << (n * 4);
    return (this->bits & mask) >> (n * 4);
}

設定某個特定位置的數值(先將該位置重設爲0000，再使用"or"將新的數值存入):

void Puzzle::set(int n, uint8_t val) {
    uint64_t mask = ~(uint64_t(0b1111) << (n * 4));
    this->bits &= mask; // set the target area to zero
    uint64_t valmask = uint64_t(val) << (n * 4);
    this->bits |= valmask;
}

檢查目前是否是目標狀態(goal):

bool Puzzle::is_goal() {
    return this->bits == uint64_t(0x0FEDCBA987654321);
}

接下來要實作移動方格的功能，爲了要移動方格首先要先確定0在puzzle中的哪個位置，因此先實作尋找0位置的funcition:

int Puzzle::find_zero_position() {
    for (int i = 0; i < 16; i++) {
        if (this->at(i) == 0) {
            return i;
        }
    }
    return -1;
}

互換兩個位置的值(15-Puzzle中，移動一次就相當於將該方格與0互換位置):

void Puzzle::swap(int i, int j) {
    uint64_t tmp = this->at(i);
    this->set(i, this->at(j));
    this->set(j, tmp);
}

實作移動的功能，向上移動表示0下面的方格往上移動(如果已經在最邊邊因此不能再移動了，則回傳false表示無法移動):

// returns false if the move is invalid
bool Puzzle::move(Direction dir) {
    int p0 = this->find_zero_position();
    int new_p0;

    switch (dir) {
    case UP:
        new_p0 = p0 + 4;
        if (new_p0 >= 16) {
            return false;
        }
        break;
    case DOWN:
        new_p0 = p0 - 4;
        if (new_p0 < 0) {
            return false;
        }
        break;
    case LEFT:
        new_p0 = p0 + 1;
        // not movable if zero is at the right most column
        if ((new_p0 >= 16) || (new_p0 % 4 == 0)) {
            return false;
        }
        break;
    case RIGHT:
        new_p0 = p0 - 1;
        // not movable if zero is at the left most column
        if ((new_p0 < 0) || ((new_p0 + 1) % 4 == 0)) {
            return false;
        }
        break;
    default:
        return false;
    }

    this->swap(p0, new_p0);
    return true;
}

## Algorithms

### Solvability
首先，需要先確認輸入的15-Puzzle是有解的(https://en.wikipedia.org/wiki/15_puzzle#Solvability)，實作solvable function:

bool Puzzle::solvable() {
    int inversion_count = 0;
    for (uint32_t i = 0; i < 15; i++) {
        if (at(i) == 0) {
            continue;
        }
        for (uint32_t j = i + 1; j < 16; j++) {
            if (at(j) != 0 && at(i) > at(j)) {
                inversion_count++;
            }
        }
    }
    int zero_row = this->zero_position / 4;
    return ((zero_row + inversion_count) % 2 != 0);
}

### BFS(Breadth-first search)
爲了找出最佳解，第一個可能的方法就是使用BFS來搜尋，但是由於每步會有2~4種選擇性(角落的有2種，邊邊的有3種，中間的有4種)，單純使用BFS會導致狀態數量快速增長直到記憶體無法負荷爲止(平均在第17步時就需要儲存超過1億個狀態，而最難的15-Puzzle需要80步才能解開)。

### A*
爲了解決BFS的不足，A\*引入了一個heuristic function(啟發函數)，這個函數可以用來評估當前狀態距離終點還需要多少成本，如果成本是0則表示已經抵達終點。
首先我們需要一個priority queue來儲存目前訪問過的狀態，並根據他們的優先順序來尋找下一個應該訪問的狀態。
這個優先順序表示爲 $f(n)$ ，其值越小越好，而 $f(n)=g(n)+h(n)$ ，其中$g(n)$表示從起始點到目前狀態所花費的成本，$h(n)$則表示heuristic function計算出的值。

### Heuristic
我們使用Manhattan distance作爲我們的heuristic function，他的計算方式是$h(n)=|x_n - x_g|+|y_n-y_g|$，其中$(x_n, y_n)$表示此方格現在的位置，$(x_g, y_g)$表示方格的終點位置。
將所有方格的值相加，就可以得到heuristic function的值。
*並非所有heuristic都可以找到最佳解，要找到最佳解需要滿足一定的條件( https://en.wikipedia.org/wiki/Admissible_heuristic )

在Puzzle中實作計算heuristic的function:

int manhattan_distance(int i, int j) {
    int ix = i % 4, iy = i / 4;
    int jx = j % 4, jy = j / 4;
    return abs(ix - jx) + abs(iy - jy);
}

int Puzzle::heuristic() {
    int val = 0;
    for (int i = 0; i < 16; i++) {
        uint8_t c = this->at(i);
        // does not include 0
        if (c != 0) {
            val += manhattan_distance(c - 1, i);
        }
    }
    return val;
}

## Solver
Solver中包含兩個關鍵元件: 一個是用來表示當前狀態的class，另一個是priority queue。

### State
State中需要保存:
1. 當前的Puzzle，以用來往下一個狀態走。
2. 目前走了多遠，也就是$g(n)$。這對找出最佳解至關重要。
3. 當前Puzzle的heuristic。
4. 上一個State的指標，能夠在抵達終點後回溯到起始狀態，找出最佳解的路徑。
5. 上一個State到目前這個State是採取了什麼動作，用途同4.

class State {
  public:
    State(State *parent, uint64_t bits, int walked, int heuristic,
          Direction dir) {
        this->parent = parent;
        this->bits = bits;
        this->walked = walked;
        this->heuristic = heuristic;
        this->dir = dir;
    }
    uint64_t get_bits() { return this->bits; }
    int heuristic;
    int walked;
    State *parent;
    Direction dir;

  private:
    uint64_t bits;
};

bool state_compare(State *i, State *j) {
    return i->walked + i->heuristic < j->walked + j->heuristic;
}

### Priority Queue
使用binary heap實作一個簡單的priority queue(想要更好的效能可以使用fibonacci heap):

template <typename T> class PriorityQueue {
  public:
    PriorityQueue(bool (*compare)(T i, T j)) {
        container = std::vector<T>(1);
        this->compare = compare;
    }

    PriorityQueue(bool (*compare)(T i, T j), int capacity) {
        container = std::vector<T>(1);
        container.reserve(capacity);
        this->compare = compare;
    }

    bool empty() { return container.size() == 1; }

    void push(T t) {
        container.push_back(t);
        heapify_bottomup(container.size() - 1);
    }

    void clear() {
        container.clear();
    }

    T top() { return container[1]; }

    void pop() {
        if (empty()) {
            return;
        }
        container[1] = container[container.size() - 1];
        container.pop_back();
        heapify_topdown(1);
    }

    int size() { return container.size() - 1; }

  private:
    std::vector<T> container;
    bool (*compare)(T i, T j);

    void heapify_bottomup(int curr) {
        T bottom = container[curr];
        while (curr != 1 && compare(bottom, container[curr / 2])) {
            container[curr] = container[curr / 2];
            curr /= 2;
        }
        container[curr] = bottom;
    }

    void heapify_topdown(int curr) {
        int size = container.size();
        T root = container[curr];
        int child;

        while (curr * 2 < size) {
            // left
            child = curr * 2;
            // right
            if (child < size && 
                compare(container[child + 1], container[child])) {
                child += 1;
            }
            if (compare(container[child], root)) {
                container[curr] = container[child];
            } else {
                break;
            }
            curr = child;
        }
        container[curr] = root;
    }
};

### A* Implementation
藉由上述兩個元件，使用A\*實作Solver class:

Solver::Solver() {}

std::vector<Direction> Solver::solve(Puzzle puzzle) {
    PriorityQueue<State *> pq(state_compare);
    std::vector<State *> used;

    int walked = 0;

    State *root =
        new State(nullptr, puzzle.get_bits(), walked, puzzle.heuristic(), UP);
    pq.push(root);
    State *last = nullptr;

    while (!pq.empty()) {
        State *curr = pq.top();
        last = curr;
        walked = curr->walked + 1;
        pq.pop();
        used.push_back(curr);

        Puzzle p(curr->get_bits());
        if (p.is_goal()) {
            break;
        }

        for (auto dir : {UP, DOWN, LEFT, RIGHT}) {
            Puzzle tmp = p;
            if (tmp.move(dir)) {
                State *next = new State(curr,
                    tmp.get_bits(), walked, tmp.heuristic(), dir);
                pq.push(next);
            }
        }
    }

    std::vector<Direction> answer;
    while (true) {
        if (last->parent == nullptr) {
            break;
        }
        answer.push_back(last->dir);
        last = last->parent;
    }
    std::reverse(answer.begin(), answer.end());

    while (!pq.empty()) {
        State *s = pq.top();
        pq.pop();
        delete s;
    }
    for (auto s : used) {
        delete s;
    }

    return answer;
}

至此基本的15-Puzzle solver已經完成了，能夠用來解步數較少的puzzle。

## Optimizations
整個程式還有一些可以最佳化的地方，用來加速程式。

### Caching 0 Position
在Puzzle class中可以看到，每次要移動的時候都需要重新找一次0的位置，這無疑是做白用工
將0的位置保存起來重複使用，可以節省不少時間。
但需要記得在建構子中初始化0的位置，以及每次進行move之後要更新0的位置。

class Puzzle {
  public:
    Puzzle();
    Puzzle(const std::string &input);
    Puzzle(uint64_t bits);

  private:
    uint64_t bits;
    int zero_position;
};

// "0" stands for the blank
Puzzle::Puzzle(const std::string &input) {
    this->bits = 0;
    ...
    this->zero_position = this->find_zero_position();
}

// returns false if the move is invalid
bool Puzzle::move(Direction dir) {
    int p0 = this->zero_position;
    int new_p0;

    ...

    this->swap(p0, new_p0);
    this->zero_position = new_p0;
    return true;
}

### Partially Update Heuristic
另外一個可以減少計算量的是heuristic，因爲每次移動一格只會影響到該格的Manhattan distance，完全可以不用重新計算其他格子的值:

class Puzzle {
  public:
    Puzzle();
    Puzzle(const std::string &input);
    Puzzle(uint64_t bits);

  private:
    uint64_t bits;
    int zero_position;
    int heuristic_v;
};

// "0" stands for the blank
Puzzle::Puzzle(const std::string &input) {
    this->bits = 0;
    ...
    this->zero_position = this->find_zero_position();
    this->heuristic_v = this->calculate_heuristic();
}

int Puzzle::heuristic() { return this->heuristic_v; }

// returns false if the move is invalid
bool Puzzle::move(Direction dir) {
    int p0 = this->zero_position;
    int new_p0;

    ...

    int tile = at(new_p0) - 1;
    this->heuristic_v -= manhattan_distance(tile, new_p0);
    this->swap(p0, new_p0);
    this->zero_position = new_p0;
    this->heuristic_v += manhattan_distance(tile, p0);
    return true;
}

### Avoid Duplicated States
如果檢查在A*過程中走到的State，會發現他其實常常重複訪問同一個Puzzle，這其實是非常沒有效率的。如果使用一個hashmap來記錄已經訪問過的Puzzle，可以大量減少不必要的計算。
這個hashmap的key是Puzzle，剛好Puzzle是用一個uint64來存，可以不需要重新寫一個hash function。而value則是儲存這個Puzzle是走多遠(walked)，因爲可能會發現一個比較短的路徑到達當前這個Puzzle，爲了避免找到次佳解，當遇到重複的Puzzle時且路徑較短時，需要更新他的值。

std::vector<Direction> Solver::solve(Puzzle puzzle) {
    PriorityQueue<State *> pq(state_compare);
    std::vector<State *> used;
    // record visited states with its priority
    std::unordered_map<uint64_t, int> visited;
    int walked = 0;

    State *root =
        new State(nullptr, puzzle.get_bits(), walked, puzzle.heuristic(), UP);
    visited[puzzle.get_bits()] = 0;
    pq.push(root);
    State *last = nullptr;

    while (!pq.empty()) {
        State *curr = pq.top();
        last = curr;
        walked = curr->walked + 1;
        pq.pop();
        used.push_back(curr);

        Puzzle p(curr->get_bits());
        if (p.is_goal()) {
            break;
        }

        for (auto dir : {UP, DOWN, LEFT, RIGHT}) {
            Puzzle tmp = p;
            tmp.move(dir);
            State *next = new State(curr,
                tmp.get_bits(), walked, tmp.heuristic(), dir);

            // if not visited before
            if (visited.count(tmp.get_bits()) == 0) {
                pq.push(next);
                visited[tmp.get_bits()] = walked;
            } else {
                // update if the path is shorter
                if (curr->walked < visited[tmp.get_bits()]) {
                    visited[tmp.get_bits()] = walked;
                    pq.push(next);
                }
            }
        }
    }

    std::vector<Direction> answer;
    while (true) {
        if (last->parent == nullptr) {
            break;
        }
        answer.push_back(last->dir);
        last = last->parent;
    }
    std::reverse(answer.begin(), answer.end());

    while (!pq.empty()) {
        State *s = pq.top();
        pq.pop();
        delete s;
    }
    for (auto s : used) {
        delete s;
    }

    return answer;
}

## Limitations
A\*能比BFS更有效率的找出解答，但是在問題比較困難的時候，A\*依然會因爲需要記憶太多狀態導致記憶體不足。例如：`0291ca8d6574feb3`的解需要60步，這導致A*在解的過程中需要使用超過8GiB的記憶體，因而成爲一個主要的限制。爲了解決這個問題，我們改使用IDA\*演算法。

## IDA\* (Iterative Deepening A\*)
IDA\*的本質其實比較偏向DFS(Depth First Search)，他主要的概念是給與一個預算，並使用DFS往下搜尋，直到超出預算則返回繼續從上一個狀態開始。當遍歷完成後，根據這次遍歷的結果給出一個新的預算，重新使用這個預算用DFS搜尋。IDA\*會重複這個過程直到找到解爲止。

IDA\*的優點: 不需要記憶大量狀態，因此不會有記憶體爆炸的問題。
缺點: 會大量重複訪問曾經訪問過的狀態。

雖然IDA\*相較於A\*而言會大量訪問重複的狀態，但是在實務上由於A\*需要維護一個龐大的priority queue(動輒幾百、千萬)，消耗了大量的運算成本。最終的結果是IDA\*有更好的效率以及更短的執行時間，同時記憶體使用量甚少。

IDA\*的程式碼如下:

const int FOUND = -1;

int Solver::dfs(Puzzle p, int walked, int limit) {
    this->count++;
    int h = p.heuristic();
    int f = walked + h;

    if (f > limit) {
        return f;
    }
    if (p.is_goal()) {
        return FOUND;
    }

    int min = INT_MAX;
    for (auto dir : {UP, DOWN, LEFT, RIGHT}) {
        Puzzle tmp = p;
        if (!tmp.move(dir)) {
            continue;
        }
        auto iter = std::find(this->visited.begin(), this->visited.end(),
            tmp.get_bits());
        if (iter != this->visited.end()) {
            continue;
        }
        this->visited.push_back(tmp.get_bits());
        int res = dfs(tmp, walked + 1, limit);
        if (res == FOUND) {
            this->path.push_back(dir);
            return FOUND;
        }
        this->visited.pop_back();
        if (res < min) {
            min = res;
        }
    }
    return min;
}

std::vector<Direction> Solver::solve(Puzzle puzzle) {
    this->path.clear();
    this->visited.clear();
    this->count = 0;

    int budget = puzzle.heuristic();

    // IDA*
    while (true) {
        int new_budget = dfs(puzzle, 0, budget);
        if (new_budget == FOUND) {
            break;
        }
        budget = new_budget;
    }
    std::reverse(this->path.begin(), this->path.end());

    return this->path;
}

其中，Solver.visited是一個vector，用來記錄目前DFS路上訪問過的狀態，避免重複訪問。
不使用unordered_set的原因是由於這些狀態的數量通常很小，使用set反而會減速。
Solver.path則是在找到終點狀態時，在遞迴返回時將找到的路徑一一填入解答中(但最後要reverse才是答案)。

至此，整個15-puzzle solver就算是完成了。雖然他在解較難的問題時(>60幾步)需要花費大量時間(成指數增長)，但不會吃記憶體導致甚至沒辦法解開。
還有其他的改進方法就是找一個更強大的heuristic function(在搜尋演算法中，好的heuristic是相當重要的)，讓程式在搜尋中少走許多歪路，才能快速找到解答。

## Test Data
- 2348170c56ab9def (15 moves)
- 51309af4d7b826ec (25 moves)
- 1f3452d8a70b96ec (30 moves)
- 12345dc8796eba0f (33 moves)
- 1f345dc8796eab20 (44 moves)
- 0bd45c329671af8e (50 moves)
- 58d9ebc1324a70f6 (56 moves)
- 38abfe7951024c6d (58 moves)
- cbfed67a13248095 (64 moves)