Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Implementation of A* for the 8-puzzle
#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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment