Implementation of A* for the 8-puzzle

a_star.cc

#include <cstdio>
#include <map>
#include <set>
#include <vector>

using namespace std;

const int dx[] = {-1, 0, 1, 0};
const int dy[] = {0, 1, 0, -1};

template<int SIZE>
struct board {
  template<class BOARD>
  board(BOARD board_array): board_(SIZE, vector<int>(SIZE)) {
    for (int i = 0; i < SIZE; ++i) {
      for (int j = 0; j < SIZE; ++j) {
        board_[i][j] = board_array[i][j];
      }
    }
  }

  vector<board> getNeighbours() {
    vector<board> res;
    for (int i = 0; i < SIZE; ++i) {
      for (int j = 0; j < SIZE; ++j) {
        if (board_[i][j]) {
          continue;
        }
        for (int dir = 0; dir < 4; ++dir) {
          int r = i + dx[dir];
          int c = j + dy[dir];
          if (r < 0 || r >= SIZE || c < 0 || c >= SIZE) {
            continue;
          }
          swap(board_[i][j], board_[r][c]);
          res.push_back(board(board_));
          swap(board_[i][j], board_[r][c]);
        }
      }
    }
    return res;
  }

  int getManhattanHeuristic() const {
    int res = 0;
    for (int i = 0; i < SIZE; ++i) {
      for (int j = 0; j < SIZE; ++j) {
        int num = board_[i][j];
        if (!num) {
          continue;
        }
        int row = (num - 1) / 3;
        int col = (num - 1) % 3;
        res += abs(row - i) + abs(col - j);
      }
    }
    return res;
  }

  bool isFinal() const {
    for (int i = 0; i < SIZE; ++i) {
      for (int j = 0; j < SIZE; ++j) {
        if (board_[i][j] && board_[i][j] != (3 * i + j + 1)) {
          return false;
        }
      }
    }
    return true;
  }

  bool operator<(const board<SIZE>& other) const {
    return board_ < other.board_;
  }

  vector<vector<int> > board_;
};

template<int SIZE>
struct state {
  state(const board<SIZE>& board, int dist): board_(board), dist(dist) {}
  board<SIZE> board_;
  int dist;
};

template<int SIZE>
bool operator<(const state<SIZE>& a, const state<SIZE>& b) {
  return a.dist == b.dist ? a.board_ < b.board_ : a.dist < b.dist;
}

template<int SIZE, int (board<SIZE>::*heuristic)(void) const>
int AStar(board<SIZE>& first) {
  map<board<SIZE>, int> dist;
  set<state<SIZE> > s;
  dist[first] = 0;
  s.insert(state<SIZE>(first, (first.*heuristic)()));

  while (!s.empty()) {
    state<SIZE> cur = *s.begin();
    s.erase(s.begin());
    int cur_dist = dist[cur.board_];
    if (cur.board_.isFinal()) {
      return cur_dist;
    }
    vector<board<SIZE> > next = cur.board_.getNeighbours();
    for (size_t i = 0; i < next.size(); ++i) {
      if (dist[next[i]] > cur_dist + 1) {
        s.erase(state<SIZE>(next[i], dist[next[i]] + (next[i].*heuristic)()));
        dist[next[i]] = cur_dist + 1;
        s.insert(state<SIZE>(next[i], dist[next[i]] + (next[i].*heuristic)()));
      }
    }
  }
  return -1;
}

int main() {
  board<3> b((int[3][3]){{6, 5, 3}, {2, 4, 8}, {7, 0, 1}});
  board<3> goal((int[3][3]){{1, 2, 3}, {4, 5, 6}, {7, 0, 8}});
  int dist = AStar<3, &board<3>::getManhattanHeuristic>(goal);
  printf("Distance to goal state: %d\n", dist);
}